DROPS

Document

Track B: Automata, Logic, Semantics, and Theory of Programming

DOI: 10.4230/LIPIcs.ICALP.2025.168

Nondeterministic Tree-Walking Automata Are Not Closed Under Complementation

Authors: Olga Martynova and Alexander Okhotin

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

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

Cite as

Olga Martynova and Alexander Okhotin. Nondeterministic Tree-Walking Automata Are Not Closed Under Complementation. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 168:1-168:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{martynova_et_al:LIPIcs.ICALP.2025.168,
  author =	{Martynova, Olga and Okhotin, Alexander},
  title =	{{Nondeterministic Tree-Walking Automata Are Not Closed Under Complementation}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{168:1--168:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.168},
  URN =		{urn:nbn:de:0030-drops-235459},
  doi =		{10.4230/LIPIcs.ICALP.2025.168},
  annote =	{Keywords: Finite automata, tree-walking automata, complementation}
}

Document

DOI: 10.4230/LIPIcs.STACS.2021.52

Lower Bounds for Graph-Walking Automata

Authors: Olga Martynova and Alexander Okhotin

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract

Graph-walking automata (GWA) traverse graphs by moving between the nodes following the edges, using a finite-state control to decide where to go next. It is known that every GWA can be transformed to a GWA that halts on every input, to a GWA returning to the initial node in order to accept, as well as to a reversible GWA. This paper establishes lower bounds on the state blow-up of these transformations: it is shown that making an n-state GWA traversing k-ary graphs return to the initial node requires at least 2(n-1)(k-3) states in the worst case; the same lower bound holds for the transformation to halting automata. Automata satisfying both properties at once must have at least 4(n-1)(k-3) states. A reversible automaton must have at least 4(n-1)(k-3)-1 states. These bounds are asymptotically tight to the upper bounds proved using the methods from the literature.

Cite as

Olga Martynova and Alexander Okhotin. Lower Bounds for Graph-Walking Automata. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 52:1-52:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{martynova_et_al:LIPIcs.STACS.2021.52,
  author =	{Martynova, Olga and Okhotin, Alexander},
  title =	{{Lower Bounds for Graph-Walking Automata}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{52:1--52:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.52},
  URN =		{urn:nbn:de:0030-drops-136974},
  doi =		{10.4230/LIPIcs.STACS.2021.52},
  annote =	{Keywords: Finite automata, graph-walking automata, halting, reversibility}
}

Search Results

Documents authored by Martynova, Olga

Nondeterministic Tree-Walking Automata Are Not Closed Under Complementation

Abstract

Cite as

Lower Bounds for Graph-Walking Automata

Abstract

Cite as

Thanks for your feedback!

Could not send message