LIPIcs.MFCS.2019.29.pdf
- Filesize: 0.72 MB
- 14 pages
Document
The Quantifier Alternation Hierarchy of Synchronous Relations
Authors
-
Part of:
Volume:
44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-08-20
Cite AsGet BibTex
Diego Figueira, Varun Ramanathan, and Pascal Weil. The Quantifier Alternation Hierarchy of Synchronous Relations. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 29:1-29:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.MFCS.2019.29
https://doi.org/10.4230/LIPIcs.MFCS.2019.29
Abstract
The class of synchronous relations, also known as automatic or regular, is one of the most studied subclasses of rational relations. It enjoys many desirable closure properties and is known to be logically characterized: the synchronous relations are exactly those that are defined by a first-order formula on the structure of all finite words, with the prefix, equal-length and last-letter predicates. Here, we study the quantifier alternation hierarchy of this logic. We show that it collapses at level Sigma_3 and that all levels below admit decidable characterizations. Our results reveal the connections between this hierarchy and the well-known hierarchy of first-order defined languages of finite words.
Subject Classification
ACM Subject Classification
- Theory of computation → Logic
- Theory of computation → Transducers
Keywords
- synchronous relations
- automatic relations
- first-order logic
- characterization
- quantifier alternation
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Parosh Aziz Abdulla, Bengt Jonnson, Marcus Nilsson, and Mayank Saksena. A survey of regular model checking. In International Conference on Concurrency Theory (CONCUR), pages 35-48, 2003.
- Pablo Barceló, Leonid Libkin, Anthony Widjaja Lin, and Peter T. Wood. Expressive Languages for Path Queries over Graph-Structured Data. ACM Transactions on Database Systems (TODS), 37(4):31, 2012. URL: https://doi.org/10.1145/2389241.2389250.
- Michael Benedikt, Leonid Libkin, Thomas Schwentick, and Luc Segoufin. Definable relations and first-order query languages over strings. Journal of the ACM, 50(5):694-751, 2003. URL: https://doi.org/10.1145/876638.876642.
-
Jean Berstel. Transductions and Context-Free Languages. B. G. Teubner, 1979.
- Achim Blumensath and Erich Grädel. Automatic Structures. In Annual IEEE Symposium on Logic in Computer Science (LICS), pages 51-62. IEEE Computer Society Press, 2000. URL: https://doi.org/10.1109/LICS.2000.855755.
-
Ahmed Bouajjani, Bengt Jonsson, Marcus Nilsson, and Tayssir Touili. Regular Model Checking. In International Conference on Computer Aided Verification (CAV), pages 403-418. Springer, 2000.
-
J. Richard Büchi. On a Decision Method in Restricted Second-Order Arithmetic. In Proc. Int. Congr. for Logic, Methodology, and Philosophy of Science, pages 1-11. Stanford Univ. Press, 1962.
-
Christian Choffrut. Relations over Words and Logic: A Chronology. Bulletin of the EATCS, 89:159-163, 2006.
- Samuel Eilenberg, Calvin C. Elgot, and John C. Shepherdson. Sets recognized by n-tape automata. Journal of Algebra, 13(4):447-464, 1969. URL: https://doi.org/10.1016/0021-8693(69)90107-0.
- Graham Higman. Ordering by divisibility in abstract algebras. Proceedings of the London Mathematical Society (3), 2(7):326-336, 1952. URL: https://doi.org/10.1112/plms/s3-2.1.326.
-
M. Lothaire. Combinatorics on Words, volume 17 of Encyclopedia of Mathematics and its Applications. Addison-Wesley, Reading, MA, 1983. Reprinted by Cambridge University Press, 1997.
-
Robert McNaughton and Seymour Papert. Counter-Free Automata. The MIT Press, Cambridge, Mass., 1971.
-
Jean-Éric Pin. Varieties of Formal Languages. North Oxford Academic, London, 1986.
-
Jean-Éric Pin and Howard Straubing. Monoids of upper triangular matrices. In Colloquia Mathematica Societatis Janos Bolyai, pages 259-272, 1981.
-
Jean-Éric Pin and Pascal Weil. Polynomial Closure and Unambiguous Product. Theory of Computing Systems, 30(4):383-422, 1997.
- Thomas Place and Marc Zeitoun. Going Higher in the First-Order Quantifier Alternation Hierarchy on Words. In International Colloquium on Automata, Languages and Programming (ICALP), pages 342-353, 2014. URL: https://doi.org/10.1007/978-3-662-43951-7_29.
- Thomas Place and Marc Zeitoun. The tale of the quantifier alternation hierarchy of first-order logic over words. SIGLOG News, 2(3):4-17, 2015. URL: https://doi.org/10.1145/2815493.2815495.
- Thomas Place and Marc Zeitoun. Concatenation Hierarchies: New Bottle, Old Wine. In International Computer Science Symposium in Russia (CSR), pages 25-37, 2017. URL: https://doi.org/10.1007/978-3-319-58747-9_5.
-
Marcel Paul Schützenberger. On finite monoids having only trivial subgroups. Information and Control, 8:190-194, 1965.
-
Imre Simon. Piecewise testable events. In H. Barkhage, editor, Automata Theory and Formal Languages, 2nd GI Conference, Kaiserslautern, May 22-23, 1975, volume 33 of LNCS, pages 214-222. Springer, 1975.
-
Howard Straubing. Finite Automata, Formal Logic, and Circuit Complexity. Birkhäuser, Boston, Basel and Berlin, 1994.
-
Howard Straubing and Pascal Weil. An introduction to automata theory. In Deepak D'Souza and Priti Shankar, editors, Modern applications of automata theory, volume 2 of I.I.Sc. Monographs, pages 3-43. World Scientific, 2012.