Behavior of finite automata in mazes

The paper is devoted to the study of problems on the behavior of finite automata in mazes. For any n, a maze is constructed that can be bypassed with 2n stones but you can’t get around with n stones. The range of tasks is extensive and touches upon key aspects of theoretical Computer Science. Of course, the solution of such problems does not mean the automatic solution of complex problems of complexity theory, however, the consideration of these issues can have a positive impact on the understanding of the essence of theoretical Computer Science. It is hoped that the behavior of automata in mazes is a good model for non-trivial information theoretic problems, and the development of methods and approaches to the study of robot behavior will give more serious results in the future. Problems related to automaton analysis of geometric media have a rather rich history of study. The first work that gave rise to this kind of problems, it is necessary to recognize the work of Shannon [24]. It deals with a model of a mouse in the form of an automaton, which must find a specific target in the maze. Another early work, one way or another affecting our problems, is the work of Fisher [9] on computing systems with external memory in the form of a discrete plane. A serious impetus to the study of the behavior of automata in mazes was the work of Depp [7, 8], in which the following model is proposed: there is a certain configuration of cells from mathbbZ^2 (chess maze), in which finite automata, surveying some neighborhood of the cell in which they are, can move to an adjacent cell in one of four directions. The main question posed in such a model is whether there is an automaton that bypasses all such mazes. In [20], Muller constructed a flat trap for a given automaton (a maze that does not completely bypass) in the form of a 3-graph. Budach [5] constructed a chess trap for any given finite automaton. Note that Budach’s solution was quite complex (the first versions contained 175 pages). More visual solutions to this question are presented here [29, 31, 33, 34]. Antelman [2] estimated the complexity of such a trap by the number of cells, and in [1] Antelman, Budach, and Rollick made a finite trap for any finite automaton system. In the formulation with a chess maze and one automaton, there are a number of results related to the problems of traversability of labyrinths with different numbers of holes, with bundles of labyrinths by the number of States of the automaton, and other issues. An overview of such problems can be found for example here [35]. The impossibility of traversing all flat chess labyrinths with one automaton raised the question of studying the possible amplifications of the automaton model, which will solve the problem of traversal. The main way of strengthening can be the consideration of a collective of automata, instead of one automaton, interacting with each other. A special and widely used case is the consideration of a system of one full-fledged automaton and a certain number of automata of stones, which have no internal state and can move only together with the main automaton. Interaction between machines is a key feature of this gain, it is allowed to have a collective (or one machine with stones) external memory, thereby significantly diversifies its behavior. If you get rid of the interaction of automata, the resulting  independent system will be little better than a single machine. Next, we discuss the known results associated with the collective automata.

maze traversal, finite state machine

1. Antelmann H., Budach L., Rollik H. A. On universale traps // EIK. 1979. Vol. 15. No. 3. Pp. 123–131.

2. Antelmann H. An application of the prime number theorem in automata theory // ICS PAS Reports 411. 1980. Pp. 9–11.

3. Blum M., Kozen D. On the power of the compass // Proc. 19th IEEE FOCS Conf. 1978. Pp. 132–142.

4. Blum M., Sakoda W. On the capability of finite automata in 2 and 3 dimensional space // Proc. 17th IEEE FOCS Conf. 1977. Pp. 147–161.

5. Budach L. Automata and labyrinths // Math. Nachrichten 86. 1978. Pp. 195–282.

6. Burnside W., “On an unsettled question in the theory of discontinuous groups” // Quart. J. Pure Appl. Math., 1902, 33, 230–238.

7. Dopp K. Automaten in Labyrinthen I // EIK. 1971. Vol. 7. No. 2. Pp. 79–94.

8. Dopp K. Automaten in Labyrinthen II // EIK. 1971. Vol. 7. No. 3. Pp. 167–190.

9. Fischer P. C. Multi-tape and infinite-state automata: A survey // Comm. ACM. 1965. Vol. 8. No. 12. Pp. 799–805.

10. Habasinski Z., Karpinski M. A codification of Blum-Sakoda 7-pebbles algorithm // ICS PAS Reports 448. Warszawa, 1981.

11. Hall M. jun., “Solution of the Burnside problem for exponentsix” // Illinois J. Math., 1958, 2, 764–786.

