DOI

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 (“Tree-walking automata do not recognize all regular languages”, SIAM J. Comp. 38 (2008) 658-701). In addition, it is shown that nondeterministic tree-walking automata are stronger than unambiguous tree-walking automata.
Original languageEnglish
Title of host publication52nd International Colloquium on Automata, Languages, and Programming
PublisherDagstuhl Publishing
Number of pages17
ISBN (Print)9783959773720
DOIs
StatePublished - 30 Jun 2025
Event52nd International Colloquium on Automata, Languages, and Programming - Орхус, Denmark
Duration: 8 Jul 2025 → 11 Jul 2025
https://conferences.au.dk/icalp2025

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
Volume334

Conference

Conference52nd International Colloquium on Automata, Languages, and Programming
Abbreviated titleICALP 2025
Country/TerritoryDenmark
CityОрхус
Period8/07/25 → 11/07/25
Internet address

    Research areas

  • Finite automata, complementation, tree-walking automata

ID: 138292167