Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


Образец для цитирования:

Сапунов С. В. Об оценке длины слова, различающего две вершины помеченного неорграфа // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2013. Т. 13, вып. 2. С. 105-111. DOI: https://doi.org/10.18500/1816-9791-2013-13-2-1-105-111

Опубликована онлайн: 
27.02.2013
Язык публикации: 
русский
Рубрика: 
УДК: 
519.7

Об оценке длины слова, различающего две вершины помеченного неорграфа

Авторы: 
Сапунов Сергей Валерьевич, Институт прикладной математики и механики НАН Украины, г. Донецк
Аннотация: 

Рассматривается задача различения вершин помеченного неорграфа по ассоциированным с ними языкам в алфавите меток. Показано, что верхняя оценка длины слова, различающего две вершины графа, равна половине от числа его вершин. 

DOI: 
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. Грунский И. С., Сапунов С. В. Идентификация вер- шин помеченных граф
Краткое содержание:
(downloads: 7)
Полный текст в формате PDF:
(downloads: 10)