Шукати за:
Роком видання
Автором
Назвою статті
On height of vertex identifiers of vertex labeled graphs
Повний текст (PDF)
УДК: 519.7
Мова публікації: Російська
Stuc. intelekt. 2013; 18; (3):444-454
Анотація: The problem of vertex distinguishing on vertex labeled graphs is considered. Two vertices are called distinguishable if associated languages over the alphabet of labels are different. A linear upper bound of vertex distinguishing word length equal to half of the number of all vertices is obtained. It is shown that at both languages of two different vertices there are distinguishing words and their lengths are less then number of all vertices. Upper bounds of height of finite sets of words over the vertex labels alphabet distinguishing a given vertex from other (i.e. identifiers) are obtained.
Ключові слова: vertex labeled graphs, languages over the label alphabet, vertex identifiers
Посилання:
- Kapitonova Yu.V., Letichevsky A.A. Mathematical Theory of Computational Systems Design. – Moscow : Nauka, 1988. – 296 p.
- Dudek G. Jenkin M. Computational Principles of Mobile Robotics – Cambridge University Press, Cambridge, 2000. – 280 p.
- Peled Doron A. Software Reliability Methods – Springer. – Verlag, 2001. – 331 p.
- Kohavi Z., Jha N. Switching and finite automata theory – Cambridge University Press, 2010. – 617 p.
- Sapunov S.V. Mobile Robot Self Location on Topological Environment // Iskusstvennyj intellekt. – 2008. № 4. – P. 558-565.
- Grunsky I.S., Sapunov S.V. Identification of vertices of vertex labeled graphs // Trudy IPMM. – 2010. – V. 20. – P. 86-97.
- Hopcroft J.E., Motwani R., Ullman J.D. Introduction to Automata Theory, Languages, and Computation. – Moscow, Williams Publishing, 2002. – 528 p.
- Grunsky I.S., Sapunov S.V. Reconstruction of the graph of operating environment of mobile robot by vertex-labeling sufficient for further navigation // Iskusstvennyj intellekt. – 2012. № 4. – P. 420-428.