License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2021.52
URN: urn:nbn:de:0030-drops-136974
URL: https://drops.dagstuhl.de/opus/volltexte/2021/13697/
Go to the corresponding LIPIcs Volume Portal

Martynova, Olga ; Okhotin, Alexander

Lower Bounds for Graph-Walking Automata

pdf-format:
LIPIcs-STACS-2021-52.pdf (0.9 MB)

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.

BibTeX - Entry

@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/opus/volltexte/2021/13697},
  URN =		{urn:nbn:de:0030-drops-136974},
  doi =		{10.4230/LIPIcs.STACS.2021.52},
  annote =	{Keywords: Finite automata, graph-walking automata, halting, reversibility}
}

Keywords: Finite automata, graph-walking automata, halting, reversibility
Collection: 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Issue Date: 2021
Date of publication: 10.03.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI