Standard

Nondeterministic tree-walking automata are not closed under complementation. / Мартынова, Ольга Максимовна; Охотин, Александр Сергеевич.

52nd International Colloquium on Automata, Languages, and Programming. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2025. 168 (Leibniz International Proceedings in Informatics (LIPIcs); Том 334).

Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › Рецензирование

Harvard

Мартынова, ОМ & Охотин, АС 2025, Nondeterministic tree-walking automata are not closed under complementation. в 52nd International Colloquium on Automata, Languages, and Programming., 168, Leibniz International Proceedings in Informatics (LIPIcs), Том. 334, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 52nd International Colloquium on Automata, Languages, and Programming, Орхус, Дания, 8/07/25. https://doi.org/10.4230/LIPIcs.ICALP.2025.168

APA

Мартынова, О. М., & Охотин, А. С. (2025). Nondeterministic tree-walking automata are not closed under complementation. в 52nd International Colloquium on Automata, Languages, and Programming [168] (Leibniz International Proceedings in Informatics (LIPIcs); Том 334). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ICALP.2025.168

Vancouver

Мартынова ОМ, Охотин АС. Nondeterministic tree-walking automata are not closed under complementation. в 52nd International Colloquium on Automata, Languages, and Programming. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2025. 168. (Leibniz International Proceedings in Informatics (LIPIcs)). https://doi.org/10.4230/LIPIcs.ICALP.2025.168

Author

Мартынова, Ольга Максимовна ; Охотин, Александр Сергеевич. / Nondeterministic tree-walking automata are not closed under complementation. 52nd International Colloquium on Automata, Languages, and Programming. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2025. (Leibniz International Proceedings in Informatics (LIPIcs)).

BibTeX

@inproceedings{0951c97c3c804c87b0215e5fdff46e20,
title = "Nondeterministic tree-walking automata are not closed under complementation",
abstract = "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{\'n}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.",
keywords = "Finite automata, complementation, tree-walking automata",
author = "Мартынова, {Ольга Максимовна} and Охотин, {Александр Сергеевич}",
year = "2025",
month = jun,
day = "30",
doi = "10.4230/LIPIcs.ICALP.2025.168",
language = "English",
isbn = "9783959773720",
series = "Leibniz International Proceedings in Informatics (LIPIcs)",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
booktitle = "52nd International Colloquium on Automata, Languages, and Programming",
address = "Germany",
note = "null ; Conference date: 08-07-2025 Through 11-07-2025",
url = "https://conferences.au.dk/icalp2025",

}

RIS

TY - GEN

T1 - Nondeterministic tree-walking automata are not closed under complementation

AU - Мартынова, Ольга Максимовна

AU - Охотин, Александр Сергеевич

PY - 2025/6/30

Y1 - 2025/6/30

N2 - 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.

AB - 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.

KW - Finite automata

KW - complementation

KW - tree-walking automata

UR - https://www.mendeley.com/catalogue/6b425b3c-11d4-3de3-bbdd-1cc47c45e04e/

U2 - 10.4230/LIPIcs.ICALP.2025.168

DO - 10.4230/LIPIcs.ICALP.2025.168

M3 - Conference contribution

SN - 9783959773720

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

BT - 52nd International Colloquium on Automata, Languages, and Programming

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Y2 - 8 July 2025 through 11 July 2025

ER -

ID: 138292167