12. Hemmerling A. 1-pointer automata searching finite plane graphs // Z. Math. Logik Grundlag. Math. 1986. Vol. 32. Pp. 245–256.

13. Hemmerling A. Normed two-plane traps for finite systems of cooperating compass automata // J. Inf. Process. Cybern. EIK 1987. Vol. 28. No. 8/9. Pp. 453–470.

14. Hoffmann F. One pebble does not suffice to search plane labyrinths // Lecture Notes in Computer Science. 1981. Vol. 117. Pp. 433–444.

15. Hoffman F. 1-Kiesel-Automaten in Labyrinthen // Report R-Math-06/82. AdW der DDR, Berlin, 1982.

16. Ivanov S. On the Burnside problem on periodic groups // Bull. Amer. Math. Soc. (N. S.), 27:2 (1992), 257–260; arXiv: math/9210221.

17. Kilibarda G. On the minimum universal collectives of automata for plane labyrinths // Discrete Math. Appl. 1993. Vol. 3. No. 6. Pp. 555–586.

18. Kriegel K. Universelle 1-Kiesel-Automaten fur k-komponentige Labyrinthe // Report R-Math-04/84. AdW der DDR, Berlin, 1984.

19. Minsky M. Computation: Finite and Infinite Machines (1st ed.). Englewood Cliffs, N. J.: Prentice-Hall, Inc, 1967.

20. Muler ? H. Endliche Automaten und Labyrinthen // EIK. 1971. Vol. 7. No. 4. Pp. 261–264.

21. Rollik H. A. Automaten in planaren Graphen // Acta Informatica. 1980. Vol. 13. Pp. 287–298.

22. Savitch W. Relations between nondeterministic and deterministic tape complexities // Journal of Computer and System Science. 1970. Vol. 4. Pp. 177–192.

23. Savitch W. Maze recognizing automata and nondeterministic tape complexity // Journal of Computer and System Science. 1973. Vol. 7. Pp. 389–403.

24. Shannon Cl. E. Presentation of a maze-solving machine // Cybernetics Trans. of the 8th Conf. of the Josiah Macy Jr. Found / Editor: H. Forester. 1951. Pp. 173–180.

25. Szepietowski A. A finite 5-pebble-automaton can search every maze // Information Processing Letters. 1982. Vol. 15. No. 5. Pp. 199–204.

26. Aдян С. И. Проблема Бернсайда и тождества в группах. М.: Наука, 1975.

27. Анджанс А. В. Поведение детерминированных и вероятностных автоматов в лабиринтах: Дис. ... канд. физ.-мат. наук. Рига, 1987. 90 с.

28. Голод Е. С. О ниль-алгебрах в финитно-аппроксимируемых группах // Изв. АН СССР. Сер. матем., 1964, 28(2), 273–276.

29. Килибарда Г. Об универсальных лабиринтах-ловушках для конечных множеств автоматов // Дискретная математика. 1990. Т. 2. Вып. 1. С. 72–79.

30. Килибарда Г. О минимальных универсальных коллективах автоматов для плоских лабиринтов // Дискретная математика. 1994. Т. 6. Вып. 4. C. 133–153.

31. Килибарда Г. Новое доказательство теоремы Будаха-Подколзина //

32. Килибарда Г., Ушчумлич Ш. О лабиринтах-ловушках для коллективов автоматов // Дискретная математика. 1993. Т. 5. Вып. 2. C. 29–50.

33. Кудрявцев В. Б., Подколзин А. С, Ушчумлич Ш. Введение в теорию абстрактных автоматов. М.: Изд-во МГУ, 1985.

34. Кудрявцев В. Б., Алешин С. В., Подколзин А. С. Введение в теорию автоматов. М.: Наука, 1985.

35. Кудрявцев Г. Килибарда Ш. Ушчумлич Системы автоматов в лабиринтах. Грант РФФИ № 06-01-00240.

36. Новиков П. С., Адян С. И. О бесконечных периодических группах. I, II, III // Изв. АН СССР. Сер. матем., 1968, 32(1), 212–244; 32(2), 251–524; 32(3), 709–731.

37. Санов И. Н. Решение проблемы Бернсайда для показателя 4 // Ученые записки ЛГУ. Сер. матем., 1940, 10, 166–170.

38. Xарари Ф. Теория графов. М.: Мир, 1973