О высоте идентификаторов вершин помеченных графов

• Дата: 2013
• Автори: Сапунов, С.В., Пилипенко, В.Ю.
• Формат: Стаття
• Мова: Russian
• Опубліковано: Інститут проблем штучного інтелекту МОН України та НАН України 2013
• Назва видання: Искусственный интеллект
• Теми: Интеллектуальные робототехнические системы
• Онлайн доступ: http://dspace.nbuv.gov.ua/handle/123456789/85116
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Цитувати: О высоте идентификаторов вершин помеченных графов / С.В. Сапунов, В.Ю. Пилипенко // Искусственный интеллект. — 2013. — № 3. — С. 444–454. — Бібліогр.: 8 назв. — рос.

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