Reversibility of computations in graph-walking automata

Název česky Reverzibilita výpočtů automatů chodících po grafech
Autoři

KUNC Michal OKHOTIN Alexander

Druh Článek ve sborníku
Konference Mathematical Foundations of Computer Science 2013
Fakulta / Pracoviště MU

Přírodovědecká fakulta

Citace
WWW http://dx.doi.org/10.1007/978-3-642-40313-2_53
Doi http://dx.doi.org/10.1007/978-3-642-40313-2_53
Obor Obecná matematika
Klíčová slova graph-walking automaton; reversible computation
Popis Č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.

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.