Research output: Contribution to journal › Article › peer-review
Reversibility of computations in graph-walking automata. / Kunc, Michal; Okhotin, Alexander.
In: Information and Computation, Vol. 275, 104631, 12.2020.Research output: Contribution to journal › Article › peer-review
}
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 -
ID: 72034393