Geodesic
Distinguishability of $s$-labyrinths
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 10 (2009), pp. 14-22 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In this paper we consider rectangular and $s$-labyrinths. We investigate problems similar to classical ones in the automata theory, namely, the distinguishability of vertices and the labyrinths equivalence. We prove that for the considered class of labyrinths these problems are solvable and estimate the distinguishing word length. For rectangular labyrinths we prove that the isomorphism and equivalence relations coincide.
Keywords: plane rectangular labyrinth, $s$-labyrinth, distinguishability of vertices, distinguishability of labyrinths. 
@article{IVM_2009_10_a1,
     author = {V. I. Grunskaya},
     title = {Distinguishability of $s$-labyrinths},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {14--22},
     year = {2009},
     number = {10},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2009_10_a1/}
}
TY  - JOUR
AU  - V. I. Grunskaya
TI  - Distinguishability of $s$-labyrinths
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2009
SP  - 14
EP  - 22
IS  - 10
UR  - http://geodesic.mathdoc.fr/item/IVM_2009_10_a1/
LA  - ru
ID  - IVM_2009_10_a1
ER  - 
%0 Journal Article
%A V. I. Grunskaya
%T Distinguishability of $s$-labyrinths
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2009
%P 14-22
%N 10
%U http://geodesic.mathdoc.fr/item/IVM_2009_10_a1/
%G ru
%F IVM_2009_10_a1
V. I. Grunskaya. Distinguishability of $s$-labyrinths. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 10 (2009), pp. 14-22. http://geodesic.mathdoc.fr/item/IVM_2009_10_a1/

[1] Kuipers B., “The spatial semantic hierarchy”, Artificial Intelligence, 119:1–2 (2000), 191–233 | DOI | MR | Zbl

[2] Kilibarda G., Kudryavtsev V. B., Ushchumlich Sch., “Nezavisimye sistemy avtomatov v labirintakh”, Diskretn. matem., 15:2 (2003), 3–39 | MR | Zbl

[3] Grunskaya V. I., “Ob otlichimosti ploskikh shakhmatnykh labirintov”, Intellektualnye sistemy, 8 (2004), 457–464

[4] Sapunov S. V., “Ekvivalentnost pomechennykh grafov”, Tr. IPMM NANU, 7, 2002, 162–167 | MR | Zbl

[5] Sapunov S. V., “Kontrol pomechennykh grafov”, Tr. IPMM NANU, 8, 2003, 106–110 | MR | Zbl

[6] Kharari F., Teoriya grafov, Mir, M., 1973, 300 pp. | MR

[7] Kudryavtsev V. B., Aleshin S. V., Podkolzin A. S., Vvedenie v teoriyu konechnykh avtomatov, Nauka, M., 1985, 320 pp. | MR | Zbl

[8] Grunskaya V. I., “Realizuemost slov v mozaichnykh labirintakh”, Izvestiya vuzov. Matematika, 2009, no. 8, 19–25