Geodesic
On recognizing labyrinths by automata
Diskretnaya Matematika, Tome 12 (2000) no. 2, pp. 51-65 
B. Stamatovic. On recognizing labyrinths by automata. Diskretnaya Matematika, Tome 12 (2000) no. 2, pp. 51-65. http://geodesic.mathdoc.fr/item/DM_2000_12_2_a3/
@article{DM_2000_12_2_a3,
     author = {B. Stamatovic},
     title = {On recognizing labyrinths by automata},
     journal = {Diskretnaya Matematika},
     pages = {51--65},
     year = {2000},
     volume = {12},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2000_12_2_a3/}
}
TY  - JOUR
AU  - B. Stamatovic
TI  - On recognizing labyrinths by automata
JO  - Diskretnaya Matematika
PY  - 2000
SP  - 51
EP  - 65
VL  - 12
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DM_2000_12_2_a3/
LA  - ru
ID  - DM_2000_12_2_a3
ER  - 
%0 Journal Article
%A B. Stamatovic
%T On recognizing labyrinths by automata
%J Diskretnaya Matematika
%D 2000
%P 51-65
%V 12
%N 2
%U http://geodesic.mathdoc.fr/item/DM_2000_12_2_a3/
%G ru
%F DM_2000_12_2_a3

Voir la notice de l'article provenant de la source Math-Net.Ru

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.

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

[2] Kudryavtsev V. B., Podkolzin A. S., Ushchumlich Sh., Vvedenie v teoriyu abstraktnykh avtomatov, Nauka, Moskva, 1985

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

[4] Kharari F., Teoriya grafov, Mir, Moskva, 1973 | MR