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

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

Повний опис

Збережено в:
Бібліографічні деталі
Дата: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 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
Опис
Резюме:Рассматривается задача различения вершин помеченного графа по ассоциированным с ними языкам в алфавите меток. Показано, что верхняя оценка длины слова, различающего две вершины графа, детерминированного по разметке окрестностей вершин, равна половине числа его вершин. Показано также, что в языке каждой из любых двух различных вершин есть слово, отличающее одну вершину от другой, и его длина меньше числа вершин графа. Найдены оценки высоты конечных множеств слов, отличающих одну вершину графа от всех других его вершин (т.н. идентификаторов).