Geodesic
On traversing labyrinths by automata that leave nonerasable marks
Diskretnaya Matematika, Tome 9 (1997) no. 1, pp. 123-133

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

The problem of traversal of plane labyrinths by automata was set by C. Shannon at the beginning of sixties. It is known that there exists no finite automaton which can traverse an arbitrary preassigned labyrinth. It is natural to carry on the search of the positive solution of the problem of the traversal of labyrinths by automata in two directions. The first direction is concerned with consideration of more restricted classes of labyrinths and the second one is concerned with extension of capabilities of automata traversing labyrinths. In this paper it is shown that there exists an automaton leaving one unremovable label (colour) in nodes of a labyrinth which can traverse an arbitrary rectangular labyrinth. 
@article{DM_1997_9_1_a9,
     author = {A. Z. Nasyrov},
     title = {On traversing labyrinths by automata that leave nonerasable marks},
     journal = {Diskretnaya Matematika},
     pages = {123--133},
     publisher = {mathdoc},
     volume = {9},
     number = {1},
     year = {1997},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_1997_9_1_a9/}
}
TY  - JOUR
AU  - A. Z. Nasyrov
TI  - On traversing labyrinths by automata that leave nonerasable marks
JO  - Diskretnaya Matematika
PY  - 1997
SP  - 123
EP  - 133
VL  - 9
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_1997_9_1_a9/
LA  - ru
ID  - DM_1997_9_1_a9
ER  - 
%0 Journal Article
%A A. Z. Nasyrov
%T On traversing labyrinths by automata that leave nonerasable marks
%J Diskretnaya Matematika
%D 1997
%P 123-133
%V 9
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_1997_9_1_a9/
%G ru
%F DM_1997_9_1_a9
A. Z. Nasyrov. On traversing labyrinths by automata that leave nonerasable marks. Diskretnaya Matematika, Tome 9 (1997) no. 1, pp. 123-133. http://geodesic.mathdoc.fr/item/DM_1997_9_1_a9/