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

• Veröffentlicht in: Искусственный интеллект
• Datum: 2013
• Hauptverfasser: Сапунов, С.В., Пилипенко, В.Ю.
• Format: Artikel
• Sprache: Russian
• Veröffentlicht: Інститут проблем штучного інтелекту МОН України та НАН України 2013
• Schlagworte: Интеллектуальные робототехнические системы
• Online Zugang: https://nasplib.isofts.kiev.ua/handle/123456789/85116
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Zitieren: О высоте идентификаторов вершин помеченных графов / С.В. Сапунов, В.Ю. Пилипенко // Искусственный интеллект. — 2013. — № 3. — С. 444–454. — Бібліогр.: 8 назв. — рос.

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