Reversibility of computations in graph-walking automata

J 2020

Reversibility of computations in graph-walking automata

KUNC, Michal a Alexander OKHOTIN

Základní údaje

Originální název

Reversibility of computations in graph-walking automata

Autoři

KUNC, Michal a Alexander OKHOTIN

Vydání

Information and computation, San Diego, Academic Press Inc Elsevier Science, 2020, 0890-5401

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10101 Pure mathematics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Impakt faktor

Impact factor: 0.704

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14310/20:00114625

Organizační jednotka

Přírodovědecká fakulta

Klíčová slova anglicky

Graph-walking automata; Tree-walking automata; Finite automata; Reversible computation; Halting

Štítky

14311010, rivok

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 7. 1. 2021 09:28, Mgr. Marie Novosadová Šípková, DiS.

Anotace

V originále

Graph-walking automata (GWA) are finite-state devices that traverse graphs given as an input by following their edges; they have been studied both as a theoretical notion and as a model of pathfinding in robotics. If a graph is regarded as the set of memory configurations of a certain abstract machine, then various families of devices can be described as GWA: such are two-way finite automata, their multi-head and multi-tape variants, tree-walking automata and their extension with pebbles, picture-walking automata, space-bounded Turing machines, etc. This paper defines a transformation of an arbitrary deterministic GWA to a reversible GWA. This is done with a linear blow-up in the number of states, where the constant factor depends on the degree of the graphs being traversed. The construction directly applies to all basic models representable as GWA, and, in particular, subsumes numerous existing results for making individual models halt on every input. (C) 2020 Elsevier Inc. All rights reserved.

Návaznosti

GBP202/12/G061, projekt VaV

Název: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Akronym: CE-ITI)

Investor: Grantová agentura ČR, Centrum excelence - Institut teoretické informatiky

Citovat

KUNC, Michal a Alexander OKHOTIN. Reversibility of computations in graph-walking automata. Information and computation. San Diego: Academic Press Inc Elsevier Science, 2020, roč. 275, December 2020, s. 1-32. ISSN 0890-5401. Dostupné z: https://doi.org/10.1016/j.ic.2020.104631.

@article{1721079,
   author = {Kunc, Michal and Okhotin, Alexander},
   article_location = {San Diego},
   article_number = {December 2020},
   doi = {https://doi.org/10.1016/j.ic.2020.104631},
   keywords = {Graph-walking automata; Tree-walking automata; Finite automata; Reversible computation; Halting},
   language = {eng},
   issn = {0890-5401},
   journal = {Information and computation},
   title = {Reversibility of computations in graph-walking automata},
   url = {https://doi.org/10.1016/j.ic.2020.104631},
   volume = {275},
   year = {2020}
}

TY  - JOUR
ID  - 1721079
AU  - Kunc, Michal - Okhotin, Alexander
PY  - 2020
TI  - Reversibility of computations in graph-walking automata
JF  - Information and computation
VL  - 275
IS  - December 2020
SP  - 1-32
EP  - 1-32
PB  - Academic Press Inc Elsevier Science
SN  - 08905401
KW  - Graph-walking automata
KW  - Tree-walking automata
KW  - Finite automata
KW  - Reversible computation
KW  - Halting
UR  - https://doi.org/10.1016/j.ic.2020.104631
L2  - https://doi.org/10.1016/j.ic.2020.104631
N2  - Graph-walking automata (GWA) are finite-state devices that traverse graphs given as an input by following their edges; they have been studied both as a theoretical notion and as a model of pathfinding in robotics. If a graph is regarded as the set of memory configurations of a certain abstract machine, then various families of devices can be described as GWA: such are two-way finite automata, their multi-head and multi-tape variants, tree-walking automata and their extension with pebbles, picture-walking automata, space-bounded Turing machines, etc. This paper defines a transformation of an arbitrary deterministic GWA to a reversible GWA. This is done with a linear blow-up in the number of states, where the constant factor depends on the degree of the graphs being traversed. The construction directly applies to all basic models representable as GWA, and, in particular, subsumes numerous existing results for making individual models halt on every input. (C) 2020 Elsevier Inc. All rights reserved.
ER  -

KUNC, Michal a Alexander OKHOTIN. Reversibility of computations in graph-walking automata. \textit{Information and computation}. San Diego: Academic Press Inc Elsevier Science, 2020, roč.~275, December 2020, s.~1-32. ISSN~0890-5401. Dostupné z: https://doi.org/10.1016/j.ic.2020.104631.

Přehled o publikaci