О высоте идентификаторов вершин помеченных графов
Рассматривается задача различения вершин помеченного графа по ассоциированным с ними языкам в алфавите меток. Показано, что верхняя оценка длины слова, различающего две вершины графа, детерминированного по разметке окрестностей вершин, равна половине числа его вершин. Показано также, что в языке...
Збережено в:
| Дата: | 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| id |
irk-123456789-85116 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-851162015-07-20T03:02:22Z О высоте идентификаторов вершин помеченных графов Сапунов, С.В. Пилипенко, В.Ю. Интеллектуальные робототехнические системы Рассматривается задача различения вершин помеченного графа по ассоциированным с ними языкам в алфавите меток. Показано, что верхняя оценка длины слова, различающего две вершины графа, детерминированного по разметке окрестностей вершин, равна половине числа его вершин. Показано также, что в языке каждой из любых двух различных вершин есть слово, отличающее одну вершину от другой, и его длина меньше числа вершин графа. Найдены оценки высоты конечных множеств слов, отличающих одну вершину графа от всех других его вершин (т.н. идентификаторов). Розглядається задача розрізнення вершин позначеного графа за асоційованими з ними мовами в алфавіті позначок. Визначено, що верхня оцінка довжини слова, що розрізнює дві вершини графа, детермінованого за розміткою околів вершин, дорівнює половині від кількості його вершин. Визначено також, що у мові кожної з двох різних вершин є слово, яке відрізняє одну вершину від іншої, і його довжина менша, ніж кількість вершин у графі. Знайдено оцінки висоти скінчених множин слів, що відрізняють одну вершину графа від інших його вершин (т.з. ідентифікаторів). The problem of vertex distinguishing on vertex labeled graphs is considered. Two vertices are called distinguishable if associated languages over the alphabet of labels are different. A linear upper bound of vertex distinguishing word length equal to half of the number of all vertices is obtained. It is shown that at both languages of two different vertices there are distinguishing words and their lengths are less then number of all vertices. Upper bounds of height of finite sets of words over the vertex labels alphabet distinguishing a given vertex from other (i.e. identifiers) are obtained. 2013 Article О высоте идентификаторов вершин помеченных графов / С.В. Сапунов, В.Ю. Пилипенко // Искусственный интеллект. — 2013. — № 3. — С. 444–454. — Бібліогр.: 8 назв. — рос. 1561-5359 http://dspace.nbuv.gov.ua/handle/123456789/85116 519.7 ru Искусственный интеллект Інститут проблем штучного інтелекту МОН України та НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Интеллектуальные робототехнические системы Интеллектуальные робототехнические системы |
| spellingShingle |
Интеллектуальные робототехнические системы Интеллектуальные робототехнические системы Сапунов, С.В. Пилипенко, В.Ю. О высоте идентификаторов вершин помеченных графов Искусственный интеллект |
| description |
Рассматривается задача различения вершин помеченного графа по ассоциированным с ними языкам в
алфавите меток. Показано, что верхняя оценка длины слова, различающего две вершины графа,
детерминированного по разметке окрестностей вершин, равна половине числа его вершин. Показано
также, что в языке каждой из любых двух различных вершин есть слово, отличающее одну вершину
от другой, и его длина меньше числа вершин графа. Найдены оценки высоты конечных множеств
слов, отличающих одну вершину графа от всех других его вершин (т.н. идентификаторов). |
| format |
Article |
| author |
Сапунов, С.В. Пилипенко, В.Ю. |
| author_facet |
Сапунов, С.В. Пилипенко, В.Ю. |
| author_sort |
Сапунов, С.В. |
| title |
О высоте идентификаторов вершин помеченных графов |
| title_short |
О высоте идентификаторов вершин помеченных графов |
| title_full |
О высоте идентификаторов вершин помеченных графов |
| title_fullStr |
О высоте идентификаторов вершин помеченных графов |
| title_full_unstemmed |
О высоте идентификаторов вершин помеченных графов |
| title_sort |
о высоте идентификаторов вершин помеченных графов |
| publisher |
Інститут проблем штучного інтелекту МОН України та НАН України |
| publishDate |
2013 |
| topic_facet |
Интеллектуальные робототехнические системы |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/85116 |
| citation_txt |
О высоте идентификаторов вершин помеченных
графов / С.В. Сапунов, В.Ю. Пилипенко // Искусственный интеллект. — 2013. — № 3. — С. 444–454. — Бібліогр.: 8 назв. — рос. |
| series |
Искусственный интеллект |
| work_keys_str_mv |
AT sapunovsv ovysoteidentifikatorovveršinpomečennyhgrafov AT pilipenkovû ovysoteidentifikatorovveršinpomečennyhgrafov |
| first_indexed |
2023-10-18T19:30:24Z |
| last_indexed |
2023-10-18T19:30:24Z |
| _version_ |
1796147146652647424 |