TY - GEN

T1 - Lower bounds for graph-walking automata

AU - Martynova, Olga

AU - Okhotin, Alexander

N1 - Publisher Copyright: © Olga Martynova and Alexander Okhotin; licensed under Creative Commons License CC-BY 4.0.

PY - 2021/3/1

Y1 - 2021/3/1

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

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

KW - Finite automata

KW - Graph-walking automata

KW - Halting

KW - Reversibility

KW - graph-walking automata

KW - halting

KW - reversibility

UR - http://www.scopus.com/inward/record.url?scp=85115201736&partnerID=8YFLogxK

UR - https://www.mendeley.com/catalogue/342571d3-f05f-321f-8e24-79b6a4715bd6/

U2 - 10.4230/LIPIcs.STACS.2021.52

DO - 10.4230/LIPIcs.STACS.2021.52

M3 - Conference contribution

AN - SCOPUS:85115201736

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021

A2 - Blaser, Markus

A2 - Monmege, Benjamin

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

T2 - 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021

Y2 - 16 March 2021 through 19 March 2021

ER -