Search by:
Year of publication
Author name
Paper title
On height of vertex identifiers of vertex labeled graphs
Full text (PDF)
UDC: 519.7
Publication Language: Russian
Stuc. intelekt. 2013; 18(3):444-454
Abstract: 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.
Keywords: vertex labeled graphs, languages over the label alphabet, vertex identifiers
References:
- 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.