
Probabilistic methods of bypass of the labyrinth using stones and random number generator
E. G. Kondakova^{a}, A. Ya. KanelBelov^{bc} ^{a} Moscow Institute of physics and
technology (Moscow)
^{b} BarIlan University (Ramat Gan, Israel)
^{c} College of Mathematics and Statistics,
Shenzhen University, Shenzhen, 518061, China
Abstract:
There is a wide range of problems devoted to the possibility of traversing the maze by finite automatons.
They can differ as the type of maze(it can be any graph, even infinite), and the automata themselves or their number.
In particular, a finite state machine can have a memory (store) or a random bit generator.
In the future, we will assume that the robot — is a finite automaton with a random bit generator, unless otherwise stated.
In addition, in this system, there can be stonesan object that the finite state machine can carry over the graph, and flagsan object whose presence the finite state machine can only "observe".
This topic is of interest due to the fact that some of these problems are closely related to problems from probability theory and computational complexity.
This paper continues to address some of the open questions posed in Ajans's thesis: traversal by a robot with a random bit generator of integer spaces in the presence of a stone and a subspace of [4] flags.
Such problems help to develop the mathematical apparatus in this area, in addition, in this work we investigate the almost unexplored behavior of a robot with a random number generator.
It is extremely important to transfer combinatorial methods developed by A. M. Raigorodsky in the problems of this topic.
This work is devoted to the maze traversal by a finite automaton with a random bit generator.
This problem is part of the actively developing theme of traversing the maze by various finite automata
or their teams, which is closely related to problems from the theory of complexity of calculations and probability theory.
In this work it is shown what dimensions a robot with a generator of random bits, and you can get around stone
integer space with flag subspace. In this paper, we will study the behavior of a finite automaton with a random bit generator on integer spaces.
In particular, it is proved that
the robot bypasses $\mathbb{Z}^2$ and cannot bypass $\mathbb{Z}^3$;
the c ++ robot bypasses $\mathbb{Z}^4$ and cannot bypass $\mathbb{Z}^5$;
a robot with a stone and a flag bypasses $\mathbb{Z}^6$ and cannot bypass $\mathbb{Z}^7$;
a robot with a stone and a flag plane bypasses $\mathbb{Z}^8$ and cannot bypass $\mathbb{Z}^9$.
Keywords:
maze traversal, finite state machine.
Funding Agency 
Grant Number 
Russian Science Foundation 
171101377 
The work is supported By the Russian Scientific Foundation (grant № 171101377). 
DOI:
https://doi.org/10.22405/222683832018203296315
Full text:
PDF file (703 kB)
UDC:
519.713 Received: 05.10.2019 Accepted:12.11.2019
Citation:
E. G. Kondakova, A. Ya. KanelBelov, “Probabilistic methods of bypass of the labyrinth using stones and random number generator”, Chebyshevskii Sb., 20:3 (2019), 296–315
Citation in format AMSBIB
\Bibitem{KonKan19}
\by E.~G.~Kondakova, A.~Ya.~KanelBelov
\paper Probabilistic methods of bypass of the labyrinth using stones and random number generator
\jour Chebyshevskii Sb.
\yr 2019
\vol 20
\issue 3
\pages 296315
\mathnet{http://mi.mathnet.ru/cheb813}
\crossref{https://doi.org/10.22405/222683832018203296315}
Linking options:
http://mi.mathnet.ru/eng/cheb813 http://mi.mathnet.ru/eng/cheb/v20/i3/p296
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles

Number of views: 
This page:  7  Full text:  2 
