Nondeterministic tree-walking automata are not closed under complementation

DOI

https://doi.org/10.4230/LIPIcs.ICALP.2025.168
Final published version

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 language	English
Title of host publication	52nd International Colloquium on Automata, Languages, and Programming
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Number of pages	17
ISBN (Print)	9783959773720
DOIs	https://doi.org/10.4230/LIPIcs.ICALP.2025.168
State	Published - 30 Jun 2025
Event	52nd International Colloquium on Automata, Languages, and Programming - Орхус, Denmark Duration: 8 Jul 2025 → 11 Jul 2025 https://conferences.au.dk/icalp2025

Publication series

Name	Leibniz International Proceedings in Informatics (LIPIcs)
Volume	334

Conference

Conference	52nd International Colloquium on Automata, Languages, and Programming
Abbreviated title	ICALP 2025
Country/Territory	Denmark
City	Орхус
Period	8/07/25 → 11/07/25
Internet address	https://conferences.au.dk/icalp2025

Research areas

Finite automata, complementation, tree-walking automata

ID: 138292167