Reversibility of computations in graph-walking automata

Michal Kunc, Alexander Okhotin

Research outputpeer-review

10 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Proceedings
Pages595-606
Number of pages12
DOIs
Publication statusPublished - 15 Oct 2013
Event38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013 - Klosterneuburg
Duration: 26 Aug 201330 Aug 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8087 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013
CountryAustria
CityKlosterneuburg
Period26/08/1330/08/13

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Reversibility of computations in graph-walking automata'. Together they form a unique fingerprint.

Cite this