Publication details

Reversibility of computations in graph-walking automata


KUNC Michal OKHOTIN Alexander

Year of publication 2013
Type Article in Proceedings
Conference Mathematical Foundations of Computer Science 2013
MU Faculty or unit

Faculty of Science

Field General mathematics
Keywords graph-walking automaton; reversible computation
Description 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.

You are running an old browser version. We recommend updating your browser to its latest version.

More info