On the Directional Movement of a Graph-Walking Automaton without a Compass on Square Grid Graph

Abstract

This paper deals with the problem of organizing a directional movement of a finite automaton without a compass on vertex-labeled square grid graph. A minimal number of classes of vertex labels is found that is necessary and sufficient for the automaton to maintain movement direction on the graph. Algorithms for constructing minimal vertex-labeling for finite and infinite grids are developed.