Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. II. Реконструкция при наличии запрещенного слова

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2015
Автори:	Сметанин, Ю.Г., Ульянов, М.В.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2015
Назва видання:	Кибернетика и системный анализ
Теми:	Новые средства кибернетики, информатики, вычислительной техники и системного анализа
Онлайн доступ:	http://dspace.nbuv.gov.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

id	irk-123456789-124770
record_format	dspace
spelling	irk-123456789-1247702017-10-05T03:02:50Z Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. II. Реконструкция при наличии запрещенного слова Сметанин, Ю.Г. Ульянов, М.В. Новые средства кибернетики, информатики, вычислительной техники и системного анализа Рассматривается расширение задачи реконструкции слов по заданному мультимножеству подслов, предположительно порожденных смещением окна фиксированной длины со сдвигом 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. 2015 Article Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. II. Реконструкция при наличии запрещенного слова / Ю.Г. Сметанин, М.В. Ульянов // Кибернетика и системный анализ. — 2015. — Т. 51, № 1. — С. 179-186. — Бібліогр.: 10 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/124770 519.16, 519.17 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Новые средства кибернетики, информатики, вычислительной техники и системного анализа Новые средства кибернетики, информатики, вычислительной техники и системного анализа
spellingShingle	Новые средства кибернетики, информатики, вычислительной техники и системного анализа Новые средства кибернетики, информатики, вычислительной техники и системного анализа Сметанин, Ю.Г. Ульянов, М.В. Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. II. Реконструкция при наличии запрещенного слова Кибернетика и системный анализ
description	Рассматривается расширение задачи реконструкции слов по заданному мультимножеству подслов, предположительно порожденных смещением окна фиксированной длины со сдвигом 1. Это связано с наличием дополнительных ограничений на допустимые решения. Изучен случай, когда эти ограничения определяются запрещенными словами. Получено решение задачи, основанное на поиске эйлеровых путей в мультиорграфе де Брейна с дополнительной операцией редукции ребер и применением специальных алгебраических операций умножения матриц смежности, определенных в первой части статьи.
format	Article
author	Сметанин, Ю.Г. Ульянов, М.В.
author_facet	Сметанин, Ю.Г. Ульянов, М.В.
author_sort	Сметанин, Ю.Г.
title	Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. II. Реконструкция при наличии запрещенного слова
title_short	Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. II. Реконструкция при наличии запрещенного слова
title_full	Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. II. Реконструкция при наличии запрещенного слова
title_fullStr	Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. II. Реконструкция при наличии запрещенного слова
title_full_unstemmed	Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. II. Реконструкция при наличии запрещенного слова
title_sort	реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. ii. реконструкция при наличии запрещенного слова
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2015
topic_facet	Новые средства кибернетики, информатики, вычислительной техники и системного анализа
url	http://dspace.nbuv.gov.ua/handle/123456789/124770
citation_txt	Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. II. Реконструкция при наличии запрещенного слова / Ю.Г. Сметанин, М.В. Ульянов // Кибернетика и системный анализ. — 2015. — Т. 51, № 1. — С. 179-186. — Бібліогр.: 10 назв. — рос.
series	Кибернетика и системный анализ
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
first_indexed	2025-07-09T02:00:32Z
last_indexed	2025-07-09T02:00:32Z
_version_	1837132871580516352
fulltext	Þ.Ã. ÑÌÅÒÀÍÈÍ, Ì.Â. ÓËÜßÍÎÂ ÓÄÊ 519.16, 519.17 ÐÅÊÎÍÑÒÐÓÊÖÈß ÑËÎÂ ÏÎ ÊÎÍÅ×ÍÎÌÓ ÌÓËÜÒÈÌÍÎÆÅÑÒÂÓ ÏÎÄÑËÎÂ Â ÃÈÏÎÒÅÇÅ ÑÄÂÈÃÀ 1. II. ÐÅÊÎÍÑÒÐÓÊÖÈß ÏÐÈ ÍÀËÈ×ÈÈ ÇÀÏÐÅÙÅÍÍÎÃÎ ÑËÎÂÀ1 Àííîòàöèÿ. Ðàññìàòðèâàåòñÿ ðàñøèðåíèå çàäà÷è ðåêîíñòðóêöèè ñëîâ ïî çàäàííîìó ìóëü- òèìíîæåñòâó ïîäñëîâ, ïðåäïîëîæèòåëüíî ïîðîæäåííûõ ñìåùåíèåì îêíà ôèêñèðîâàííîé äëèíû ñî ñäâèãîì 1. Ýòî ñâÿçàíî ñ íàëè÷èåì äîïîëíèòåëüíûõ îãðàíè÷åíèé íà äîïóñòèìûå ðåøåíèÿ. Èçó÷åí ñëó÷àé, êîãäà ýòè îãðàíè÷åíèÿ îïðåäåëÿþòñÿ çàïðåùåííûìè ñëîâàìè. Ïî- ëó÷åíî ðåøåíèå çàäà÷è, îñíîâàííîå íà ïîèñêå ýéëåðîâûõ ïóòåé â ìóëüòèîðãðàôå äå Áðåé- íà ñ äîïîëíèòåëüíîé îïåðàöèåé ðåäóêöèè ðåáåð è ïðèìåíåíèåì ñïåöèàëüíûõ àëãåáðàè÷åñ- êèõ îïåðàöèé óìíîæåíèÿ ìàòðèö ñìåæíîñòè, îïðåäåëåííûõ â ïåðâîé ÷àñòè ñòàòüè. Êëþ÷åâûå ñëîâà: ðåêîíñòðóêöèÿ ñëîâ, çàïðåùåííîå ñëîâî, ýéëåðîâû ïóòè, ìóëüòèîðãðàô äå Áðåéíà, êîìáèíàòîðèêà ñëîâ. ÂÂÅÄÅÍÈÅ Â ïåðâîé ÷àñòè íàñòîÿùåé ñòàòüè [1] áûë ïðåäëîæåí íàáîð àëãåáðàè÷åñêèõ îïåðàöèé íàä ñëîâàìè, â òåðìèíàõ êîòîðûõ ñôîðìóëèðîâàíà çàäà÷à ðåêîí- ñòðóêöèè ñëîâ íàä êîíå÷íûì àëôàâèòîì ïî ïîäñëîâàì ýòîãî ñëîâà. Çàäà÷à ðå- êîíñòðóêöèè áûëà ñâåäåíà ê çàäà÷å ïîèñêà ýéëåðîâûõ ïóòåé (öèêëîâ) â ìóëü- òèîðãðàôå äå Áðåéíà. Ïðåäëîæåí ìåòîä ïåðå÷èñëåíèÿ âñåõ ðåøåíèé çàäà÷è ðåêîíñòðóêöèè íà îñíîâå âîçâåäåíèÿ â ñòåïåíü ìàòðèöû ñìåæíîñòè ìóëüòèîð- ãðàôà äå Áðåéíà ñ èñïîëüçîâàíèåì ñïåöèàëüíî ââåäåííûõ îïåðàöèé. Â äîïîëíåíèå ê ïðèâåäåííûì â [1] ðåçóëüòàòàì îòìåòèì, ÷òî èç ïðåäëîæåííîãî ñâåäåíèÿ çàäà÷è ðåêîíñòðóêöèè áåç çàïðåòîâ ê ïîèñêó ýéëåðîâûõ ïóòåé â ìóëüòèîð- ãðàôå äå Áðåéíà î÷åâèäíî ñëåäóåò îäíîçíà÷íîñòü ðåêîíñòðóêöèè â ñëó÷àå, åñëè ïî- ëóñòåïåíü âûõîäà êàæäîé âåðøèíû íå ïðåâîñõîäèò åäèíèöû. Èç ýòîãî, â ñâîþ î÷å- ðåäü, ñëåäóåò ïðåäñòàâëåííûé A. Carpi è A. de Luca â [2] ñîâåðøåííî èíûìè ìåòî- äàìè ðåçóëüòàò î äîñòàòî÷íîé äëèíå ïîäñëîâ äëÿ îäíîçíà÷íîé ðåêîíñòðóêöèè. Â íàñòîÿùåé ñòàòüå ðàññìàòðèâàåòñÿ çàäà÷à ðåêîíñòðóêöèè ïî ïîäñëîâàì, êîãäà äëÿ äîïóñòèìûõ ðåøåíèé ñóùåñòâóþò äîïîëíèòåëüíûå îãðàíè÷åíèÿ. Íàè- áîëüøèé ïðàêòè÷åñêèé èíòåðåñ ïðåäñòàâëÿåò ñëó÷àé, êîãäà ðåêîíñòðóèðóåìîå ñëî- âî íå ñîäåðæèò çàðàíåå çàäàííîãî íàáîðà çàïðåùåííûõ ñëîâ. Ýòîò ñëó÷àé ñîîòâåò- ñòâóåò îïèñàíèþ ïîñëåäîâàòåëüíîñòåé â ñèìâîëè÷åñêîé äèíàìèêå [3], ãäå îñíîâ- íûì ïîíÿòèåì ÿâëÿåòñÿ ïðîñòðàíñòâî ñäâèãîâ (shift space), îïðåäåëÿåìîå íàáîðàìè çàïðåùåííûõ ñëîâ. Â äðóãèõ òåðìèíàõ ðàññìàòðèâàåìóþ çàäà÷ó ìîæíî ñ÷èòàòü çà- äà÷åé âîññòàíîâëåíèÿ ñëîâ èç ÿçûêà, îïðåäåëÿåìîãî íàáîðîì çàïðåùåííûõ ñëîâ. Îäèí èç âîçìîæíûõ âàðèàíòîâ ðåøåíèÿ çàäà÷è ðåêîíñòðóêöèè íà îñíîâå ïîäñëîâ ôèêñèðîâàííîé äëèíû ñäâèãà 1 ïðè åäèíñòâåííîì çàïðåùåííîì ñëîâå ñîñòàâëÿåò ïðåäìåò èññëåäîâàíèÿ íàñòîÿùåé ðàáîòû, ïðåäñòàâëÿþùåé âòîðóþ ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 1 179 1Ðàáîòà âûïîëíåíà ïðè ïîääåðæêå ÐÔÔÈ, ãðàíò ¹ 13-07-00516. Îêîí÷àíèå. Íà÷àëî â ¹ 1, 2014. © Þ.Ã. Ñìåòàíèí, Ì.Â. Óëüÿíîâ, 2015 ÷àñòü ñòàòüè. Äëÿ ðåøåíèÿ çàäà÷è â ýòîé ïîñòàíîâêå ïðåäëàãàåòñÿ èñïîëüçîâàòü ìåòîäèêó, îïèñàííóþ â ïåðâîé ÷àñòè. Äëÿ ÷àñòíîãî ñëó÷àÿ ýòîé çàäà÷è ðàçðàáî- òàí ìåòîä ðåäóêöèè ìóëüòèîðãðàôà äå Áðåéíà, ïîçâîëÿþùèé ïðîâåðÿòü íàëè÷èå ðåøåíèÿ ñ ïîìîùüþ ïîèñêà ýéëåðîâûõ ïóòåé. Îïèñûâàåìûé ìåòîä åñòåñòâåííî ðàñïðîñòðàíÿåòñÿ íà ñëó÷àé íåñêîëüêèõ çàïðåùåííûõ ñëîâ, à òàêæå íà çàäà÷è ðåêîíñòðóêöèè ïðîñòðàíñòâ ñäâèãîâ êîíå÷íîãî òèïà â ñèìâîëè÷åñêîé äèíàìèêå. ÒÅÐÌÈÍÎËÎÃÈß È ÎÁÎÇÍÀ×ÅÍÈß Â òåêñòå íàñòîÿùåé ñòàòüè èñïîëüçóþòñÿ êàê îáùèå îáîçíà÷åíèÿ, ñâÿçàííûå ñ ðåêîíñòðóêöèåé ñëîâ, ââåäåííûå â ïåðâîé ÷àñòè ñòàòüè, òàê è îáîçíà÷åíèÿ, îòðàæàþùèå ñïåöèôèêó äàííîé ÷àñòè, ñîñòîÿùóþ â íàëè÷èè çàïðåùåííûõ ñëîâ. Òåì íå ìåíåå â öåëÿõ ëîãè÷åñêîé ÿñíîñòè èçëîæåíèÿ ïðèâåäåì âñå èñ- ïîëüçóåìûå îáîçíà÷åíèÿ ïîëíîñòüþ: • � � { }0 1, — áèíàðíûé àëôàâèò, s — ïðîèçâîëüíûé ñèìâîë àëôàâèòà; • �0 � � — ïóñòîå ìíîæåñòâî; • �k — k-ÿ äåêàðòîâà ñòåïåíü ìíîæåñòâà � (k-ýëåìåíòíûé êîðòåæ); • � �* � � � k k 0 � — òðàíçèòèâíîå çàìûêàíèå � (ìíîæåñòâî âñåõ âîçìîæíûõ êîðòåæåé); • c — ïðîèçâîëüíûé êîðòåæ (äëÿ êîðòåæà c îïðåäåëèì äëèíó — ÷èñëî ñî- ñòàâëÿþùèõ åãî ýëåìåíòîâ êàê ìîùíîñòü ìóëüòèìíîæåñòâà, îáðàçîâàííîãî èç êîðòåæà \| \|c n� , íàïðèìåð \| ( , , , )\|0110 4� . Äëèíà ïóñòîãî êîðòåæà ðàâíà íóëþ); • R c i( , ) — ôóíêöèÿ âûáîðà ýëåìåíòà êîðòåæà, îïðåäåëåííàÿ ïðè 1 � �i c\| \| è âîçâðàùàþùàÿ ýëåìåíò ñ íîìåðîì i èç êîðòåæà c ; åñëè i c�\| \| , òî R c i( , ) � �; åñëè ýëåìåíòû êîðòåæà ïðèíàäëåæàò � , òî ôóíêöèÿ âîçâðàùàåò ñèìâîë àëôàâè- òà, íàïðèìåð R (( , , , ), )10 01 3 0� ; • w — ñëîâî (íàä àëôàâèòîì) — ïîñëåäîâàòåëüíîñòü ñèìâîëîâ àëôàâèòà, ïðè ýòîì ñîáñòâåííî ñèìâîëû àëôàâèòà åñòü ñëîâà ïî îïðåäåëåíèþ; • � — ïóñòîå (íå ñîäåðæàùåå ñèìâîëîâ) ñëîâî; • çíàê + ïðåäñòàâëÿåò îïåðàöèþ êîíêàòåíàöèè (ñêëåéêè) ñëîâ: w w w w1 2 1 2� � ; ðåçóëüòàò îïåðàöèè + åñòü ñëîâî, ïðåäñòàâëÿþùåå ïîñëåäîâà- òåëüíîñòü ñèìâîëîâ ñëîâà w1, çà êîòîðîé ñëåäóåò ïîñëåäîâàòåëüíîñòü ñèìâîëîâ ñëîâà w2 , íàïðèìåð 01 11 0111� � ; • D D c w( ): ( ) � , ãäå c �* — êîðòåæ, w — ñëîâî; îïåðàòîð D( ) — äåñòðóê- òîð êîðòåæà, ïðåäñòàâëÿþùèé îïåðàòîð ñîçäàíèÿ ñëîâà èç êîðòåæà ïóòåì êîíêà- òåíàöèè ñèìâîëîâ àëôàâèòà � , D c w R c R c R c c( ) ( , ) ( , ) ( , \| \| )� � � � �1 2 � , íàïðèìåð D(( , , , ))1101 1101� ; • L L C W( ): ( ) � , ãäå C � �* — ìíîæåñòâî êîðòåæåé, W — ìíîæåñòâî ñëîâ; L( ) — îïåðàòîð ñîçäàíèÿ ìíîæåñòâà ñëîâ, ñîñòîÿùèõ èç ñèìâîëîâ àëôàâèòà � , êîòîðûé äåéñòâóåò íà ìíîæåñòâî êîðòåæåé ïîñðåäñòâîì ïîñëåäîâàòåëüíîãî ïðè- ìåíåíèÿ îïåðàòîðà D( ) , L C W w c C w D c( ) \| ( )� � � �{ } , íàïðèìåð L( ( , , , ), ( , , ) ) ,{ } { }1101 011 1101011� ; • w s s s Lk k� 1 2� ( )� — ïðîèçâîëüíîå ñëîâî èç ìíîæåñòâà L k( )� íàä àëôà- âèòîì � ; • \| \| \| ( ) \|w k L w� � 1 — äëèíà ñëîâà, îïðåäåëÿåìàÿ êàê ÷èñëî ýëåìåíòîâ â êîðòåæå, ïîðîæäàþùåì ýòî ñëîâî; • L L w w kk k� � �( ) \| \|� { } — ìíîæåñòâî âñåõ ñëîâ äëèíû k íàä àëôàâèòîì � ; • L L* ( )� � — ïîëíûé ÿçûê íàä àëôàâèòîì � , ò.å. ìíîæåñòâî âñåõ âîçìîæ- íûõ ñëîâ; 180 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 1 • L L� — ïðîèçâîëüíûé íåïîëíûé ÿçûê íàä àëôàâèòîì � ; • åñëè w s s s Ln n� 1 2� ( )� , òî ïðè k n� èìååì � � s s si i ik1 2 � , 1 1� i , i i2 1 1� � , ..., i i nk k� � � 1 1 , — ïîäñëîâî äëèíû k ñëîâà w ; • Q w i l( , , ) — îïåðàòîð âûäåëåíèÿ ïîäñëîâà äëèíû l â ñëîâå w , íà÷èíàÿ ñ ñèìâîëà â ïîçèöèè i ; åñëè \| \|w n� , òî îïåðàòîð îïðåäåëåí ïðè i l n� �1 : Q s s s i l u s s sn i i i l( , , )1 2 1 1� �� ; • P w Q w k s s s Lk k( ) ( , , ) ( )� � 1 1 1 2 1 1 � � — ïîëíûé ïðåôèêñ äëèíû \| \|w 1 ñëîâà w , \| \|w k� � 2 ; • S w Q w k s s Lk k( ) ( , , ) ( )� � 2 1 2 1 � � — ïîëíûé ñóôôèêñ äëèíû \| \|w 1 ñëîâà w , \| \|w k� � 2 ; • Sn w Q w k s Lk( ) ( , , ) ( )� � 1 1� — ñóôôèêñ ñëîâà w äëèíû1 — ñèìâîë àëôà- âèòà, \| \|w k� � 2 ; • V L mk( , ) — îïåðàòîð âûáîðêè: åãî ðåçóëüòàò ïðåäñòàâëÿåò ïðîèçâîëüíîå ïîäìíîæåñòâî (âîçìîæíî, ñ ïîâòîðåíèÿìè) èç m ñëîâ ìíîæåñòâà Lk : V L m i m s s s Lk i i i i k i k( , ) \| , ; ( ) ( ) ( )� � � { }� �1 1 2 � ; çàìåòèì, ÷òî ââèäó îñîáåííîñòåé çàäà÷è äîïóñêàåì ðàññìîòðåíèå V L mk( , ) êàê ìóëüòèìíîæåñòâà ñ êðàòíîñòÿìè ýëåìåíòîâ; â ýòîì ñëó÷àå m — ñóììà êðàò- íîñòåé ýëåìåíòîâ; • SH w k1( , ) — îïåðàòîð ñäâèãà 1; îïåðàòîð, îïðåäåëåííûé ïðè \| \|w k� , ïî- ðîæäàåò ìíîæåñòâî ïîäñëîâ äëèíû k ìîùíîñòè \| \|w k �1, âûïîëíÿÿ ñäâèã íà åäè- íèöó îêíà äëèíû k ïî ñëîâó w , íà÷èíàÿ ñ êðàéíåé ëåâîé ïîçèöèè ñëîâà w : SH w k u j w k u Q w j kj j1 1 1( , ) \| , \| \| ; ( , , )� � � �{ } ; äëÿ îïåðàòîðà SH w k1( , ) äîïóñêàåì ñîçäàíèå ìóëüòèìíîæåñòâà, íàïðèìåð SH1 1101010 4 1101 1010 0101 1010 1101 1010 2( , ) , , , , ( )� �{ } { , 0101} ; • � — çàïðåùåííîå ñëîâî; w \ � — îïåðàöèÿ «êîëëàïñà» — ïðè î÷åâèäíîì óñëîâèè \| \| \| \|w � � ðåçóëüòàòîì îïåðàöèè ÿâëÿåòñÿ èëè ñëîâî w, åñëè îíî íå ñîäåð- æèò çàïðåùåííîãî ïîäñëîâà �, èëè �, åñëè ñëîâî w ñîäåðæèò �: w w j w Q w j j Q w j \ , \| \| \| \| : ( , , \| \| ) , , : ( , , \| \| ) � � � � � � � � � � � � � � 1 1 ; � � � • � ( , )L � — îïåðàòîð ðåäóêöèè ÿçûêà L ïî çàïðåòó �. Äîïóñêàåì, ÷òî ÿçûê L ìîæåò áûòü ìóëüòèìíîæåñòâîì, îïåðàòîð � ( , )L � , äåéñòâóÿ íà ÿçûê L , îñòàâëÿåò òîëüêî òå ñëîâà èç ÿçûêà L , êîòîðûå íå ñîäåðæàò çàïðåùåííîãî ñëîâà � : � ( , ) \| \L u u w w L� �� { } , îáîçíà÷èì L \ � ÿçûê L , ðåäóöèðîâàííûé ïî çàïðåòó �; òàêèì îáðàçîì, L L\ ( , )� �� . ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È ÐÅÊÎÍÑÒÐÓÊÖÈÈ ÏÐÈ ÍÀËÈ×ÈÈ ÇÀÏÐÅÙÅÍÍÎÃÎ ÑËÎÂÀ Êàê è â [1], ñ÷èòàåì çàäàííûìè äëèíó ïîäñëîâà k , ÷èñëî ïîäñëîâ m è èñõîä- íîå ìóëüòèìíîæåñòâî ñëîâ V L mk( , ) íàä àëôàâèòîì � � { }0 1, , ðàññìàòðèâàåìîå êàê áàçèñ ðåêîíñòðóêöèè, ò.å. êàê ìóëüòèìíîæåñòâî ïîäñëîâ ñäâèãà 1 îòíîñè- òåëüíî íåêîòîðîãî íåèçâåñòíîãî ñëîâà w . Äàëåå, â ïîñòàíîâêå 2, çàäàíî åäèí- ñòâåííîå çàïðåùåííîå ñëîâî � äëÿ ðåêîíñòðóèðóåìûõ ñëîâ w . Îòìåòèì, ÷òî ôîðìóëèðîâêà ïîñòàíîâêè 2 òåñíî ñâÿçàíà ñ ïîñòàíîâêîé 1. Ïîñòàíîâêà 1. Çàäà÷à ðåêîíñòðóêöèè áåç çàïðåòîâ. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 1 181 Ñîäåðæàòåëüíî. Â óñëîâèÿõ ãèïîòåçû ñäâèãà 1 îòíîñèòåëüíî ìóëüòèìíî- æåñòâà V L mk( , ) âîçìîæíî ëè âûïîëíèòü ðåêîíñòðóêöèþ ñëîâà w â ïðèíöèïå, è åñëè ýòà çàäà÷à èìååò ðåøåíèå, òî êàêîé âèä èìåþò âîçìîæíûå ðåêîíñòðóêöèè? Ôîðìàëüíî. Ââåäåì â ðàññìîòðåíèå ìíîæåñòâî W w w m k V L m SH w kk� � � �{ }\| \| , ( , ) ( , )1 1 ; (1) ïðè ýòîì âûðàæåíèå (1) ïîíèìåòñÿ êàê ðàâåíñòâî ìóëüòèìíîæåñòâ (ðàâíû êàê ýëåìåíòû, òàê è èõ êðàòíîñòè). Òîãäà åñëè \| \|W � 0 , òî ðåøåíèÿ íåò (ðåêîíñòðóê- öèÿ ñëîâ íåâîçìîæíà); åñëè \| \|W � 1, òî ðåøåíèå åñòü (ðåêîíñòðóêöèÿ âîçìîæíà). Â äàëüíåéøåì âîçìîæíûå ðåøåíèÿ çàäà÷è â ïîñòàíîâêå 1 áóäåì íàçûâàòü ïðîñòûìè ðåøåíèÿìè çàäà÷è ðåêîíñòðóêöèè. Ïîñòàíîâêà 2. Çàäà÷à ðåêîíñòðóêöèè ñ çàïðåòîì. Ñîäåðæàòåëüíî. Â óñëîâèÿõ ãèïîòåçû ñäâèãà 1 îòíîñèòåëüíî ìóëüòèìíî- æåñòâà V L mk( , ) âîçìîæíà ëè â ïðèíöèïå ðåêîíñòðóêöèÿ òàêîãî ñëîâà èëè ñëîâ w , êîòîðûå íå ñîäåðæàò ñëîâà � â êà÷åñòâå ïîäñëîâà, è êàêîé âèä èìåþò ýòè ðåêîíñòðóèðóåìûå ñëîâà? Ôîðìàëüíî. Ââåäåì â ðàññìîòðåíèå àíàëîãè÷íî ïîñòàíîâêå 1 ìíîæåñòâî W W\ ( , )� �� , ãäå W îïðåäåëåíî â ñîîòâåòñòâèè ñ (1). Òîãäà, ðàññìàòðèâàÿ ñîâìåñòíî ìíîæåñòâà W è W \ � , âûäåëèì ñëåäóþùèå ñëó÷àè. Ñëó÷àé 1. \| \|W � 0 — ìíîæåñòâî ïðîñòûõ ðåøåíèé çàäà÷è ðåêîíñòðóêöèè ïóñòî, è î÷åâèäíî, ÷òî \| \ \|W � � 0 , òîãäà ìíîæåñòâîV L mk( , ) â ïðèíöèïå íå ÿâëÿ- åòñÿ ðåêîíñòðóèðóþùèì. Ñëó÷àé 2. \| \|W � 1è \| \ \|W � � 0 — ðåøåíèÿ â ïîñòàíîâêå 2 íåò, âñå ïðîñòûå ðå- êîíñòðóêöèè ñîäåðæàò çàïðåùåííîå ñëîâî. Òàêèì îáðàçîì, ðåêîíñòðóêöèÿ íà áàçå V L mk( , ) áåç çàïðåùåííîãî ñëîâà � íåâîçìîæíà. Ñëó÷àé 3. \| \|W � 1 è \| \| \| \ \|W W� � — ðåøåíèå â ïîñòàíîâêå 2 ñóùåñòâóåò, è âñå ïðîñòûå ðåêîíñòðóêöèè íå ñîäåðæàò çàïðåùåííîãî ñëîâà; òîãäà ìóëüòèìíîæåñòâî V L mk( , ) äîñòàâëÿåò ïîëíîå ðåøåíèå çàäà÷è ðåêîíñòðóêöèè â ïîñòàíîâêå 2, êîòîðîå ñîâïàäàåò ñ ïðîñòûì ðåøåíèåì â ïîñòàíîâêå 1. Çàìåòèì, ÷òî ýòîò ñëó÷àé ýêâèâàëåí- òåí ðåêîíñòðóêöèè èç ïðîñòðàíñòâà ñäâèãîâ, îïðåäåëÿåìîãî çàïðåùåííûì ñëîâîì. Ñëó÷àé 4. \| \|W � 1 è \| \| \| \ \|W W� � — ðåøåíèå â ïîñòàíîâêå 2 ñóùåñòâóåò, íî åñòü òàêèå ïðîñòûå ðåêîíñòðóêöèè, êîòîðûå ñîäåðæàò çàïðåùåííîå ñëîâî; òîãäà ìóëüòèìíîæåñòâî V L mk( , ) äîñòàâëÿåò ÷àñòè÷íîå ðåøåíèå çàäà÷è ðåêîíñòðóêöèè â ïîñòàíîâêå 2. Â ýòîì ñëó÷àå ïðåäñòàâëÿåò èíòåðåñ ïîëó÷åíèå êàê òî÷íîãî ÷èñ- ëà ðåøåíèé M W� �� \| \ \| , òàê è ñàìèõ ðåøåíèé çàäà÷è — ìíîæåñòâà ñëîâ W \ �. ÎÑÎÁÅÍÍÎÑÒÈ ÏÎÑÒÀÍÎÂÊÈ 2 È ÒÐÈÂÈÀËÜÍÛÅ ÑËÓ×ÀÈ Îñîáåííîñòè ïîñòàíîâêè 2 ñâÿçàíû íå òîëüêî ñ íàëè÷èåì ñàìîãî çàïðåùåííîãî ñëîâà � , íî è ñ ñîîòíîøåíèÿìè ìåæäó åãî äëèíîé è äëèíàìè ðåêîíñòðóèðóþ- ùèõ è ðåêîíñòðóèðóåìûõ ñëîâ. Â öåëÿõ èçëîæåíèÿ ýòèõ îñîáåííîñòåé îáîçíà÷èì n äëèíó çàïðåùåííîãî ñëîâà � è îòìåòèì, ÷òî äëèíû âñåõ ïîäñëîâ â ìóëüòèìíî- æåñòâå V L mk( , ) ðàâíû k, à äëèíà ðåêîíñòðóèðóåìûõ ñëîâ w W , åñëè V L mk( , ) ÿâëÿåòñÿ ðåêîíñòðóèðóþùèì ïîäìíîæåñòâîì, ðàâíà r w m k� � � \| \| 1 . Â çàâèñèìîñòè îò ñîîòíîøåíèé ìåæäó óêàçàííûìè äëèíàìè âîçíèêàþò âà- ðèàíòû, ïðèâîäÿùèå ê ðàçëè÷íûì ñëó÷àÿì ðåøåíèÿ â ïîñòàíîâêå 2. Äàëåå ïîä òðèâèàëüíûìè ñëó÷àÿìè áóäåì ïîíèìàòü òàêèå ðåøåíèÿ, êîòîðûå âûïîëíÿþòñÿ ñ íåçíà÷èòåëüíûìè âû÷èñëèòåëüíûìè çàòðàòàìè, ò.å. ñ ìàëîé òðóäîåìêîñòüþ. Ïðè ýòîì ïîëíîå èññëåäîâàíèå ìíîæåñòâà W íå ñ÷èòàåì òðèâèàëüíûì ñëó÷àåì, òàê êàê ñàìî ïîëó÷åíèå ìíîæåñòâà ðåêîíñòðóèðóåìûõ ñëîâ ñâÿçàíî ñ ïåðå÷èñëå- íèåì âñåõ ýéëåðîâûõ ïóòåé íà îñíîâå ñïåöèàëüíîãî ñèìâîëüíîãî âîçâåäåíèÿ â ñòåïåíü ìàòðèöû ñòîèìîñòåé, ïîäðîáíî îïèñàííîãî â [1]. Ðàññìîòðèì â ðàçâåðíóòîì âèäå òðèâèàëüíûé ñëó÷àé è âàðèàíòû, âîçíèêàþ- ùèå â ïîñòàíîâêå 2. Ïóñòü \| \|W � 0 — ðåøåíèÿ çàäà÷è â ïîñòàíîâêå 1 íå ñóùåñòâóåò è, î÷åâèäíî, íåò ðåøåíèé â ïîñòàíîâêå 2. Ýòîò ñëó÷àé ýëåìåíòàðíî èäåíòèôèöèðóåòñÿ ïðîâåð- 182 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 1 êîé ñóùåñòâîâàíèÿ ýéëåðîâà ïóòè (öèêëà), ïîëó÷åííîì â ïîñòàíîâêå I ìóëüòèîð- ãðàôà äå Áðåéíà [4]. Íàëè÷èå ýéëåðîâà öèêëà (èëè ïóòè) óñòàíàâëèâàåòñÿ ÷åðåç ïîäñ÷åò ïîëóñòåïåíåé çàõîäà è âûõîäà âåðøèí ìóëüòèîðãðàôà ([5], ñ. 145) è òðå- áóåò íå áîëåå ÷åì îäíîêðàòíîãî ïðîõîäà ïî ìàòðèöå ñìåæíîñòè ìóëüòèîðãðàôà äå Áðåéíà. Ñëîæíîñòü òàêîé ïðîâåðêè îöåíèâàåòñÿ êàê O m( )2 . Äàëåå ðàññìîòðèì âàðèàíòû, âîçíèêàþùèå ïðè íàëè÷èè ïðîñòîé ðåêîí- ñòðóêöèè, ò.å. íàëè÷èè ýéëåðîâà ïóòè â ìóëüòèîðãðàôå äå Áðåéíà, îáåñïå÷èâàþ- ùåãî âûïîëíåíèå óñëîâèÿ \| \|W � 1 (ñëó÷àè 2-4). Ýòè âàðèàíòû èäåíòèôèöèðóþòñÿ ñëåäóþùèìè ñîîòíîøåíèÿìè ìåæäó çíà÷åíèÿìè äëèí n , k è r . Âàðèàíò À. Äëèíà n çàïðåùåííîãî ñëîâà áîëüøå äëèíû r ðåêîíñòðóèðóåìî- ãî ñëîâà (n r� ) . Òîãäà ïîëó÷àåì âàðèàíò ñëó÷àÿ 3: \| \|W � 1 è \| \| \| \ \|W W� � — âñå âîçìîæíûå ðåêîíñòðóêöèè íå ñîäåðæàò çàïðåùåííîãî ñëîâà � , è ðåøåíèå äëÿ ïîñòàíîâêè 2 äîñòàâëÿåòñÿ ïðîñòîé ðåêîíñòðóêöèåé. Âàðèàíò èäåíòèôèöèðóåòñÿ çà O( )1 îïåðàöèé. Âàðèàíò Á. Äëèíà n çàïðåùåííîãî ñëîâà ìåíüøå äëèíû k ñëîâ (n k� ) èç èñ- õîäíîãî ìóëüòèìíîæåñòâà V L mk( , ) . Äëÿ èññëåäîâàíèÿ ýòîãî âàðèàíòà ðàññìîò- ðèì ìíîæåñòâî èç ïîäñëîâ äëèíû n , ïîëó÷åííûõ ñäâèãîì 1 ïî âñåì ñëîâàì èç V L mk( , ) : U SH n V L mi i m i k� � 1 1 ( , ), ( , )� �� . Òîãäà åñëè � U , òî èìååò ìåñòî ñëó÷àé 2: \| \|W � 1 , \| \ \|W � � 0 — ðåøåíèÿ â ïîñòàíîâêå 2 íåò, âñå ïðîñòûå ðåêîíñòðóêöèè ñîäåðæàò çàïðåùåííîå ñëîâî, ïîñêîëüêó îíî ÿâëÿåòñÿ ïîäñëîâîì îäíîãî èç ñëîâ èñõîäíîãî ìíîæåñòâà V L mk( , ); åñëè � �U , òî \| \| \| \ \|W W� � è ïîëó÷àåì âàðèàíò ñëó÷àÿ 3: \| \|W � 1 , \| \| \| \ \|W W� � — âñå âîçìîæíûå ïðîñòûå ðåêîíñòðóêöèè íå ñîäåðæàò çàïðåùåí- íîãî ñëîâà è ìíîæåñòâî W äîñòàâëÿåò ðåøåíèå äàííîé çàäà÷è â ïîñòàíîâêå 2. Ñëîæíîñòü ïðîâåðêè âàðèàíòà Á îïðåäåëÿåòñÿ ñëîæíîñòüþ ïîñòðîåíèÿ ìíî- æåñòâà U , êîòîðàÿ îöåíèâàåòñÿ êàê O kmn mn mn( ) �2 îïåðàöèé íàä ñèìâîëàìè, ïîñêîëüêó ñäâèã íåîáõîäèìî âûïîëíèòü äëÿ âñåõ m ñëîâ èç V L mk( , ) è äëÿ êàæ- äîãî èç íèõ ïîëó÷èòü k n �1 ïîäñëîâ ñäâèãà 1, èìåþùèõ äëèíó n. Âàðèàíò Â. Äëèíà n çàïðåùåííîãî ñëîâà ðàâíà äëèíå k ïîäñëîâ (n k� ) èç V L mk( , ) ; òîãäà ïðîâåðÿåì, ÿâëÿåòñÿ ëè � ýëåìåíòîì ìóëüòèìíîæåñòâà V L mk( , ) . Åñëè � V L mk( , ) , òî èìååò ìåñòî ñëó÷àé 2: \| \|W � 1, \| \ \|W � � 0 — ðåøåíèÿ â ïîñòàíîâêå 2 íåò, âñå ïðîñòûå ðåêîíñòðóêöèè ñîäåðæàò çàïðåùåííîå ñëîâî, ïîñêîëüêó îíî ÿâëÿåòñÿ îäíèì èç ñëîâ èñõîäíîãî ìóëüòèìíîæåñòâà V L mk( , ) . Åñëè � �V L mk( , ) , òî \| \| \| \ \|W W� � è ïîëó÷àåì âàðèàíò ñëó÷àÿ 3: \| \|W � 1è \| \| \| \ \|W W� � — âñå âîçìîæíûå ðåêîíñòðóêöèè íå ñîäåðæàò çàïðåùåííîãî ñëîâà è ìíîæåñòâî W îïðåäåëÿåò ðåøåíèå äëÿ ïîñòàíîâêè 2. Òðóäîåìêîñòü ïðîâåðêè âàðèàíòà B îïðåäåëÿåòñÿ ñëîæíîñòüþ ïðîâåðêè âõîæäåíèÿ � â ìóëüòèìíîæåñòâî V L mk( , ) , ò.å. ñîñòàâëÿåò O mn( ) ñèìâîëüíûõ îïåðàöèé. ÐÅØÅÍÈÅ ÏÎÑÒÀÍÎÂÊÈ 2 ÏÅÐÅ×ÈÑËÅÍÈÅÌ ÂÑÅÕ ÝÉËÅÐÎÂÛÕ ÏÓÒÅÉ Ñîîòíîøåíèå äëèí k n r� � ïðèâîäèò ê íåòðèâèàëüíîìó âàðèàíòó ïîñòàíîâ- êè 2. Î÷åâèäíûé ïóòü èññëåäîâàíèÿ äëÿ ýòîãî âàðèàíòà — ðåøåíèå ïîñòàíîâ- êè 1 ñ ïîñëåäóþùåé ïðîâåðêîé âõîæäåíèÿ çàïðåùåííîãî ñëîâà â ìíîæåñòâî ñëîâ ðåêîíñòðóêöèè. Ôàêòè÷åñêè ýòî ïåðåáîðíîå ðåøåíèå äëÿ ïîñòàíîâêè 2 íà îñíîâå ðåøåíèÿ â ïîñòàíîâêå 1 âêëþ÷àåò òðè ýòàïà. 1. Ðåøåíèå ïîñòàíîâêè 1 ïóòåì ïåðå÷èñëåíèÿ âñåõ ýéëåðîâûõ ïóòåé íà îñíî- âå ñïåöèàëüíîãî ñèìâîëüíîãî âîçâåäåíèÿ â ñòåïåíü ìàòðèöû ñìåæíîñòè, îïèñàí- íîãî â ïåðâîé ÷àñòè ñòàòüè. Â ðåçóëüòàòå ïîëó÷àåì ìíîæåñòâî ñëîâ W, ÿâëÿþ- ùèõñÿ ïðîñòûìè ðåêîíñòðóêöèÿìè áåç çàïðåòîâ. 2. Ïîñòðîåíèå ìíîæåñòâà ñëîâ, íå ñîäåðæàùèõ çàïðåùåííîãî ñëîâà, ïó- òåì ïðèìåíåíèÿ îïåðàòîðà � (îïåðàòîðà ðåäóêöèè ÿçûêà) ñ çàïðåòîì � ê ìíî- ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 1 183 æåñòâó W, ò.å. ïðîâåðêè âõîæäåíèÿ çàïðåùåííîãî ñëîâà â ìíîæåñòâî ðåêîí- ñòðóêöèè. Â ðåçóëüòàòå ïîëó÷àåì ìíîæåñòâî ðåêîíñòðóêöèé áåç çàïðåùåííî- ãî ñëîâà: W W\ ( , )� �� . 3. Èäåíòèôèêàöèÿ âñåõ âîçìîæíûõ ÷åòûðåõ ñëó÷àåâ â ïîñòàíîâêå 2 çàäà÷è ðåêîíñòðóêöèè ïðè íàëè÷èè çàïðåùåííîãî ñëîâà ïóòåì ñðàâíåíèÿ ìîùíîñòè ìíîæåñòâ W è W \ � . Â ðàìêàõ òàêîãî ðåøåíèÿ âûäåëèì âàðèàíò, êîãäà n r� , ò.å. äëèíà n çàïðå- ùåííîãî ñëîâà ðàâíà äëèíå r ðåêîíñòðóèðóåìîãî ñëîâà, è ïðîâåðÿåì, ÿâëÿåòñÿ ëè � ýëåìåíòîì ìíîæåñòâà ïðîñòûõ ðåêîíñòðóêöèé W . Ïðè ýòîì åñëè � W, òî èìååò ìåñòî ñëó÷àé 4: \| \|W � 1 è \| \| \| \ \|W W� � — ìóëüòèìíîæåñòâî V L mk( , ) äîñòàâ- ëÿåò ÷àñòè÷íîå ðåøåíèå çàäà÷è ðåêîíñòðóêöèè â ïîñòàíîâêå 2. Îñîáåííîñòü äàí- íîãî âàðèàíòà ñîñòîèò â òîì, ÷òî â ìíîæåñòâå W åñòü òîëüêî îäíî çàïðåùåííîå ñëîâî � , è ñëåäîâàòåëüíî M W� � \| \| 1 . Åñëè � �W, òî \| \| \| \ \|W W� � è ïîëó÷àåì âàðèàíò ñëó÷àÿ 3: \| \|W � 1è \| \| \| \ \|W W� � — âñå âîçìîæíûå ðåêîíñòðóêöèè íå ñîäåð- æàò çàïðåùåííîãî ñëîâà è ìíîæåñòâî W îïðåäåëÿåò ðåøåíèå äëÿ ïîñòàíîâêè 2. Ïðè îïðåäåëåííûõ óñëîâèÿõ ðåøåíèå äëÿ ïîñòàíîâêè 2 ìîæåò áûòü ïîëó÷å- íî ñ ìåíüøåé òðóäîåìêîñòüþ, ÷åì ÷åðåç ïðÿìîå ðåøåíèå çàäà÷è ðåêîíñòðóêöèè áåç çàïðåòîâ. Âàðèàíò òàêîãî ÷àñòè÷íîãî ðåøåíèÿ, îñíîâàííûé íà ñïåöèàëüíîé ïðîöåäóðå ðåäóêöèè ìóëüòèîðãðàôà äå Áðåéíà, ïðåäñòàâëåí íèæå. ÐÅØÅÍÈÅ Â ×ÀÑÒÍÛÕ ÑËÓ×ÀßÕ ÍÀ ÎÑÍÎÂÅ ÐÅÄÓÊÖÈÈ ÃÐÀÔÀ ÄÅ ÁÐÅÉÍÀ Ðàññìîòðèì íåòðèâèàëüíûé âàðèàíò \| \|W � 1 ïðè ñîîòíîøåíèè äëèí k n r� � è ââåäåì ñïåöèàëüíóþ ïðîöåäóðó ðåäóêöèè ìóëüòèîðãðàôà äå Áðåéíà G D H� ( , ) , ïîñòðîåííîãî íà îñíîâå ìóëüòèìíîæåñòâà V L mk( , ) . Îòìåòèì, ÷òî äóãè hi â G îïèñûâàþòñÿ ïÿòåðêîé h d d e r pi j l i i i� ( , , , , )� , ãäå d j — íà÷àëü- íàÿ âåðøèíà äóãè, dl — êîíå÷íàÿ âåðøèíà äóãè, ei — ñèìâîëè÷åñêîå èìÿ äóãè, ri — êðàòíîñòü, �pi — çíà÷åíèå ñëîâà èç V L mk( , ) . Ïðîöåäóðà ðåäóêöèè âêëþ÷àåò ñëåäóþùèå äâà ýòàïà. Ýòàï 1. Ïîèñê çàïðåùåííîãî ñëîâà â ìóëüòèîðãðàôå äå Áðåéíà. 1. Ñòðîèì óïîðÿäî÷åííîå ìóëüòèìíîæåñòâî Q ïîäñëîâ äëèíû k èç çàïðå- ùåííîãî ñëîâà ïîñðåäñòâîì îïåðàòîðà ñäâèãà 1: Q SH k q ii� � �1 1( , ) \|� { , n k �1} . 2. Ïîëàãàåì i �1 è ïðèñâàèâàåì êîðòåæó t çíà÷åíèå ïóñòî. 3. Èùåì â G D H� ( , ) äóãó h j , äëÿ êîòîðîé R h qj i( , )5 � , ò.å. äóãó, çíà÷åíèå êîòîðîé ñîâïàäàåò ñ i-ì ñäâèãîì ïî çàïðåùåííîìó ñëîâó. Åñëè òàêîé äóãè íåò, òî èìååì âàðèàíò ñëó÷àÿ 3: \| \|W � 1 è \| \| \| \ \|W W� � , è ðåøàåì çàäà÷ó â ïîñòàíîâêå 1. Â ýòîì ñëó÷àå ýòàï 1 çàêîí÷åí. Åñëè òàêàÿ äóãà åñòü, òî äîáàâëÿåì â êîðòåæ t ýëå- ìåíò h j : t t h j� � è ïðîäîëæàåì ýòàï 1. 4. Óâåëè÷èâàåì çíà÷åíèå i i� �1è ïåðåõîäèì ê øàãó 3 äëÿ âñåõ i n k� �1 . 5. Ïóòü ïî äóãàì, îïèñûâàåìûé êîðòåæåì t , ïîðîæäàåò çàïðåùåííîå ñëîâî. Ýòàï 2. Ñîáñòâåííî ðåäóêöèÿ ìóëüòèîðãðàôà G D H� ( , ) . Ïî ìóëüòèîðãðàôó G D H� ( , ) ñòðîèì ðåäóöèðîâàííûé ìóëüòèîðãðàô G D H� � �( , ) ñëåäóþùèì îáðàçîì. 1. Ïî âñåì ýëåìåíòàì êîðòåæà t , ò.å. ïî âñåì h i n ki , ,� �1 1, (íóìåðàöèÿ â ïîðÿäêå ïîñòðîåíèÿ êîðòåæà) âûïîëíÿåì ðåäóêöèþ ðåáåð: h d d e r p h d d e r pi j l i i i i j l i i i� � � � ( , , , , ) ( , , , , )� �1 ; åñëè ri �1 0 , òî ñ÷èòàåì, ÷òî äóãà hi óäàëåíà èç G� . 2. Äîáàâëÿåì â ãðàô G D H� � �( , ) íîâóþ äóãó, èìåþùóþ çíà÷åíèå çàïðåùåí- íîãî ñëîâà è ñîåäèíÿþùóþ íà÷àëüíóþ è êîíå÷íóþ âåðøèíû íàéäåííîãî ïóòè: H H h h R R t R R t n k e� � �� * * *, ( ( ( , ), ), ( ( , ), ), , , )1 1 1 2 1 � . Êîíåö ïðîöåäóðû. 184 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 1 Çàìåòèì, ÷òî ñàìà ïðîöåäóðà ðåäóêöèè èìååò ìàëóþ òðóäîåìêîñòü, ïî- ñêîëüêó íà ýòàïå 1 ïðîèñõîäèò ïðîñìîòð âñåõ m äóã â G D H� ( , ) äëÿ ïîèñêà ïîäñëîâà q1 äëèíû n è íå áîëåå äâóõ äóã íà âñåõ ïîñëåäóþùèõ n k øàãàõ, ýòî äàåò îöåíêó ñëîæíîñòè O mn n kn( )� 2 22 äëÿ ýòàïà 1, à ýòàï 2, ÷òî î÷åâèäíî, íå óâåëè÷èâàåò ýòó ñëîæíîñòü. Èññëåäîâàíèå ðåäóöèðîâàííîãî ìóëüòèîðãðàôà G D H� � �( , ) ïîçâîëÿåò ïîëó- ÷èòü íåêîòîðóþ èíôîðìàöèþ î ðåøåíèÿõ ïîñòàíîâêè 2. Îòìåòèì, ÷òî íàéäåí- íûé â ïðîöåäóðå ðåäóêöèè ïóòü, îòðàæàþùèé çàïðåùåííîå ñëîâî, åùå íå ÿâëÿ- åòñÿ ãàðàíòèåé òîãî, ÷òî ýéëåðîâ ïóòü (öèêë) ïðîõîäèò èìåííî â òàêîé ïîñëåäî- âàòåëüíîñòè ïî ýòèì äóãàì. Ïîýòîìó íåîáõîäèìî èññëåäîâàíèå íàëè÷èÿ ýéëåðîâîãî ïóòè (öèêëà) â G D H� � �( , ) . Íàëè÷èå â G D H� � �( , ) ýéëåðîâà ïóòè (ýéëåðîâà öèêëà) îïðåäåëÿåò ñóùå- ñòâîâàíèå ðåøåíèÿ çàäà÷è ðåêîíñòðóêöèè, âêëþ÷àþùåãî çàïðåùåííîå ñëîâî. Ïîñêîëüêó ïðè ðåäóêöèè äëÿ âñåõ âåðøèí ñîõðàíÿåòñÿ ñîîòíîøåíèå ìåæäó ïî- ëóñòåïåíÿìè çàõîäà è âûõîäà âåðøèí, òî èñõîäíûé ýéëåðîâ ìóëüòèîðãðàô G D H� ( , ) , ïðåîáðàçîâàííûé ïðîöåäóðîé ðåäóêöèè â G D H� � �( , ) , ëèáî îñòàåòñÿ ãðàôîì ñ ýéëåðîâûì ïóòåì (öèêëîì) è, âîçìîæíî, ñîäåðæèò èçîëèðîâàííûå âåð- øèíû, ëèáî ñòàíîâèòñÿ íåñâÿçíûì ãðàôîì ñ íåñêîëüêèìè êîìïîíåíòàìè, êàæäàÿ èç êîòîðûõ ÿâëÿåòñÿ ýéëåðîâûì ãðàôîì. Â ïåðâîì ñëó÷àå çàäà÷à ðåêîíñòðóêöèè èìååò ðåøåíèÿ, âêëþ÷àþùèå çàïðåùåí- íîå ñëîâî, ïðè ýòîì íåèçâåñòíî — åñòü ëè ðåøåíèÿ, íå ñîäåðæàùèå çàïðåòà; äëÿ îò- âåòà íà ýòîò âîïðîñ íåîáõîäèìî ïîëíîå èññëåäîâàíèå ÷åðåç ðåøåíèå â ïîñòàíîâêå 1. Âî âòîðîì ñëó÷àå çàäà÷à ðåêîíñòðóêöèè íå èìååò ðåøåíèé, ñîäåðæàùèõ çà- ïðåùåííîå ñëîâî: \| \|W � 1 è \| \| \| \ \|W W� � . Îñîáî îòìåòèì, ÷òî ýòîò ñëó÷àé íåâîçìî- æåí, åñëè êðàòíîñòü âñåõ äóã â ïóòè, ñîîòâåòñòâóþùåì çàïðåùåííîìó ñëîâó â èñõîäíîì ìóëüòèîðãðàôå G D H� ( , ) , áîëüøå èëè ðàâíà äâóì. Ïðè ýòîì óñëîâèè íåò íåîáõîäèìîñòè ïðîâåðÿòü íàëè÷èå ýéëåðîâà ïóòè (öèêëà) â ðåäóöèðîâàííîì ãðàôå, ïîñêîëüêó ýòî î÷åâèäíî. Òàêèì îáðàçîì, ïðåäëîæåííàÿ ïðîöåäóðà ðåäóêöèè ïîçâîëÿåò ñ ìàëîé òðó- äîåìêîñòüþ èäåíòèôèöèðîâàòü ÷àñòíûé ñëó÷àé îòñóòñòâèÿ ðåøåíèé, ñîäåðæà- ùèõ çàïðåùåííîå ñëîâî, ÷òî ïðåäñòàâëÿåò, â ÷àñòíîñòè, èíòåðåñ îòíîñèòåëüíî ñèìâîëè÷åñêîé äèíàìèêå [3] è ðÿäå ïðèëîæåíèé [6–10]. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 1 185 1 1 2 2 1 Ðèñ. 1. Èñõîäíûé ìóëüòèîðãðàô äå Áðåéíà — äóãè çàïðåùåííîãî ñëîâà èìåþò êðàòíîñòü äâà 1 1 1 1 1 � Ðèñ. 2. Ðåäóöèðîâàííûé ìóëüòèîðãðàô äå Áðåéíà — íàëè÷èå ýéëåðîâîãî öèêëà ïðèâîäèò ê ðåøåíèÿì, âêëþ÷àþùèì çàïðåùåííîå ñëîâî � 1 1 1 1 Ðèñ. 3. Èñõîäíûé ìóëüòèîðãðàô äå Áðåéíà — äóãè çàïðåùåííîãî ñëîâà èìåþò êðàòíîñòü îäèí 1 1 Ðèñ. 4. Ðåäóöèðîâàííûé ìóëüòèîðãðàô äå Áðåéíà íå èìååò ýéëåðîâûõ ïóòåé (öèêëîâ) — íåò ðåêîíñòðóêöèé, âêëþ÷àþùèõ çàïðåùåííîå ñëîâî � Ïðîèëëþñòðèðóåì ïðîöåäóðó ðåäóêöèè, ðàññìàòðèâàÿ òîëüêî ñòðóêòóðó ãðà- ôîâ ñ óêàçàíèåì êðàòíîñòè äóã. Æèðíûì âûäåëåíû äóãè, ïðåäñòàâëÿþùèå çàïðå- ùåííîå ñëîâî. Öèôðû íàä äóãàìè ñîîòâåòñòâóþò êðàòíîñòè âõîæäåíèÿ ïîäñëîâ â ñëîâî. Íà ðèñ. 1 è 2 ïðèâåäåí ñëó÷àé, êîãäà â ìóëüòèîðãðàôå G D H� � �( , ) ïîñëå ðåäóêöèè ñîõðàíÿåòñÿ ýéëåðîâ öèêë è, ñëåäîâàòåëüíî, åñòü ðåêîíñòðóêöèè, ñî- äåðæàùèå çàïðåùåííîå ñëîâî. Íà ðèñ. 3 è 4 ïðèâîäèòñÿ ñëó÷àé, êîãäà â ðåäóöè- ðîâàííîì ãðàôå ïðîïàäàþò ýéëåðîâû ïóòè (öèêëû) è ãðàô ñòàíîâèòñÿ íåñâÿç- íûì — â ðåøåíèè ïîñòàíîâêè 2 íåò ðåêîíñòðóêöèé ñ çàïðåùåííûì ñëîâîì. ÇÀÊËÞ×ÅÍÈÅ Â íàñòîÿùåé ñòàòüå ðàññìîòðåíà ïîñòàíîâêà 2 çàäà÷è ðåêîíñòðóêöèè ïî çàäàííî- ìó ìóëüòèìíîæåñòâó ïîäñëîâ, ïðåäïîëîæèòåëüíî ïîðîæäåííûõ ñìåùåíèåì îêíà ôèêñèðîâàííîé äëèíû ñî ñäâèãîì 1 ïî íåêîòîðîìó ñëîâó. Îñîáåííîñòü ýòîé ïî- ñòàíîâêè ñîñòîèò â íàëè÷èè çàïðåùåííîãî ñëîâà â ðåêîíñòðóêöèè. Ïðèíÿòûé â ïåðâîé ÷àñòè îïåðàòîðíûé ïîäõîä ðàñøèðåí íà îïèñàíèå îïåðàöèé ñ çàïðåùåí- íûìè ñëîâàìè. Ðàññìîòðåíû ÷åòûðå âîçìîæíûõ ñëó÷àÿ ðåøåíèÿ çàäà÷è ðåêîí- ñòðóêöèè â ïîñòàíîâêå 2, ñïåöèàëüíî âûäåëåíû è èññëåäîâàíû òðèâèàëüíûå ñëó- ÷àè. Ïðåäëîæåí âàðèàíò ïîëíîãî ðåøåíèÿ çàäà÷è, îñíîâàííûé íà ðåøåíèè ïîñòà- íîâêè 1 ïóòåì ïåðå÷èñëåíèÿ âñåõ ýéëåðîâûõ ïóòåé (öèêëîâ) â ìóëüòèîðãðàôå äå Áðåéíà ñ ïðèìåíåíèåì ñïåöèàëüíûõ àëãåáðàè÷åñêèõ îïåðàöèé óìíîæåíèÿ ìàòðèö ñìåæíîñòè, îïðåäåëåííûõ â ïåðâîé ÷àñòè ñòàòüè. Äîïîëíèòåëüíî ïðåäëîæåí âà- ðèàíò ÷àñòè÷íîãî ðåøåíèÿ, îñíîâàííûé íà ââåäåííîé àâòîðàìè ïðîöåäóðå ðåäóê- öèè è ïîñëåäóþùåì èññëåäîâàíèè ðåäóöèðîâàííîãî ìóëüòèîðãðàôà äå Áðåéíà. Ðàññìîòðåííûé ìåòîä ïîçâîëÿåò ýôôåêòèâíî ñ ó÷åòîì òðóäîåìêîñòè èäåíòèôè- öèðîâàòü ñëó÷àé îòñóòñòâèÿ çàïðåùåííîãî ñëîâà â ìíîæåñòâå ñëîâ ðåêîíñòðóêöèè. Ýòîò ñëó÷àé ïðåäñòâàëÿåò îïðåäåëåííûé èíòåðåñ, ïîñêîëüêó îñíîâíûì ïîíÿòèåì ÿâ- ëÿåòñÿ ïðîñòðàíñòâî ñäâèãîâ â ñèìâîëè÷åñêîé äèíàìèêå. Â ýòîì àñïåêòå îòìåòèì, ÷òî äëÿ çàäà÷è ïðîâåðêè, îïðåäåëÿåò ëè äàííîå ìóëüòèìíîæåñòâî ïîäñëîâ ïðîñòðàí- ñòâî ñäâèãîâ, çàäàííîå îïðåäåëåííûìè çàïðåòàìè, ïðåäëîæåííàÿ ïðîöåäóðà ðåäóê- öèè è ïîñëåäóþùåãî èññëåäîâàíèÿ ìóëüòèîðãðàôà äîñòàâëÿåò ïîëíîå ðåøåíèå. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. Ñ ì å ò à í è í Þ . Ã . , Ó ë ü ÿ í î â Ì . Â . Ðåêîíñòðóêöèÿ ñëîâ ïî êîíå÷íîìó ìóëüòèìíîæåñòâó ïîäñëîâ â ãèïîòåçå ñäâèãà 1. I. Ðåêîíñòðóêöèÿ áåç çàïðåòîâ // Êèáåðíåòèêà è ñèñòåìíûé àíà- ëèç. — 2014. — ¹ 1. — Ñ. 168–177. 2. C a r p i A . , d e L u c a A . Words and special factors // Theoretical Computer Sci. — 2001. — 259. — P. 145–182. 3. L i n d D . , M a r c u s B . An introduction to symbolic dynamics and coding. — Cambridge, UK: Cambridge Univ. Press, 1995. — 495 p. 4. d e B r u i j n N . G . A ñombinatorial problem // Nederl. Akad. Wetensch. Proc. 49. — P. 758–764; Indagoniones Math. — 1946. — 8. — P. 461–467. 5. Ø à ï î ð å â Ñ . Ä . Äèñêðåòíàÿ ìàòåìàòèêà. Êóðñ ëåêöèé. — ÑÏá.: ÁÕÂ-Ïåòåðáóðã, 2006. — 400 ñ. 6. L o t h a i r e M . Combinatorics of words. Encyclopedia of mathematics and its applications. — Reading, Mass.: Addison-Wesley Publ. Co. — 1983. — 17. — 228 p. — http://www-igm.univ-mlv.fr/~berstel/Lothaire/. 7. L o t h a i r e M . Algebraic combinatorics on words. — Cambridge, UK: Cambridge Univ. press, 2002. — 455 p. — http://www-igm.univ-mlv.fr/~berstel/Lothaire/. 8. L o t h a i r e M . Applied combinatorics on words, 2005. — 610 c. 9. D r e y e r W . , K o t z D i t t r i c h A . , S c h m i d t D . Research perspectives for time series manage- ment systems // SIGMOD Record. — 1994. — 23, N 1. — P. 10–15. 10. Ã à ñ ô è ë ä Ä . Ñòðîêè, äåðåâüÿ è ïîñëåäîâàòåëüíîñòè â àëãîðèòìàõ: Èíôîðìàòèêà è âû÷èñëè- òåëüíàÿ áèîëîãèÿ / Ïåð. ñ àíãë. — ÑÏá.: Íåâñêèé äèàëåêò; ÁÕÂ–Ïåòåðáóðã, 2003. — 654 ñ. Ïîñòóïèëà 26.09.2014 186 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 1

Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. II. Реконструкция при наличии запрещенного слова

Репозитарії

Схожі ресурси