Document Open Access Logo

On Unambiguous Regular Tree Languages of Index (0,2)

Authors Jacques Duparc, Kevin Fournier, Szczepan Hummel

PDF
Thumbnail PDF

File

LIPIcs.CSL.2015.534.pdf
  • Filesize: 1.31 MB
  • 15 pages

Document Identifiers

Author Details

Jacques Duparc
Kevin Fournier
Szczepan Hummel

Cite As Get BibTex

Jacques Duparc, Kevin Fournier, and Szczepan Hummel. On Unambiguous Regular Tree Languages of Index (0,2). In 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 41, pp. 534-548, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.CSL.2015.534

Abstract

Unambiguous automata are usually seen as a natural class of automata in-between deterministic and nondeterministic ones. We show that in case of infinite tree languages, the unambiguous ones are topologically far more complicated than the deterministic ones. We do so by providing operations that generate a family (A_{alpha})_{alpha < phi_2(0)} of unambiguous automata such that:

1. It respects the strict Wadge ordering: alpha < beta if and only if A_{alpha} <_W A_{beta}. This can be established without the help of any determinacy principle, simply by providing effective winning strategies in the underlying games.

2. Its length (phi_2(0)) is the first fixpoint of the ordinal function that itself enumerates all fixpoints of the ordinal exponentiation x |-> omega^x: an ordinal tremendously larger than (omega^(omega))^3 +3 which is the height of the Wadge hierarchy of deterministic tree languages as uncovered by Filip Murlak.

3. The priorities of all these parity automata only range from 0 to 2.

Subject Classification

Keywords
  • Tree Automata
  • Unambiguity
  • Wadge Hierarchy.

Metrics

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

References

  1. Alessandro Andretta and Alain Louveau. Wadge degrees and pointclasses. In Alexander S. Kechris, Benedikt Löwe, and John R. Steel, editors, Wadge Degrees and Projective Ordinals: The Cabal Seminar, Volume II. Cambridge University Press, 2012. Google Scholar
  2. André Arnold. Rational omega-languages are non-ambiguous. Theoretical Computer Science, 26:221-223, 1983. Google Scholar
  3. André Arnold, Jacques Duparc, Filip Murlak, and Damian Niwiński. On the topological complexity of tree languages. Logic and automata: History and Perspectives, 2:9-29, 2007. Google Scholar
  4. Mikołaj Bojańczyk. A bounding quantifier. In CSL, pages 41-55, 2004. Google Scholar
  5. Mikołaj Bojańczyk, Tomasz Gogacz, Henryk Michalewski, and Michał Skrzypczak. On the decidability of MSO+U on infinite trees. In ICALP, pages 50-61, 2014. Google Scholar
  6. Mikołaj Bojańczyk, Paweł Parys, and Szymon Toruńczyk. The MSO+U theory of (N, less) is undecidable. CoRR, abs/1502.04578, 2015. Google Scholar
  7. Arnaud Carayol and Christof Löding. MSO on the infinite binary tree: Choice and order. In CSL, pages 161-176, 2007. Google Scholar
  8. Arnaud Carayol, Christof Löding, Damian Niwiński, and Igor Walukiewicz. Choice functions and well-orderings over the infinite binary tree. Central European Journal of Mathematics, 8:662-682, 2010. Google Scholar
  9. Thomas Colcombet. Forms of determinism for automata (invited talk). In STACS, pages 1-23, 2012. Google Scholar
  10. Jacques Duparc. Wadge hierarchy and Veblen hierarchy, Part I : Borel sets of finite rank. The Journal of Symbolic Logic, 66(1):56-86, 2001. Google Scholar
  11. Jacques Duparc and Filip Murlak. On the topological complexity of weakly recognizable tree languages. In Fundamentals of Computation Theory, 16th International Symposium, FCT 2007, Budapest, Hungary, August 27-30, 2007, Proceedings, pages 261-273, 2007. Google Scholar
  12. Szczepan Hummel. Unambiguous tree languages are topologically harder than deterministic ones. In GandALF, pages 247-260, 2012. Google Scholar
  13. Filip Murlak. The Wadge hierarchy of deterministic tree languages. Logical Methods in Computer Science, 4(4), 2008. Google Scholar
  14. Damian Niwiński and Igor Walukiewicz. Ambiguity problem for automata on infinite trees. unpublished note, 1996. Google Scholar
  15. Michael O. Rabin. Decidability of second-order theories and automata on infinite trees. Transactions of the AMS, 141:1-23, 1969. Google Scholar
  16. Robert Van Wesep. Wadge degrees and descriptive set theory. In Alexander S. Kechris, Benedikt Löwe, and John R. Steel, editors, Wadge Degrees and Projective Ordinals: The Cabal Seminar, Volume II. Cambridge University Press, 2012. Google Scholar
  17. Oswald Veblen. Increasing functions of finite and transfinite ordinals. Transactions of the American Mathematical Society, 9(3):280-292, 1908. Google Scholar
  18. William W. Wadge. Reducibility and determinateness on the Baire space. PhD thesis, University of California, Berkeley, 1984. 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