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 |
