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