2026-07-28T08:11:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23545 2025-10-02T12:58:22Z ddc:004 open_access

Nondeterministic Tree-Walking Automata Are Not Closed Under Complementation Martynova, Olga Okhotin, Alexander Finite automata tree-walking automata complementation It is proved that the family of tree languages recognized by nondeterministic tree-walking automata is not closed under complementation, solving a problem raised by Bojańczyk and Colcombet (https://doi.org/10.1137/050645427, SIAM J. Comp. 38 (2008) 658-701). In addition, it is shown that nondeterministic tree-walking automata are stronger than unambiguous tree-walking automata. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Olga Martynova and Alexander Okhotin 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.168 urn:nbn:de:0030-drops-235459 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.168 eng https://creativecommons.org/licenses/by/4.0/legalcode