Reversibility of computations in graph-walking automata

KUNC, Michal and Alexander OKHOTIN. Reversibility of computations in graph-walking automata. In Krishnendu Chatterjee, Jirí Sgall. Mathematical Foundations of Computer Science 2013. Berlin: Springer, 2013, p. 595-606. ISBN 978-3-642-40312-5. Available from: https://dx.doi.org/10.1007/978-3-642-40313-2_53.

Basic information

• Original name: Reversibility of computations in graph-walking automata
• Name in Czech: Reverzibilita výpočtů automatů chodících po grafech
• Authors: KUNC, Michal (203 Czech Republic, guarantor, belonging to the institution) and Alexander OKHOTIN (643 Russian Federation).
• Edition: Berlin, Mathematical Foundations of Computer Science 2013, p. 595-606, 12 pp. 2013.
• Publisher: Springer

Other information

• Original language: English
• Type of outcome: Proceedings paper
• Field of Study: 10101 Pure mathematics
• Country of publisher: Germany
• Confidentiality degree: is not subject to a state or trade secret
• Publication form: printed version "print"
• WWW: URL
• Impact factor: Impact factor: 0.402 in 2005
• RIV identification code: RIV/00216224:14310/13:00069382
• Organization unit: Faculty of Science
• ISBN: 978-3-642-40312-5
• ISSN: 0302-9743
• Doi: http://dx.doi.org/10.1007/978-3-642-40313-2_53
• UT WoS: 000342994500053
• Keywords (in Czech): automat chodící po grafech; reverzibilní výpočet
• Keywords in English: graph-walking automaton; reversible computation
• Tags: International impact, Reviewed

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.

Abstract (in Czech)

Článek zavádí obecnou notaci pro deterministické automaty procházející konečnými neorientovanými strukturami: automaty chodící po grafech. Tento abstraktní pojem v sobě zahrnuje takové modely jako dvoucestné konečné automaty, včetně jejich vícepáskových a vícehlavových variant, automaty chodící po stromech a jejich rozšíření s kameny, automaty chodící po obrázcích, prostorově omezené Turingovy stroje, atd. Poté je ukázáno, že každý automat chodící po grafech je možné transformovat na ekvivalentní reverzibilní automat, v němž je každý krok výpočtu logicky vratný. Toho je dosaženo s lineárním nárůstem počtu stavů, přičemž lineární faktor závisí na stupni procházených grafů. Tuto konstrukci lze přímo aplikovat na všechny základní modely zahrnuté v tomto abstraktním pojmu.

Links

• EE2.3.20.0051, research and development project: Name: Algebraické metody v kvantové logice