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/}
}
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/