It is Undecidable if Two Regular Tree Languages can be Separated by a Deterministic Tree-walking Automaton

• Autorzy: Bojańczyk M.

Identyfikatory

DOI

10.3233/FI-2017-1551

• Języki publikacji: EN

Abstrakty

EN

The following problem is shown undecidable: given regular languages L, K of finite trees, decide if there exists a deterministic tree-walking automaton which accepts all trees in L and rejects all trees in K. The proof uses a technique of Kopczyński from [1].

Słowa kluczowe

EN

machine theory; algorithms; computational geometry; Boolean functions; natural numbers

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 154, nr 1/4
• Strony: 37--46
• Opis fizyczny: Bibliogr. 10 poz., rys.

Twórcy

autor

Bojańczyk M.

• The University of Warsaw, Institute of Informatics, Banacha 2, 02-097 Warsaw, Poland

Bibliografia

• [1] Kopczyński E. Invisible Pushdown Languages. In: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS ’16, New York, NY, USA, July 5-8, 2016. 2016 pp. 867–872. doi:10.1145/2933575.2933579. URL http://doi.acm.org/10.1145/2933575.2933579.
• [2] Hinz F, Dassow J. A undecidability result for regular anguages and its applications to regulated rewriting. Bulletin of the EATCS, 1989;38:168–173. ISSN-0252-9742.
• [3] Place T, Zeitoun M. The Tale of the Quantifier Alternation Hierarchy of First-Order Logic over Words. SIGLOG Newsletter, 2015;2(3):4–17. doi:10.1145/2815493.2815495.
• [4] Thomas W. Logical Aspects in the Study of Tree Languages. In: CAAP’84, 9th Colloquium on Trees in Algebra and Programming, Bordeaux, France, March 5-7, 1984, Proceedings. 1984 pp. 31–50. ISBN:0-521-26750-1.
• [5] Muscholl A, Samuelides M, Segoufin L. Complementing deterministic tree-walking automata. Inf. Process. Lett., 2006;99(1):33–39. doi:10.1016/j.ipl.2005.09.017. URL http://dx.doi.org/10.1016/j.ipl.2005.09.017.
• [6] Szymanski TG, Williams JH. Noncanonical Extensions of Bottom-Up Parsing Techniques. SIAM J. Comput., 1976;5(2):231–250. doi:10.1137/0205019. URL http://dx.doi.org/10.1137/0205019.
• [7] Bojańczyk M, Colcombet T. Tree-walking automata cannot be determinized. Theor. Comput. Sci., 2006;350(2-3):164–173. doi:10.1016/j.tcs.2005.10.031. URL http://dx.doi.org/10.1016/j.tcs.2005.10.031.
• [8] Bojańczyk M. Tree-Walking Automata. In: Language and Automata Theory and Applications, Second International Conference, LATA 2008, Tarragona, Spain, March 13-19, 2008. Revised Papers. 2008 pp. 1–2. doi:10.1007/978-3-540-88282-4_1. URL http://dx.doi.org/10.1007/978-3-540-88282-4_1.
• [9] Goubault-Larrecq J, Schmitz S. Deciding Piecewise Testable Separability for Regular Tree Languages. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy. 2016 pp. 97:1–97:15. doi:10.4230/LIPIcs.ICALP.2016.97. URL http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.97.
• [10] Wilke T. An Algebraic Characterization of Frontier Testable Tree Languages. Theor. Comput. Sci., 1996;154(1):85–106. doi:10.1016/0304-3975(95)00131-X. URL http://dx.doi.org/10.1016/0304-3975(95)00131-X.