Czasopismo
2017
|
Vol. 154, nr 1/4
|
37--46
Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Warianty tytułu
Języki publikacji
Abstrakty
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].
Czasopismo
Rocznik
Tom
Strony
37--46
Opis fizyczny
Bibliogr. 10 poz., rys.
Twórcy
autor
- The University of Warsaw, Institute of Informatics, Banacha 2, 02-097 Warsaw, Poland, bojan@mimuw.edu.pl
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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-ef89a1b4-e9cd-40dc-9884-1cf4be77eaf0