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 -