TY - JOUR

T1 - Reversibility of computations in graph-walking automata

AU - Kunc, Michal

AU - Okhotin, Alexander

N1 - Funding Information: This research was supported by the research center Institute for Theoretical Computer Science (ITI), project No. P202/12/G061 of the Czech Science Foundation . Publisher Copyright: © 2020 Elsevier Inc. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020/12

Y1 - 2020/12

N2 - Graph-walking automata (GWA) are finite-state devices that traverse graphs given as an input by following their edges; they have been studied both as a theoretical notion and as a model of pathfinding in robotics. If a graph is regarded as the set of memory configurations of a certain abstract machine, then various families of devices can be described as GWA: such are two-way finite automata, their multi-head and multi-tape variants, tree-walking automata and their extension with pebbles, picture-walking automata, space-bounded Turing machines, etc. This paper defines a transformation of an arbitrary deterministic GWA to a reversible GWA. This is done with a linear blow-up in the number of states, where the constant factor depends on the degree of the graphs being traversed. The construction directly applies to all basic models representable as GWA, and, in particular, subsumes numerous existing results for making individual models halt on every input.

AB - Graph-walking automata (GWA) are finite-state devices that traverse graphs given as an input by following their edges; they have been studied both as a theoretical notion and as a model of pathfinding in robotics. If a graph is regarded as the set of memory configurations of a certain abstract machine, then various families of devices can be described as GWA: such are two-way finite automata, their multi-head and multi-tape variants, tree-walking automata and their extension with pebbles, picture-walking automata, space-bounded Turing machines, etc. This paper defines a transformation of an arbitrary deterministic GWA to a reversible GWA. This is done with a linear blow-up in the number of states, where the constant factor depends on the degree of the graphs being traversed. The construction directly applies to all basic models representable as GWA, and, in particular, subsumes numerous existing results for making individual models halt on every input.

KW - Finite automata

KW - Graph-walking automata

KW - Halting

KW - Reversible computation

KW - Tree-walking automata

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

UR - https://www.mendeley.com/catalogue/5f88129a-1d81-3b05-acf7-a00c7a0af0d4/

U2 - 10.1016/j.ic.2020.104631

DO - 10.1016/j.ic.2020.104631

M3 - Article

AN - SCOPUS:85092724813

VL - 275

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

M1 - 104631

ER -