2013
Reversibility of computations in graph-walking automata
KUNC, Michal a Alexander OKHOTINZákladní údaje
Originální název
Reversibility of computations in graph-walking automata
Název česky
Reverzibilita výpočtů automatů chodících po grafech
Autoři
KUNC, Michal a Alexander OKHOTIN
Vydání
Berlin, Mathematical Foundations of Computer Science 2013, od s. 595-606, 12 s. 2013
Nakladatel
Springer
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10101 Pure mathematics
Stát vydavatele
Německo
Utajení
není předmětem státního či obchodního tajemství
Forma vydání
tištěná verze "print"
Odkazy
Impakt faktor
Impact factor: 0.402 v roce 2005
Kód RIV
RIV/00216224:14310/13:00069382
Organizační jednotka
Přírodovědecká fakulta
ISBN
978-3-642-40312-5
ISSN
UT WoS
000342994500053
Klíčová slova česky
automat chodící po grafech; reverzibilní výpočet
Klíčová slova anglicky
graph-walking automaton; reversible computation
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 20. 9. 2013 13:13, doc. Mgr. Michal Kunc, Ph.D.
V originále
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.
Česky
Č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.
Návaznosti
| EE2.3.20.0051, projekt VaV |
|