Chebyshevskii Sbornik
General information
Latest issue

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Chebyshevskii Sb.:

Personal entry:
Save password
Forgotten password?

Chebyshevskii Sb., 2019, Volume 20, Issue 3, Pages 165–192 (Mi cheb806)  

Behavior of finite automata in mazes

D. V. Gusev

Moscow Institute of physics and technology (Moscow)

Abstract: 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.

Keywords: maze traversal, finite state machine.

Funding Agency Grant Number
Russian Science Foundation 17-11-01377
The work was supported By the Russian scientific Foundation (grant № 17-11-01377).


Full text: PDF file (951 kB)
References: PDF file   HTML file

UDC: 517+519.713
Received: 05.10.2019

Citation: D. V. Gusev, “Behavior of finite automata in mazes”, Chebyshevskii Sb., 20:3 (2019), 165–192

Citation in format AMSBIB
\by D.~V.~Gusev
\paper Behavior of finite automata in mazes
\jour Chebyshevskii Sb.
\yr 2019
\vol 20
\issue 3
\pages 165--192

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Number of views:
    This page:90
    Full text:35

    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021