TY - JOUR

T1 - State complexity of transforming graph-walking automata to halting, returning and reversible

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

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

PY - 2023/3/1

Y1 - 2023/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 to accept, and to a reversible GWA. This paper establishes lower bounds on the state blow-up of these transformations, as well as improves the known upper bounds. It is shown that, for graphs with k labels of edge end-points, making an n-state GWA return to the initial node in the worst case requires at least 2(k−3)n and at most 2kn+n states. Similar asymptotically tight bounds are proved for transformations ensuring other properties: for halting on every input, at least 2(k−3)(n−1) and at most 2kn+1 states; for returning and halting, at least 2(k−3)(2n−1) and at most 4kn+1; for reversible, between 2(k−3)(n−1)−1 and 2kn+1; for returning and reversible, between 2(k−3)(2n−1)−1 and 4kn+1.

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 to accept, and to a reversible GWA. This paper establishes lower bounds on the state blow-up of these transformations, as well as improves the known upper bounds. It is shown that, for graphs with k labels of edge end-points, making an n-state GWA return to the initial node in the worst case requires at least 2(k−3)n and at most 2kn+n states. Similar asymptotically tight bounds are proved for transformations ensuring other properties: for halting on every input, at least 2(k−3)(n−1) and at most 2kn+1 states; for returning and halting, at least 2(k−3)(2n−1) and at most 4kn+1; for reversible, between 2(k−3)(n−1)−1 and 2kn+1; for returning and reversible, between 2(k−3)(2n−1)−1 and 4kn+1.

KW - Finite automata

KW - Graph-walking automata

KW - Halting

KW - Reversibility

UR - https://www.mendeley.com/catalogue/bb22dcdd-60de-3eb5-b6f3-bc346b8c5f83/

U2 - 10.1016/j.ic.2023.105011

DO - 10.1016/j.ic.2023.105011

M3 - Article

VL - 291

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

M1 - 105011

ER -