Reversibility of computations in graph-walking automata

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14310%2F20%3A00114625" target="_blank" >RIV/00216224:14310/20:00114625 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1016/j.ic.2020.104631" target="_blank" >https://doi.org/10.1016/j.ic.2020.104631</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.ic.2020.104631" target="_blank" >10.1016/j.ic.2020.104631</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Reversibility of computations in graph-walking automata

Popis výsledku v původním jazyce

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ázev v anglickém jazyce

Reversibility of computations in graph-walking automata

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2020

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Information and computation

ISSN

0890-5401

e-ISSN

1090-2651

Svazek periodika

275

Číslo periodika v rámci svazku

December 2020

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

32

Strana od-do

1-32

Kód UT WoS článku

000595367200029

EID výsledku v databázi Scopus

2-s2.0-85092724813