View in EDS PDF Full Text

Fragments of First-Order Logic over Infinite Words.

Saved in:
Bibliographic Details
Title: Fragments of First-Order Logic over Infinite Words.
Authors: Diekert, Volker1 diekert@fmi.uni-stuttgart.de, Kufleitner, Manfred1 kufleitner@fmi.uni-stuttgart.de
Source: Theory of Computing Systems. Apr2011, Vol. 48 Issue 3, p486-516. 31p.
Subjects: First-order logic, Storage fragmentation (Computer science), Topology, Machine theory, Vocabulary, Algebra, Duality theory (Mathematics)
Abstract: We give topological and algebraic characterizations as well as language theoretic descriptions of the following subclasses of first-order logic FO[<] for ω-languages: Σ, FO, FO∩Σ, and Δ (and by duality Π and FO∩Π). These descriptions extend the respective results for finite words. In particular, we relate the above fragments to language classes of certain (unambiguous) polynomials. An immediate consequence is the decidability of the membership problem of these classes, but this was shown before by Wilke (Classifying Discrete Temporal Properties. Habilitationsschrift, Universität Kiel, April ) and Bojańczyk (Lecture Notes in Computer Science, vol. 4962, pp. 172-185, ) and is therefore not our main focus. The paper is about the interplay of algebraic, topological, and language theoretic properties. [ABSTRACT FROM AUTHOR]
Copyright of Theory of Computing Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Links:
  – Type: pdflink
Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 57963762
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Fragments of First-Order Logic over Infinite Words.
– Name: Author
  Label: Authors
  Group: Au
  Data: &lt;searchLink fieldCode=&quot;AR&quot; term=&quot;%22Diekert%2C+Volker%22&quot;&gt;Diekert, Volker&lt;/searchLink&gt;&lt;relatesTo&gt;1&lt;/relatesTo&gt;&lt;i&gt; diekert@fmi.uni-stuttgart.de&lt;/i&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;AR&quot; term=&quot;%22Kufleitner%2C+Manfred%22&quot;&gt;Kufleitner, Manfred&lt;/searchLink&gt;&lt;relatesTo&gt;1&lt;/relatesTo&gt;&lt;i&gt; kufleitner@fmi.uni-stuttgart.de&lt;/i&gt;
– Name: TitleSource
  Label: Source
  Group: Src
  Data: &lt;searchLink fieldCode=&quot;JN&quot; term=&quot;%22Theory+of+Computing+Systems%22&quot;&gt;Theory of Computing Systems&lt;/searchLink&gt;. Apr2011, Vol. 48 Issue 3, p486-516. 31p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: &lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22First-order+logic%22&quot;&gt;First-order logic&lt;/searchLink&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Storage+fragmentation+%28Computer+science%29%22&quot;&gt;Storage fragmentation (Computer science)&lt;/searchLink&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Topology%22&quot;&gt;Topology&lt;/searchLink&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Machine+theory%22&quot;&gt;Machine theory&lt;/searchLink&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Vocabulary%22&quot;&gt;Vocabulary&lt;/searchLink&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Algebra%22&quot;&gt;Algebra&lt;/searchLink&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Duality+theory+%28Mathematics%29%22&quot;&gt;Duality theory (Mathematics)&lt;/searchLink&gt;
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: We give topological and algebraic characterizations as well as language theoretic descriptions of the following subclasses of first-order logic FO[&lt;] for ω-languages: Σ, FO, FO∩Σ, and Δ (and by duality Π and FO∩Π). These descriptions extend the respective results for finite words. In particular, we relate the above fragments to language classes of certain (unambiguous) polynomials. An immediate consequence is the decidability of the membership problem of these classes, but this was shown before by Wilke (Classifying Discrete Temporal Properties. Habilitationsschrift, Universit&#228;t Kiel, April ) and Bojańczyk (Lecture Notes in Computer Science, vol. 4962, pp. 172-185, ) and is therefore not our main focus. The paper is about the interplay of algebraic, topological, and language theoretic properties. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: &lt;i&gt;Copyright of Theory of Computing Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder&#39;s express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.&lt;/i&gt; (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=57963762
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1007/s00224-010-9266-7
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 31
        StartPage: 486
    Subjects:
      – SubjectFull: First-order logic
        Type: general
      – SubjectFull: Storage fragmentation (Computer science)
        Type: general
      – SubjectFull: Topology
        Type: general
      – SubjectFull: Machine theory
        Type: general
      – SubjectFull: Vocabulary
        Type: general
      – SubjectFull: Algebra
        Type: general
      – SubjectFull: Duality theory (Mathematics)
        Type: general
    Titles:
      – TitleFull: Fragments of First-Order Logic over Infinite Words.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Diekert, Volker
      – PersonEntity:
          Name:
            NameFull: Kufleitner, Manfred
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 04
              Text: Apr2011
              Type: published
              Y: 2011
          Identifiers:
            – Type: issn-print
              Value: 14324350
          Numbering:
            – Type: volume
              Value: 48
            – Type: issue
              Value: 3
          Titles:
            – TitleFull: Theory of Computing Systems
              Type: main
ResultId 1