Geodesic
Traversing labyrinths with holes that are restricted in fixed directions
Diskretnaya Matematika, Tome 5 (1993) no. 1, pp. 59-69.

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

For an arbitrary rational direction we consider the class of $\pi$-labyrinths whose projections of interior holes in a given direction lie within intervals of length $d$ (bounded in the given direction by the number $d$). We show that for any such class there exists a universal automaton that traverses all the $\pi$-labyrinths of this class. The number of states of the automaton depends linearly on $d$. We also consider classes of $\pi$-labyrinths all of whose interior holes are bounded by the number $d$ in some rational direction in a fixed finite set. We prove that if a certain constraint on the distribution of the interior holes in $\pi$-labyrinths of such a class is satisfied, then this class of $\pi$-labyrinths has a universal automaton. The number of states of the automaton depends cubically on $d$. 
@article{DM_1993_5_1_a3,
     author = {A. A. Zolotykh},
     title = {Traversing labyrinths with holes that are restricted in fixed directions},
     journal = {Diskretnaya Matematika},
     pages = {59--69},
     publisher = {mathdoc},
     volume = {5},
     number = {1},
     year = {1993},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_1993_5_1_a3/}
}
TY  - JOUR
AU  - A. A. Zolotykh
TI  - Traversing labyrinths with holes that are restricted in fixed directions
JO  - Diskretnaya Matematika
PY  - 1993
SP  - 59
EP  - 69
VL  - 5
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_1993_5_1_a3/
LA  - ru
ID  - DM_1993_5_1_a3
ER  - 
%0 Journal Article
%A A. A. Zolotykh
%T Traversing labyrinths with holes that are restricted in fixed directions
%J Diskretnaya Matematika
%D 1993
%P 59-69
%V 5
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_1993_5_1_a3/
%G ru
%F DM_1993_5_1_a3
A. A. Zolotykh. Traversing labyrinths with holes that are restricted in fixed directions. Diskretnaya Matematika, Tome 5 (1993) no. 1, pp. 59-69. http://geodesic.mathdoc.fr/item/DM_1993_5_1_a3/