Geodesic
On traversing labyrinths by automata in $n$-dimensional space
Diskretnaya Matematika, Tome 12 (2000) no. 4, pp. 121-137
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The problem of traversing spatial labyrinths by automata is considered. It is proved that there exists an automaton that makes one unremovable mark (colour) on vertices of a labyrinth and traverses an arbitrary $n$-dimensional rectangular labyrinth. 
@article{DM_2000_12_4_a9,
     author = {A. Z. Nasyrov},
     title = {On traversing labyrinths by automata in $n$-dimensional space},
     journal = {Diskretnaya Matematika},
     pages = {121--137},
     year = {2000},
     volume = {12},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2000_12_4_a9/}
}
TY  - JOUR
AU  - A. Z. Nasyrov
TI  - On traversing labyrinths by automata in $n$-dimensional space
JO  - Diskretnaya Matematika
PY  - 2000
SP  - 121
EP  - 137
VL  - 12
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DM_2000_12_4_a9/
LA  - ru
ID  - DM_2000_12_4_a9
ER  - 
%0 Journal Article
%A A. Z. Nasyrov
%T On traversing labyrinths by automata in $n$-dimensional space
%J Diskretnaya Matematika
%D 2000
%P 121-137
%V 12
%N 4
%U http://geodesic.mathdoc.fr/item/DM_2000_12_4_a9/
%G ru
%F DM_2000_12_4_a9
A. Z. Nasyrov. On traversing labyrinths by automata in $n$-dimensional space. Diskretnaya Matematika, Tome 12 (2000) no. 4, pp. 121-137. http://geodesic.mathdoc.fr/item/DM_2000_12_4_a9/

[1] Budach L., “Automata and labyrinths”, Math. Nachrichten, 86 (1978), 195–282 | DOI | MR | Zbl

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

[3] Kudryavtsev V. B., Ushchumlich Sh., Kilibarda G., “O povedenii avtomatov v labirintakh”, Diskretnaya matematika, 4:3 (1992), 3–28 | MR | Zbl

[4] Zyrichev A. N., “O sinteze avtomata, obkhodyaschego ploskie labirinty s ogranichennymi dyrami”, Diskretnaya matematika, 3:1 (1991), 105–113 | MR | Zbl

[5] Zolotykh A. A., “Obkhod labirintov s ogranichennymi v fiksirovannykh napravleniyakh dyrami”, Diskretnaya matematika, 5:1 (1993), 59–69 | MR | Zbl

[6] Blum M., Kozen D., “On the power of the compass”, Proc. 19th Annual Symposium on Foundations of Computer Sci., 1978, 132–142 | MR

[7] Hemmerling A., “Normed two-plane traps for finite systems of cooperating compass”, J. Inf. Process Cybern., 28:8,9 (1987), 453–470 | MR

[8] Nasyrov A. Z., “Ob obkhode labirintov avtomatami, ostavlyayuschimi nestiraemye metki”, Diskretnaya matematika, 9:1 (1997), 123–133 | MR | Zbl