Образец для цитирования:
Сапунов С. В. Об оценке длины слова, различающего две вершины помеченного неорграфа // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2013. Т. 13, вып. 2. С. 105-111. DOI: https://doi.org/10.18500/1816-9791-2013-13-2-1-105-111
Об оценке длины слова, различающего две вершины помеченного неорграфа
Рассматривается задача различения вершин помеченного неорграфа по ассоциированным с ними языкам в алфавите меток. Показано, что верхняя оценка длины слова, различающего две вершины графа, равна половине от числа его вершин.
1. Глушков В. М., Цейтлин Г. Е., Ющенко Е. Л. Ал-
гебра. Языки. Программирование. Киев : Наук. думка,
1989. 378 с.
2. Капитонова Ю. В., Летичевский А. А. Математи-
ческая теория проектирования вычислительных систем.
М. : Наука, 1988. 298 с.
3. Килибарда Г., Кудрявцев В. Б., Ушчумлич Ш. Неза-
висимые системы автоматов в лабиринтах // Дискрет-
ная математика. 2003. Т. 15, вып. 2. С. 3–39.
4. Dudek G., Jenkin M. Computational Principles of
Mobile Robotics. Cambridge University Press, 2000.
280 p.
5. Сапунов С. В. Эквивалентность помеченных гра-
фов // Труды ИПММ НАНУ. 2002. Т. 7. С. 162–167.
6. Хопкрофт Д. Э., Мотвани Р., Ульман Д. Д. Вве-
дение в теорию автоматов, языков и вычислений. М. :
Издат. дом «Вильямс». 2002. 528 с.
7. Грунский И. С., Сапунов С. В. Восстановление графа
операционной среды мобильного робота путем размет-
ки вершин, пригодной для дальнейшей навигации //
Искусственный интеллект. 2012. № 4. С. 420–428.
8. Грунский И. С., Сапунов С. В. Идентификация вер-
шин помеченных граф
