RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2000 Volume 12, Issue 2, Pages 51–65 (Mi dm335)

This article is cited in 3 papers

On recognizing labyrinths by automata

B. Stamatovic


Abstract: We consider the problem of existence of automata which recognize some rectangular labyrinths. We prove that there is no automaton, which recognizes simple rectangular labyrinths, what is not so for mosaic labyrinths. We describe an infinite class of $\pi$-labyrinths, which are not recognizable by automata.

UDC: 519.7

Received: 17.05.1999

DOI: 10.4213/dm335


 English version:
Discrete Mathematics and Applications, 2000, 10:2, 203–218

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025