TY - GEN

T1 - Reversibility of computations in graph-walking automata

AU - Kunc, Michal

AU - Okhotin, Alexander

PY - 2013/10/15

Y1 - 2013/10/15

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84885234011&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-40313-2_53

DO - 10.1007/978-3-642-40313-2_53

M3 - Conference contribution

AN - SCOPUS:84885234011

SN - 9783642403125

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 595

EP - 606

BT - Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Proceedings

T2 - 38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013

Y2 - 26 August 2013 through 30 August 2013

ER -