Geodesic
Realizability of words in mosaic labyrinths
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 8 (2009), pp. 19-25 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In this paper we study mosaic labyrinths with the help of words generated by them in the alphabet of labels attached to arcs and vertices of a labyrinth. We consider the problem of the characterization of words generated by a labyrinth. We propose a constructive recognition criterion, it defines whether a word is generated by a labyrinth or not. We establish conditions under which a word can be generated by a unique labyrinth, by a finite number of labyrinths, or by infinitely many labyrinths.
Keywords: mosaic labyrinth, realizable word, consistent word, $m$-correct word.
Mots-clés : convolution 
@article{IVM_2009_8_a2,
     author = {V. I. Grunskaya},
     title = {Realizability of words in mosaic labyrinths},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {19--25},
     year = {2009},
     number = {8},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2009_8_a2/}
}
TY  - JOUR
AU  - V. I. Grunskaya
TI  - Realizability of words in mosaic labyrinths
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2009
SP  - 19
EP  - 25
IS  - 8
UR  - http://geodesic.mathdoc.fr/item/IVM_2009_8_a2/
LA  - ru
ID  - IVM_2009_8_a2
ER  - 
%0 Journal Article
%A V. I. Grunskaya
%T Realizability of words in mosaic labyrinths
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2009
%P 19-25
%N 8
%U http://geodesic.mathdoc.fr/item/IVM_2009_8_a2/
%G ru
%F IVM_2009_8_a2
V. I. Grunskaya. Realizability of words in mosaic labyrinths. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 8 (2009), pp. 19-25. http://geodesic.mathdoc.fr/item/IVM_2009_8_a2/

[1] Kurganskii A. N., Neotlichimost konechnykh avtomatov, vzaimodeistvuyuschikh so sredoi, Dis. $\dots$ kand. fiz.-matem. nauk, Saratov, 1997, 104 pp.

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

[3] Grunskii I. S., Kurganskii A. N., “Yazyki grafov s pomechennymi vershinami”, Tr. IPMM NANU, 9, 2004, 53–60 | MR

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

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