Behavior of finite automata in mazes

D. V. Gusev

Čebyševskij sbornik, Tome 20 (2019) no. 3, pp. 165-192.

Résumé

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 $\mathbb{Z}^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.

Détail

Keywords: maze traversal, finite state machine.

Bibliographie

[1] Antelmann H., Budach L., Rollik H. A. On universale traps, EIK, 15:3 (1979), 123–131 | MR | Zbl

[2] Antelmann H., An application of the prime number theorem in automata theory, ICS PAS Reports, No 411, 1980, 9–11

[3] Blum M., Kozen D., “On the power of the compass”, Proc. 19th IEEE FOCS Conf., 1978, 132–142 | MR

[4] Blum M., Sakoda W., “On the capability of finite automata in 2 and 3 dimensional space”, Proc. 17th IEEE FOCS Conf., 1977, 147–161 | MR

[5] Budach L., “Automata and labyrinths”, Math. Nachrichten, 86 (1978), 195–282 | MR | Zbl

[6] Burnside W., “On an unsettled question in the theory of discontinuous groups"”, Quart. J. Pure Appl. Math., 33 (1902), 230–238 | Zbl

[7] Dopp K., “Automaten in Labyrinthen I”, EIK, 7:2 (1971), 79–94 | MR | Zbl

[8] Dopp K., “Automaten in Labyrinthen II”, EIK, 7:3 (1971), 167–190 | MR

[9] Fischer P. C., “Multi-tape and infinite-state automata: A survey”, Comm. ACM, 8:12 (1965), 799–805 | Zbl

[10] Habasinski Z., Karpinski M., A codification of Blum-Sakoda 7-pebbles algorithm, ICS PAS Reports No 448, Warszawa, 1981 | Zbl

[11] Hall M. jun., “Solution of the Burnside problem for exponentsix"”, Illinois J. Math., 2 (1958), 764–786 | MR | Zbl

[12] Hemmerling A., “1-pointer automata searching finite plane graphs”, Z. Math. Logik Grundlag. Math., 32 (1986), 245–256 | MR | Zbl

[13] Hemmerling A., “Normed two-plane traps for finite systems of cooperating compass automata”, J. Inf. Process. Cybern. EIK, 28:8/9 (1987), 453–470 | MR

[14] Hoffmann F., “One pebble does not suffice to search plane labyrinths”, Lecture Notes in Computer Science, 117, 1981, 433–444 | MR | Zbl

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

[16] Ivanov S., “On the Burnside problem on periodic groups”, Bull. Amer. Math. Soc. (N. S.), 27:2 (1992), 257–260, arXiv: math/9210221 | MR | Zbl

[17] Kilibarda G., “On the minimum universal collectives of automata for plane labyrinths”, Discrete Math. Appl., 3:6 (1993), 555–586 | MR | Zbl

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

[19] Minsky M., Computation: Finite and Infinite Machines, 1st ed., Prentice-Hall, Inc, Englewood Cliffs, N. J., 1967 | MR | Zbl

[20] Muler H., “Endliche Automaten und Labyrinthen”, EIK, 7:4 (1971), 261–264 | MR

[21] Rollik H. A., “Automaten in planaren Graphen”, Acta Informatica, 13 (1980), 287–298 | MR | Zbl

[22] Savitch W., “Relations between nondeterministic and deterministic tape complexities”, Journal of Computer and System Science, 4 (1970), 177–192 | MR | Zbl

[23] Savitch W., “Maze recognizing automata and nondeterministic tape complexity”, Journal of Computer and System Science, 7 (1973), 389–403 | MR | Zbl

[24] Shannon Cl. E., “Presentation of a maze-solving machine”, Cybernetics, Trans. of the 8th Conf. of the Josiah Macy Jr. Found, ed. H. Forester, 1951, 173–180

[25] Szepietowski A., “A finite 5-pebble-automaton can search every maze”, Information Processing Letters, 15:5 (1982), 199–204 | MR | Zbl

[26] Adyan S. I., Problema Bernsaida i tozhdestva v gruppakh, Nauka, M., 1975

[27] Andzhans A. V., Povedenie determinirovannykh i veroyatnostnykh avtomatov v labirintakh, Dis. ... kand. fiz.-mat. nauk, Riga, 1987, 90 pp.

[28] Golod E. S., “O nil-algebrakh v finitno-approksimiruemykh gruppakh”, Izv. AN SSSR. Ser. matem., 28:2 (1964), 273–276

[29] Kilibarda G., “Ob universalnykh labirintakh-lovushkakh dlya konechnykh mnozhestv avtomatov”, Diskretnaya matematika, 2:1 (1990), 72–79 | MR | Zbl

[30] Kilibarda G., “O minimalnykh universalnykh kollektivakh avtomatov dlya ploskikh labirintov”, Diskretnaya matematika, 6:4 (1994), 133–153 | MR | Zbl

[31] Kilibarda G., “Novoe dokazatelstvo teoremy Budakha-Podkolzina”, Diskretnaya matematika, 3:3 (1991), 135–146 | MR | Zbl

[32] Kilibarda G., Ushchumlich Sh., “O labirintakh-lovushkakh dlya kollektivov avtomatov”, Diskretnaya matematika, 5:2 (1993), 29–50 | MR | Zbl

[33] Kudryavtsev V. B., Podkolzin A. S., Ushchumlich Sh., Vvedenie v teoriyu abstraktnykh avtomatov, Izd-vo MGU, M., 1985 | MR

[34] Kudryavtsev V. B., Aleshin S. V., Podkolzin A. S., Vvedenie v teoriyu avtomatov, Nauka, M., 1985 | MR

[35] Kudryavtsev V. B., Kilibarda G., Ushchumlich Sh., Sistemy avtomatov v labirintakh, Grant RFFI No 06-01-00240

[36] Novikov P. S., Adyan S. I., “O beskonechnykh periodicheskikh gruppakh. I, II, III”, Izv. AN SSSR. Ser. matem., 32:1 (1968), 212–244 ; 32:2, 251–524 ; 32:3, 709–731 | MR

[37] Sanov I. N., “Reshenie problemy Bernsaida dlya pokazatelya 4”, Uchenye zapiski LGU. Ser. matem., 10 (1940), 166–170 | MR

[38] Xarari F., Teoriya grafov, Mir, M., 1973