Reversibility of computations in graph-walking automata

Michal Kunc, Alexander Okhotin

Результат исследований: Научные публикации в периодических изданияхстатья


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.

Язык оригиналаанглийский
Номер статьи104631
ЖурналInformation and Computation
СостояниеОпубликовано - дек 2020

Предметные области Scopus

  • Теоретические компьютерные науки
  • Информационные системы
  • Прикладные компьютерные науки
  • Математика и теория расчета

Fingerprint Подробные сведения о темах исследования «Reversibility of computations in graph-walking automata». Вместе они формируют уникальный семантический отпечаток (fingerprint).