Traversing labyrinths with holes that are restricted in fixed directions
Diskretnaya Matematika, Tome 5 (1993) no. 1, pp. 59-69
Citer cet article
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$.