Where academic tradition
meets the exciting future

Making Graph-Walking Automata Reversible

Michal Kunc, Alexander Okhotin, Making Graph-Walking Automata Reversible. TUCS Technical Reports 1042, Turku Centre for Computer Science, 2012.


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.


Full publication in PDF-format

BibTeX entry:

  title = {Making Graph-Walking Automata Reversible},
  author = {Kunc, Michal and Okhotin, Alexander},
  number = {1042},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2012},
  keywords = {Graph-walking automata, tree-walking automata, finite automata, reversible computation, halting},
  ISBN = {978-952-12-2732-5},

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication