Diskretnaya Matematika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Diskretnaya Matematika, 1993, Volume 5, Issue 1, Pages 59–69 (Mi dm668)  

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
Bibliographic databases:
UDC: 519.713
Language: Russian
Citation: A. A. Zolotykh, “Traversing labyrinths with holes that are restricted in fixed directions”, Diskr. Mat., 5:1 (1993), 59–69
Citation in format AMSBIB
\Bibitem{Zol93}
\by A.~A.~Zolotykh
\paper Traversing labyrinths with holes that are restricted in fixed directions
\jour Diskr. Mat.
\yr 1993
\vol 5
\issue 1
\pages 59--69
\mathnet{http://mi.mathnet.ru/dm668}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=1221670}
\zmath{https://zbmath.org/?q=an:0853.68135}
Linking options:
  • https://www.mathnet.ru/eng/dm668
  • https://www.mathnet.ru/eng/dm/v5/i1/p59
  • This publication is cited in the following 2 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретная математика
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024