|
Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 2009, Number 10, Pages 14–22
(Mi ivm3073)
|
|
|
|
Distinguishability of $s$-labyrinths
V. I. Grunskaya Chair of Mathematics and Information Science, Dimitrovgrad Branch of Ul'yanovsk State University, Dimitrovgrad, Ul'yanovsk region, Russia
Abstract:
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.
Received: 14.05.2007 Revised: 05.05.2009
Citation:
V. I. Grunskaya, “Distinguishability of $s$-labyrinths”, Izv. Vyssh. Uchebn. Zaved. Mat., 2009, no. 10, 14–22; Russian Math. (Iz. VUZ), 53:10 (2009), 11–17
Linking options:
https://www.mathnet.ru/eng/ivm3073 https://www.mathnet.ru/eng/ivm/y2009/i10/p14
|
Statistics & downloads: |
Abstract page: | 277 | Full-text PDF : | 49 | References: | 32 | First page: | 1 |
|