Beijing-Saint Petersburg Mathematics Colloquium (online)
Abstract
Graph-walking automata are a model studied in theoretical computer science: they traverse an undirected graph by following its edges, and use a memory of constant size to plan their movements. Graph-walking automata can be regarded both as a model of a robot navigating an unknown environment, and as a generic model of computation, with the graph modelling its memory. This paper presents the known results on these automata, ranging from their limitations in traversing graphs, studied already in the 1970s, to the later work on the logical reversibility of their computations, including the most recent lower bounds on their size.
Bio
Alexander Okhotin (Ph.D. 2004, Queen's University) is a professor of theoretical computer science at St. Petersburg State University. His main research subjects are formal grammars, finite automata and their complexity.
