Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. II. Реконструкция при наличии запрещенного слова
Рассматривается расширение задачи реконструкции слов по заданному мультимножеству подслов, предположительно порожденных смещением окна фиксированной длины со сдвигом 1. Это связано с наличием дополнительных ограничений на допустимые решения. Изучен случай, когда эти ограничения определяются запрещен...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2015 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2015
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/124770 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. II. Реконструкция при наличии запрещенного слова / Ю.Г. Сметанин, М.В. Ульянов // Кибернетика и системный анализ. — 2015. — Т. 51, № 1. — С. 179-186. — Бібліогр.: 10 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862734850259156992 |
|---|---|
| author | Сметанин, Ю.Г. Ульянов, М.В. |
| author_facet | Сметанин, Ю.Г. Ульянов, М.В. |
| citation_txt | Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. II. Реконструкция при наличии запрещенного слова / Ю.Г. Сметанин, М.В. Ульянов // Кибернетика и системный анализ. — 2015. — Т. 51, № 1. — С. 179-186. — Бібліогр.: 10 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Рассматривается расширение задачи реконструкции слов по заданному мультимножеству подслов, предположительно порожденных смещением окна фиксированной длины со сдвигом 1. Это связано с наличием дополнительных ограничений на допустимые решения. Изучен случай, когда эти ограничения определяются запрещенными словами. Получено решение задачи, основанное на поиске эйлеровых путей в мультиорграфе де Брейна с дополнительной операцией редукции ребер и применением специальных алгебраических операций умножения матриц смежности, определенных в первой части статьи.
Розглянуто розширений варіант проблеми реконструкцii слів за заданою мультимножиною пiдслiв у гіпотезі, що цей набір породжений зміщенням вікна фіксованої довжини уздовж невідомого слова з одиничним зміщенням. Даний варіант пов’язаний з наявністю додаткових обмежень на допустимі розв’язки. Вивчено випадок, коли ці обмеження визначаються забороненими словами. Запропонований розв’язок, заснований на пошуку ейлерових шляхів у мультиорграфi де Брейна з додатковою операцією редукції ребер та застосуванням спеціальних алгебраїчних операцій множення матриць суміжностi, визначених у першій частині статті.
In the second part of the paper, an extended problem of the reconstruction of a word from a set of its subwords is considered. It is assumed that the set is generated by unit shifts of a fixed window along an unknown word. In the new variant, feasible solutions must satisfy additional constraints. The case where these constraints are defined by forbidden words is considered. A solution is proposed based on the search for Euler paths or Euler cycles in a de Bruijn multidigraph with additional operation of edge reduction. After that, symbolic multiplication of adjacency matrices is applied in the same way as in the first part of the paper.
|
| first_indexed | 2025-12-07T19:45:24Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-124770 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T19:45:24Z |
| publishDate | 2015 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Сметанин, Ю.Г. Ульянов, М.В. 2017-10-04T19:50:54Z 2017-10-04T19:50:54Z 2015 Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. II. Реконструкция при наличии запрещенного слова / Ю.Г. Сметанин, М.В. Ульянов // Кибернетика и системный анализ. — 2015. — Т. 51, № 1. — С. 179-186. — Бібліогр.: 10 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/124770 519.16, 519.17 Рассматривается расширение задачи реконструкции слов по заданному мультимножеству подслов, предположительно порожденных смещением окна фиксированной длины со сдвигом 1. Это связано с наличием дополнительных ограничений на допустимые решения. Изучен случай, когда эти ограничения определяются запрещенными словами. Получено решение задачи, основанное на поиске эйлеровых путей в мультиорграфе де Брейна с дополнительной операцией редукции ребер и применением специальных алгебраических операций умножения матриц смежности, определенных в первой части статьи. Розглянуто розширений варіант проблеми реконструкцii слів за заданою мультимножиною пiдслiв у гіпотезі, що цей набір породжений зміщенням вікна фіксованої довжини уздовж невідомого слова з одиничним зміщенням. Даний варіант пов’язаний з наявністю додаткових обмежень на допустимі розв’язки. Вивчено випадок, коли ці обмеження визначаються забороненими словами. Запропонований розв’язок, заснований на пошуку ейлерових шляхів у мультиорграфi де Брейна з додатковою операцією редукції ребер та застосуванням спеціальних алгебраїчних операцій множення матриць суміжностi, визначених у першій частині статті. In the second part of the paper, an extended problem of the reconstruction of a word from a set of its subwords is considered. It is assumed that the set is generated by unit shifts of a fixed window along an unknown word. In the new variant, feasible solutions must satisfy additional constraints. The case where these constraints are defined by forbidden words is considered. A solution is proposed based on the search for Euler paths or Euler cycles in a de Bruijn multidigraph with additional operation of edge reduction. After that, symbolic multiplication of adjacency matrices is applied in the same way as in the first part of the paper. Работа выполнена при поддержке РФФИ, грант № 13-07-00516. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Новые средства кибернетики, информатики, вычислительной техники и системного анализа Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. II. Реконструкция при наличии запрещенного слова Реконструкція слів за кінцевою мультимножиною підслів в гіпотезі зсуву 1. II. Pеконструкція за наявності забороненого слова Reconstruction of a word from a finite set of its subwords under the unit shift hypothesis. Part II: Reconstruction with forbidden words Article published earlier |
| spellingShingle | Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. II. Реконструкция при наличии запрещенного слова Сметанин, Ю.Г. Ульянов, М.В. Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| title | Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. II. Реконструкция при наличии запрещенного слова |
| title_alt | Реконструкція слів за кінцевою мультимножиною підслів в гіпотезі зсуву 1. II. Pеконструкція за наявності забороненого слова Reconstruction of a word from a finite set of its subwords under the unit shift hypothesis. Part II: Reconstruction with forbidden words |
| title_full | Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. II. Реконструкция при наличии запрещенного слова |
| title_fullStr | Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. II. Реконструкция при наличии запрещенного слова |
| title_full_unstemmed | Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. II. Реконструкция при наличии запрещенного слова |
| title_short | Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. II. Реконструкция при наличии запрещенного слова |
| title_sort | реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. ii. реконструкция при наличии запрещенного слова |
| topic | Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| topic_facet | Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/124770 |
| work_keys_str_mv | AT smetaninûg rekonstrukciâslovpokonečnomumulʹtimnožestvupodslovvgipotezesdviga1iirekonstrukciâprinaličiizapreŝennogoslova AT ulʹânovmv rekonstrukciâslovpokonečnomumulʹtimnožestvupodslovvgipotezesdviga1iirekonstrukciâprinaličiizapreŝennogoslova AT smetaninûg rekonstrukcíâslívzakíncevoûmulʹtimnožinoûpídslívvgípotezízsuvu1iipekonstrukcíâzanaâvnostízaboronenogoslova AT ulʹânovmv rekonstrukcíâslívzakíncevoûmulʹtimnožinoûpídslívvgípotezízsuvu1iipekonstrukcíâzanaâvnostízaboronenogoslova AT smetaninûg reconstructionofawordfromafinitesetofitssubwordsundertheunitshifthypothesispartiireconstructionwithforbiddenwords AT ulʹânovmv reconstructionofawordfromafinitesetofitssubwordsundertheunitshifthypothesispartiireconstructionwithforbiddenwords |