Geodesic
On recognizing labyrinths by automata
Diskretnaya Matematika, Tome 12 (2000) no. 2, pp. 51-65.

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. 
@article{DM_2000_12_2_a3,
     author = {B. Stamatovic},
     title = {On recognizing labyrinths by automata},
     journal = {Diskretnaya Matematika},
     pages = {51--65},
     publisher = {mathdoc},
     volume = {12},
     number = {2},
     year = {2000},
     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
PB  - mathdoc
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
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2000_12_2_a3/
%G ru
%F DM_2000_12_2_a3
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/

[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