RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Chebyshevskii Sb.: Year: Volume: Issue: Page: Find

 Chebyshevskii Sb., 2019, Volume 20, Issue 3, Pages 296–315 (Mi cheb813)

Probabilistic methods of bypass of the labyrinth using stones and random number generator

E. G. Kondakovaa, A. Ya. Kanel-Belovbc

a Moscow Institute of physics and technology (Moscow)
b Bar-Ilan 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 stones-an object that the finite state machine can carry over the graph, and flags-an 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 17-11-01377 The work is supported By the Russian Scientific Foundation (grant № 17-11-01377).

DOI: https://doi.org/10.22405/2226-8383-2018-20-3-296-315

Full text: PDF file (703 kB)

UDC: 519.713
Accepted:12.11.2019

Citation: E. G. Kondakova, A. Ya. Kanel-Belov, “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.~Kanel-Belov \paper Probabilistic methods of bypass of the labyrinth using stones and random number generator \jour Chebyshevskii Sb. \yr 2019 \vol 20 \issue 3 \pages 296--315 \mathnet{http://mi.mathnet.ru/cheb813} \crossref{https://doi.org/10.22405/2226-8383-2018-20-3-296-315}