Research on automaton analysis of geometrical environments, images, graphs, formal languages and other discrete structures, has been on a rise for several past decades. On of the main problems for automata theory in this area is the labyrinth exit location. The major issues for automata in labyrinths group around the synthesis and analysis problems. The synthesis problem consists in describing the automata and automata systems that walk the labyrinths from a given class. The analysis problem consists in describing all labyrinths, or all labyrinths of a special kind, that are walked by given automaton or an automata system. The main model class is that of finite state automata in finite planar mosaic or infinite planar mosaic labyrinths. The present article develops the ideas of the authors' previous work dating back to 1992. It reflects both the new results and the improvements in earlier considered situations. The first two parts outline the main concepts of the research domain and the results stated further. The last part considers in detail the case of independent automata systems in the aforementioned classes of labyrinths and some of their generalizations.

automata theory, graph theory, hypergraph, automata system, labyrinth exit location

Mathematical problems and theory of numerical methods