|
This article is cited in 2 scientific papers (total 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$.
Received: 12.07.1991
Citation:
A. A. Zolotykh, “Traversing labyrinths with holes that are restricted in fixed directions”, Diskr. Mat., 5:1 (1993), 59–69
Linking options:
https://www.mathnet.ru/eng/dm668 https://www.mathnet.ru/eng/dm/v5/i1/p59
|
|