Document Open Access Logo

Unambiguous Languages Exhaust the Index Hierarchy

Author Michal Skrzypczak

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.140.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Author Details

Michal Skrzypczak
  • University of Warsaw, Banacha 2, 02-097 Warsaw, Poland

Funding

This work has been supported by Poland’s NSC (NCN) grant 2016/21/D/ST6/00491.

Cite As Get BibTex

Michal Skrzypczak. Unambiguous Languages Exhaust the Index Hierarchy. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 140:1-140:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.140

Abstract

This work is a study of the expressive power of unambiguity in the case of automata over infinite trees. An automaton is called unambiguous if it has at most one accepting run on every input, the language of such an automaton is called an unambiguous language. It is known that not every regular language of infinite trees is unambiguous. Except that, very little is known about which regular tree languages are unambiguous.
This paper answers the question whether unambiguous languages are of bounded complexity among all regular tree languages. The notion of complexity is the canonical one, called the (parity or Rabin/Mostowski) index hierarchy. The answer is negative, as exhibited by a family of examples of unambiguous languages the cannot be recognised by any alternating parity tree automata of bounded range of priorities.
Hardness of the examples is based on the theory of signatures, previously studied by Walukiewicz. The technical core of the article is a definition of the canonical signatures together with a parity game that compares signatures of a given pair of parity games (of the same index).

Subject Classification

ACM Subject Classification
  • Theory of computation → Tree languages
Keywords
  • unambiguous automata
  • parity games
  • infinite trees
  • index hierarchy

Metrics

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

Related Versions

References

  1. André Arnold. The mu-calculus alternation-depth hierarchy is strict on binary trees. ITA, 33(4/5):329-340, 1999. Google Scholar
  2. André Arnold and Damian Niwiński. Continuous separation of game languages. Fundamenta Informaticae, 81(1-3):19-28, 2007. Google Scholar
  3. Marcin Bilkowski and Michał Skrzypczak. Unambiguity and uniformization problems on infinite trees. In CSL, pages 81-100, 2013. Google Scholar
  4. Julian C. Bradfield. Simplifying the modal mu-calculus alternation hierarchy. In STACS, pages 39-49, 1998. Google Scholar
  5. Arnaud Carayol and Christof Löding. MSO on the infinite binary tree: Choice and order. In CSL, pages 161-176, 2007. Google Scholar
  6. Arnaud Carayol, Christof Löding, Damian Niwiński, and Igor Walukiewicz. Choice functions and well-orderings over the infinite binary tree. Cent. Europ. J. of Math., 8:662-682, 2010. Google Scholar
  7. Thomas Colcombet. Forms of determinism for automata. In STACS, pages 1-23, 2012. Google Scholar
  8. Jacques Duparc, Kevin Fournier, and Szczepan Hummel. On unambiguous regular tree languages of index (0, 2). In CSL, pages 534-548, 2015. Google Scholar
  9. Allen Emerson and Charanjit Jutla. Tree automata, mu-calculus and determinacy. In FOCS'91, pages 368-377, 1991. Google Scholar
  10. Yuri Gurevich and Saharon Shelah. Rabin’s uniformization problem. J. Symb. Log., 48(4):1105-1119, 1983. Google Scholar
  11. Szczepan Hummel. Unambiguous tree languages are topologically harder than deterministic ones. In GandALF, pages 247-260, 2012. Google Scholar
  12. Szczepan Hummel. Topological Complexity of Sets Defined by Automata and Formulas. PhD thesis, University of Warsaw, 2017. Google Scholar
  13. Alexander S. Kechris. Classical descriptive set theory. Springer-Verlag, New York, 1995. Google Scholar
  14. Andrzej W. Mostowski. Games with forbidden positions. Technical report, University of Gdańsk, 1991. Google Scholar
  15. Damian Niwiński and Igor Walukiewicz. Ambiguity problem for automata on infinite trees. unpublished, 1996. Google Scholar
  16. Richard E. Stearns and Harry B. Hunt. On the equivalence and containment problems for unambiguous regular expressions, regular grammars and finite automata. SIAM Journal of Computing, 14(3):598-611, 1985. Google Scholar
  17. Robert S. Streett and E. Allen Emerson. An automata theoretic decision procedure for the propositional mu-calculus. Information and Computation, 81(3):249-264, 1989. Google Scholar
  18. Wolfgang Thomas. Languages, automata, and logic. In Handbook of Formal Languages, pages 389-455. Springer, 1996. Google Scholar
  19. Wolfgang Thomas and Helmut Lescow. Logical specifications of infinite computations. In REX School/Symposium, pages 583-621, 1993. Google Scholar
  20. Igor Walukiewicz. Pushdown processes: Games and model checking. In Rajeev Alur and Thomas A. Henzinger, editors, Computer Aided Verification, pages 62-74, Berlin, Heidelberg, 1996. Springer Berlin Heidelberg. Google Scholar
  21. Igor Walukiewicz. Monadic second-order logic on tree-like structures. Theoretical Computer Science, 275(1-2):311-346, 2002. 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