Informace o publikaci
Reversibility of computations in graph-walking automata
| Název česky | Reverzibilita výpočtů automatů chodících po grafech |
|---|---|
| Autoři | |
| Rok publikování | 2013 |
| Druh | Článek ve sborníku |
| Konference | Mathematical Foundations of Computer Science 2013 |
| Fakulta / Pracoviště MU | |
| 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. |