KIAM Main page Web Library  •  Publication Searh  Русский 

Article collection "Mathematical Problems of Cybernetics" №14, Moscow, 2005
Authors: Kilibarda G., Kudryavtsev V.B., Ušćumlić S.
Automata systems in labyrinths
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
Publication language: russian,  pages: 68 (p. 93-160)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text:
List of publications citation:
Export link to publication in format:   RIS    BibTeX
About authors:
  • Kilibarda Goran,  Университет Белграда
  • Kudryavtsev Valerii Borisovich,  ,  Механико-математический факультет МГУ, кафедра математической теории интеллектуальных систем
  • Ušćumlić Scepan,  Университет Белграда