This article is cited in 2 papers

Traversing labyrinths with holes that are restricted in fixed directions

A. A. Zolotykh


Abstract: 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$.

UDC: 519.713

Received: 12.07.1991

Bibliographic databases:

• 
•