Reversibility of computations in graph-walking automata

Alexander Okhotin (University of Turku)

When: November 4, 2pm

Where: room G2.91b/G215

Abstract

Graph-walking automata are finite-state devices traversing graphs given as an input by following their edges; they have been studied both as a theoretical notion, and as a model of maze walking in robotics. In this talk, graph-walking automata are invested with another motivation: that of a general model for various kinds of deterministic machines traversing finite undirected structures, such as two-way finite automata, including their multi-head and multi-tape variants, tree-walking automata and their extension with pebbles, picture-walking automata, space-bounded Turing machines, etc. The talk begins with representing each of these devices as a particular type of graph-walking automata. The main question addressed in the talk is transforming an arbitrary deterministic graph-walking automaton to a *reversible* graph-walking automaton, in which every step of its computation is logically reversible. 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 covered by graph-walking automata, and, in particular, subsumes numerous existing results on making finite-memory devices halt on every input.

(joint work with M. Kunc)