Geodesic
On the complexity of traversing labyrinths by an automaton
Diskretnaya Matematika, Tome 5 (1993) no. 3, pp. 116-124.

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

The class of all finite labyrinths with finite holes with diameter no larger than a given natural number $n$ was considered by S. A. Bogomolov, A. A. Zolotykh and A. N. Zyrychev [Avtomaty i grafy (Automata and graphs), Saratov. Univ., Saratov, 1991; per bibl.]. They showed that a universal shunt having no more than $Cn^2$ states exists for this class. In this paper we give a more efficient bypass algorithm than the one in the above-cited book. We construct a universal shunt for this class that has $Cn$ states. 
@article{DM_1993_5_3_a10,
     author = {G. Kilibarda},
     title = {On the complexity of traversing labyrinths by an automaton},
     journal = {Diskretnaya Matematika},
     pages = {116--124},
     publisher = {mathdoc},
     volume = {5},
     number = {3},
     year = {1993},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_1993_5_3_a10/}
}
TY  - JOUR
AU  - G. Kilibarda
TI  - On the complexity of traversing labyrinths by an automaton
JO  - Diskretnaya Matematika
PY  - 1993
SP  - 116
EP  - 124
VL  - 5
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_1993_5_3_a10/
LA  - ru
ID  - DM_1993_5_3_a10
ER  - 
%0 Journal Article
%A G. Kilibarda
%T On the complexity of traversing labyrinths by an automaton
%J Diskretnaya Matematika
%D 1993
%P 116-124
%V 5
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_1993_5_3_a10/
%G ru
%F DM_1993_5_3_a10
G. Kilibarda. On the complexity of traversing labyrinths by an automaton. Diskretnaya Matematika, Tome 5 (1993) no. 3, pp. 116-124. http://geodesic.mathdoc.fr/item/DM_1993_5_3_a10/