Reversibility of computations in graph-walking automata

: Michal Kunc, Alexander Okhotin

: Krishnendu Chatterjee, Jirí Sgall

: 2013

: Lecture Notes in Computer Science

: Mathematical Foundations of Computer Science

: Lecture Notes in Computer Science

: 8087

: 595

: 606

: 12

: 978-3-642-40312-5

: 978-3-642-40313-2

: 0302-9743

DOI: https://doi.org/10.1007/978-3-642-40313-2_53

The paper proposes a general notation for deterministic automata traversing finite undirected structures: the graph-walking automata. This abstract notion covers such models as two-way finite automata, including their multi-tape and multi-head variants, tree-walking automata and their extension with pebbles, picture-walking automata, space-bounded Turing machines, etc. It is then demonstrated that every graph-walking automaton can be transformed to an equivalent reversible graph-walking automaton, so that every step of its computation is logically reversible. This is done with a linear blow-up in the number of states, where the linear factor depends on the degree of graphs being traversed. The construction directly applies to all basic models covered by this abstract notion.