On Reduction of Automata in Labyrinths


Goran Kilibarda




It is shown that every automaton acceptable for rectangular labyrinths can be reduced to an automaton that behaves according to either the left-hand rule or the right-hand rule, or does not move at all, in every plane rectangular labyrinth without leaves. This enables us to approach certain fundamental problems of the theory of automata in labyrinths in quite a different way.