A4 Refereed article in a conference publication
Reversibility of computations in graph-walking automata
Authors: Michal Kunc, Alexander Okhotin
Editors: Krishnendu Chatterjee, Jirí Sgall
Publication year: 2013
Journal: Lecture Notes in Computer Science
Book title : Mathematical Foundations of Computer Science
Series title: Lecture Notes in Computer Science
Volume: 8087
First page : 595
Last page: 606
Number of pages: 12
ISBN: 978-3-642-40312-5
eISBN: 978-3-642-40313-2
ISSN: 0302-9743
DOI: https://doi.org/10.1007/978-3-642-40313-2_53
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.
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.
UTU Research Portal