Document Open Access Logo

Uniformisation Gives the Full Strength of Regular Languages

Authors Nathan Lhote, Vincent Michielini, Michał Skrzypczak

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.61.pdf
  • Filesize: 0.5 MB
  • 13 pages

Document Identifiers

Author Details

Nathan Lhote
  • University of Warsaw, Poland
Vincent Michielini
  • University of Warsaw, Poland
Michał Skrzypczak
  • University of Warsaw, Poland

Funding

The first two authors have been supported by the European Research Council (ERC) grant under the European Union’s Horizon 2020 research and innovation programme (ERC Consolidator Grant LIPA, grant agreement No. 683080). The first author has also been supported by the DeLTA project (ANR-16-CE40-0007). The last author has been supported by Poland’s National Science Centre (NCN) (grant No. 2016/21/D/ST6/00491).

Cite As Get BibTex

Nathan Lhote, Vincent Michielini, and Michał Skrzypczak. Uniformisation Gives the Full Strength of Regular Languages. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 61:1-61:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.MFCS.2019.61

Abstract

Given R a binary relation between words (which we treat as a language over a product alphabet AxB), a uniformisation of it is another relation L included in R which chooses a single word over B, for each word over A whenever there exists one. It is known that MSO, the full class of regular languages, is strong enough to define a uniformisation for each of its relations. The quest of this work is to see which other formalisms, weaker than MSO, also have this property. In this paper, we solve this problem for pseudo-varieties of semigroups: we show that no nonempty pseudo-variety weaker than MSO can provide uniformisations for its relations.

Subject Classification

ACM Subject Classification
  • Theory of computation → Regular languages
Keywords
  • pseudo-variety
  • finite word
  • semigroup
  • uniformisation
  • regular language

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Mikołaj Bojańczyk. Effective characterizations of tree logics. In PODS, pages 53-66, 2008. Google Scholar
  2. Julius Richard Büchi. Weak Second-Order Arithmetic and Finite Automata. Mathematical Logic Quarterly, 6(1-‐6):66-92, 1960. Google Scholar
  3. Julius Richard Büchi and Lawrence H. Landweber. Solving Sequential Conditions by Finite-State Strategies. Transactions of the American Mathematical Society, 138:295-311, 1969. Google Scholar
  4. Arnaud Carayol and Christof Löding. MSO on the infinite binary tree: Choice and order. In CSL, pages 161-176, 2007. Google Scholar
  5. Volker Diekert, Paul Gastin, and Manfred Kufleitner. A Survey on Small Fragments of First-Order Logic over Finite Words. Int. J. Found. Comput. Sci., 19(3):513-548, 2008. URL: https://doi.org/10.1142/S0129054108005802.
  6. Samuel Eilenberg. Automata, languages, and machines. Pure and Applied Mathematics. Elsevier Science, 1974. Google Scholar
  7. Calvin C. Elgot. Decision Problems of Finite Automata Design and Related Arithmetics. Transactions of the American Mathematical Society, 98(1):21-51, 1961. Google Scholar
  8. Yuri Gurevich and Saharon Shelah. Rabin’s uniformization problem. Journal of Symbolic Logic, 48(4):1105-1119, 1983. Google Scholar
  9. Alexander Kechris. Classical descriptive set theory. Springer-Verlag, New York, 1995. Google Scholar
  10. Shmuel Lifsches and Saharon Shelah. Uniformization and Skolem Functions in the Class of Trees. Journal of Symbolic Logic, 63(1):103-127, 1998. Google Scholar
  11. Robert McNaughton and Seymour Papert. Counter-free automata. M.I.T. Press research monographs. M.I.T. Press, 1971. Google Scholar
  12. Vincent Michielini. Uniformization Problem for Variants of First Order Logic over Finite Words. In DLT, pages 516-528, 2018. Google Scholar
  13. Dominique Perrin and Jean-Éric Pin. Infinite Words: Automata, Semigroups, Logic and Games. Elsevier, 2004. Google Scholar
  14. Jean-Éric Pin and Howard Straubing. Some results on C-varieties. ITA, 39(1):239-262, 2005. URL: https://doi.org/10.1051/ita:2005014.
  15. Michael Oser Rabin. Decidability of second-order theories and automata on infinite trees. Transactions of the American Mathematical Society, 141:1-35, 1969. Google Scholar
  16. Michael Oser Rabin and Dana Scott. Finite Automata and Their Decision Problems. IBM Journal of Research and Development, 3(2):114-125, April 1959. Google Scholar
  17. Alexander Rabinovich. On decidability of monadic logic of order over the naturals extended by monadic predicates. Information and Computation, 205(6):870-889, 2007. Google Scholar
  18. Jan Reiterman. The Birkhoff theorem for finite algebras. Algebra Universalis, 14(1):1-10, 1982. Google Scholar
  19. Marcel Paul Schützenberger. On Finite Monoids Having Only Trivial Subgroups. Information and Control, 8(2):190-194, 1965. Google Scholar
  20. Dirk Siefkes. The recursive sets in certain monadic second order fragments of arithmetic. Arch. Math. Logik, 17(1-2):71-80, 1975. Google Scholar
  21. Imre Simon. Piecewise testable events. In Automata Theory and Formal Languages, pages 214-222, 1975. Google Scholar
  22. Imre Simon. Word Ramsey theorems. In B. Bollobas, editor, Graph Theory and Combinatorics, pages 283-291. Academic Press, London, 1984. Google Scholar
  23. Denis Thérien and Thomas Wilke. Over Words, Two Variables Are as Powerful as One Quantifier Alternation. In STOC, pages 234-240, 1998. Google Scholar
  24. Wolfgang Thomas. Star-Free Regular Sets of omega-Sequences. Information and Control, 42(2):148-156, 1979. Google Scholar
  25. Boris A. Trakhtenbrot. Finite automata and the monadic predicate calculus. Siberian Mathematical Journal, 3(1):103-131, 1962. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact