Nondeterministic tree-walking automata are not closed under complementation › Научные исследования в СПбГУ

DOI

https://doi.org/10.4230/LIPIcs.ICALP.2025.168
Конечная издательская версия

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.

Язык оригинала	английский
Название основной публикации	52nd International Colloquium on Automata, Languages, and Programming
Издатель	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Число страниц	17
ISBN (печатное издание)	9783959773720
DOI	https://doi.org/10.4230/LIPIcs.ICALP.2025.168
Состояние	Опубликовано - 30 июн 2025
Событие	52nd International Colloquium on Automata, Languages, and Programming - Орхус, Дания Продолжительность: 8 июл 2025 → 11 июл 2025 https://conferences.au.dk/icalp2025

Серия публикаций

Название	Leibniz International Proceedings in Informatics (LIPIcs)
Том	334

конференция

конференция	52nd International Colloquium on Automata, Languages, and Programming
Сокращенное название	ICALP 2025
Страна/Tерритория	Дания
Город	Орхус
Период	8/07/25 → 11/07/25
Сайт в сети Internet	https://conferences.au.dk/icalp2025

ID: 138292167