|
This article is cited in 3 scientific papers (total in 3 papers)
On the complexity of traversing labyrinths by an automaton
G. Kilibarda
Abstract:
The class of all finite labyrinths with finite holes with diameter no larger than a given natural number $n$ was considered by S. A. Bogomolov, A. A. Zolotykh and A. N. Zyrychev [Avtomaty i grafy (Automata and graphs), Saratov. Univ., Saratov, 1991; per bibl.]. They showed that a universal shunt having no more than $Cn^2$ states exists for this class. In this paper we give a more efficient bypass algorithm than the one in the above-cited book. We construct a universal shunt for this class that has $Cn$ states.
Received: 31.03.1992
Citation:
G. Kilibarda, “On the complexity of traversing labyrinths by an automaton”, Diskr. Mat., 5:3 (1993), 116–124
Linking options:
https://www.mathnet.ru/eng/dm697 https://www.mathnet.ru/eng/dm/v5/i3/p116
|
Statistics & downloads: |
Abstract page: | 311 | Full-text PDF : | 163 | First page: | 1 |
|