Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Lower bounds for graph-walking automata. / Martynova, Olga; Okhotin, Alexander.
38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021. ed. / Markus Blaser; Benjamin Monmege. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021. 52 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 187).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
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 -
ID: 85901002