Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Making Graph-Walking Automata ...

Making Graph-Walking Automata Reversible

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

Abstract:

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.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tKuOk12a,
  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