A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
Reversibility of computations in graph-walking automata
Tekijät: Michal Kunc, Alexander Okhotin
Toimittaja: Krishnendu Chatterjee, Jirí Sgall
Julkaisuvuosi: 2013
Journal: Lecture Notes in Computer Science
Kokoomateoksen nimi: Mathematical Foundations of Computer Science
Sarjan nimi: Lecture Notes in Computer Science
Vuosikerta: 8087
Aloitussivu: 595
Lopetussivu: 606
Sivujen määrä: 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
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali