Запрещенные треки и запрещенные подтреки
Поняття заборонених рядків та підпослідовностей, що застосовуються до рядків, узагальнені на треки. Стаття містить розв’язок задач побудови для заданого трека множин заборонених треків та заборонених підтреків...
Збережено в:
| Дата: | 2013 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/86229 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Запрещенные треки и запрещенные подтреки / К.В. Шахбазян, Ю.Г. Шукурян // Кибернетика и системный анализ. — 2013. — Т. 49, № 3. — С. 3-13. — Бібліогр.: 14 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-86229 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-862292015-09-11T03:01:44Z Запрещенные треки и запрещенные подтреки Шахбазян, К.В. Шукурян, Ю.Г. Кибернетика Поняття заборонених рядків та підпослідовностей, що застосовуються до рядків, узагальнені на треки. Стаття містить розв’язок задач побудови для заданого трека множин заборонених треків та заборонених підтреків The notions of forbidden strings and forbidden subsequences are generalized to traces. The paper presents algorithms to construct sets of minimum forbidden traces and minimum forbidden subtraces for a given trace. 2013 Article Запрещенные треки и запрещенные подтреки / К.В. Шахбазян, Ю.Г. Шукурян // Кибернетика и системный анализ. — 2013. — Т. 49, № 3. — С. 3-13. — Бібліогр.: 14 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/86229 519.6 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/86229 |
| citation_txt |
Запрещенные треки и запрещенные подтреки / К.В. Шахбазян, Ю.Г. Шукурян // Кибернетика и системный анализ. — 2013. — Т. 49, № 3. — С. 3-13. — Бібліогр.: 14 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT šahbazânkv zapreŝennyetrekiizapreŝennyepodtreki AT šukurânûg zapreŝennyetrekiizapreŝennyepodtreki |
| first_indexed |
2025-07-06T13:41:38Z |
| last_indexed |
2025-07-06T13:41:38Z |
| _version_ |
1836905187598401536 |
| fulltext |
Ê.Â. ØÀÕÁÀÇßÍ, Þ.Ã. ØÓÊÓÐßÍ
ÓÄÊ 519.6 ÇÀÏÐÅÙÅÍÍÛÅ ÒÐÅÊÈ
È ÇÀÏÐÅÙÅÍÍÛÅ ÏÎÄÒÐÅÊÈ
Êëþ÷åâûå ñëîâà: ÷àñòè÷íî-êîììóòàòèâíûé ìîíîèä, çàïðåùåííàÿ ñòðîêà,
çàïðåùåííûé òðåê, çàïðåùåííûé ïîäòðåê.
ÂÂÅÄÅÍÈÅ
Íàñòîÿùàÿ ñòàòüÿ ïîñâÿùåíà îáîáùåíèÿì íà òðåêè ïîíÿòèé çàïðåùåííûõ
ñòðîê è çàïðåùåííûõ ïîäïîñëåäîâàòåëüíîñòåé, ïðèìåíÿåìûõ ê ñòðîêàì [1–5].
Ýòèìè îáîáùåíèÿìè ÿâëÿþòñÿ ñëåäóþùèå ïîíÿòèÿ.
Ïóñòü M D( , )� — òðåêîâûé ìîíîèä è s t M D, ( , )� � [6]. Òðåê s íàçûâàåòñÿ
ìèíèìàëüíûì çàïðåùåííûì òðåêîì äëÿ t, åñëè s t�Fact( ), íî âñå ñîáñòâåííûå
ôàêòîðû òðåêà s ïðèíàäëåæàò Fact( )t . Ïóñòü s s sn� 1� è t t s t s tn n� 0 1 1� , ãäå
s sn1, ,� , t t M Dn0 , , ( , )� � � .  ýòîì ñëó÷àå s íàçûâàåòñÿ ïîäòðåêîì òðåêà t, è
ýòî îòíîøåíèå îáîçíà÷àåòñÿ s t� . Tðåê s íàçûâàåòñÿ ìèíèìàëüíûì çàïðåùåí-
íûì ïîäòðåêîì äëÿ òðåêà t, åñëè s t�� , íî êàæäûé ñîáñòâåííûé ïîäòðåê s ÿâëÿåò-
ñÿ ïîäòðåêîì t, ò.å. u s u t� � äëÿ êàæäîãî u M D� ( , )� .
Âî ìíîãèõ çàäà÷àõ êîìïüþòåðíîãî àíàëèçà òåêñòîâ áîëüøîé èíòåðåñ ïðåä-
ñòàâëÿåò ðàññìîòðåíèå çàïðåùåííûõ ñòðîê òåêñòîâ, ò.å. òàêèõ, êîòîðûå íå ÿâëÿ-
þòñÿ ôàêòîðàìè òåêñòà. Ïîíÿòèå ìèíèìàëüíîé çàïðåùåííîé ñòðîêè ýôôåêòèâíî
îáúåäèíÿåò îòðèöàòåëüíóþ èíôîðìàöèþ î òåêñòàõ è èãðàåò âàæíóþ ðîëü â ïðè-
ëîæåíèÿõ. Íàïðèìåð, ìåòîä ñæàòèÿ òåêñòîâ áåç ïîòåðü [7] è ìåòîä ðåêîíñòðóê-
öèè ÄÍÊ ñ ó÷åòîì ìíîæåñòâà åå ôðàãìåíòîâ îñíîâàí íà «àíòèñëîâàðÿõ» [8]. Ýòî
ïîíÿòèå èñïîëüçóåòñÿ â òåîðèè àâòîìàòîâ è ñèìâîëüíîé äèíàìèêå, ãäå êàæäîå
ïðîñòðàíñòâî ñäâèãîâ îäíîçíà÷íî îïðåäåëÿåòñÿ ìíîæåñòâîì çàïðåùåííûõ ñòðîê
[9]. Ýòî îáóñëîâèëî èíòåðåñ ê ïåðåíîñó ïîíÿòèé çàïðåùåííûõ ñòðîê è
çàïðåùåííûõ ïîäïîñëåäîâàòåëüíîñòåé íà òðåêè.
 íàñòîÿùåé ñòàòüå ïðèâåäåíî ðåøåíèå ñëåäóþùèõ çàäà÷ äëÿ çàïðåùåííûõ
òðåêîâ è çàïðåùåííûõ ïîäòðåêîâ:
N L Nf ( ): ïî êîíå÷íîìó àíòèôàêòîðèàëüíîìó ÿçûêó òðåêîâ N ðàñïîç-
íàòü òðåêè ÿçûêà L Nf ( ) — ôàêòîðèàëüíîãî òðåêîâîãî ÿçûêà, äëÿ êîòîðîãî ÿçûê
N ÿâëÿåòñÿ ÿçûêîì ìèíèìàëüíûõ çàïðåùåííûõ òðåêîâ (íà îñíîâå àâòîìàòà
Messner-a [10] äëÿ ðåøåíèÿ ïðîáëåìû ïðåôèêñà â ìîíîèäå òðåêîâ ïðåäëîæåí àë-
ãîðèòì, ðàñïîçíàþùèé L Nf ( ) äëÿ êîíå÷íîãî N );
t MFT t ( ): ïîñòðîèòü äëÿ çàäàííîãî òðåêà t M D� ( , )� ìíîæåñòâî
MFT t( ) ìèíèìàëüíûõ çàïðåùåííûõ òðåêîâ (ïðåäëîæåí àëãîðèòì, ðåøàþùèé
ïðîáëåìó);
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3 3
� Ê.Â. Øàõáàçÿí, Þ.Ã. Øóêóðÿí, 2013
N L NST ( ): ïî êîíå÷íîìó àíòèïîäòðåêîâîìó ÿçûêó òðåêîâ N ïîñòðîèòü
àâòîìàò, äîïóñêàþùèé ÿçûê L L NST� ( ), äëÿ êîòîðîãî N ÿâëÿåòñÿ ÿçûêîì ìèíè-
ìàëüíûõ çàïðåùåííûõ ïîäòðåêîâ;
t MFST t ( ): ïîñòðîèòü äëÿ çàäàííîãî òðåêà t M D� ( , )� ìíîæåñòâî
MFST t( ) ìèíèìàëüíûõ çàïðåùåííûõ ïîäòðåêîâ (íà îñíîâå àëãîðèòìà [11] äëÿ ðå-
øåíèÿ àíàëîãè÷íîé ïðîáëåìû äëÿ ñòðîê ïðåäëîæåí àëãîðèòì, ñòðîÿùèé MFST t( )).
ÌÎÍÎÈÄ ÒÐÅÊÎÂ
Äàëåå èñïîëüçîâàíû ñëåäóþùèå ïîíÿòèÿ è îáîçíà÷åíèÿ.
Ïóñòü � — êîíå÷íûé àëôàâèò, D �
� � — ðåôëåêñèâíîå è ñèììåòðè÷íîå
îòíîøåíèå çàâèñèìîñòè, I D�
( ) \� � — îòíîøåíèå íåçàâèñèìîñòè èëè ïåðåñòà-
íîâî÷íîñòè. Îòíîøåíèå I èíäóöèðóåò îòíîøåíèå ýêâèâàëåíòíîñòè � íà �* . Äâå
ñòðîêè: x y, *�� , ÿâëÿþòñÿ ýêâèâàëåíòíûìè îòíîñèòåëüíî � , åñëè ñóùåñòâóåò
ïîñëåäîâàòåëüíîñòü z zn1, , *
� �� ñòðîê òàêèõ, ÷òî x z� 1, y zn� è äëÿ âñåõ i
( )1� �i n ñóùåñòâóþò ñòðîêè z zi i� � ��, *� è áóêâû a bi i, ��, óäîâëåòâîðÿþùèå
óñëîâèÿì
z z a b z
z z b a z
i i i i i
i i i i i
� � � �
� � � �
�
�
� �
,
,1
ãäå ( , )a b Ii i � , ò.å. äâå ñòðîêè ýêâèâàëåíòíû ïî îòíîøåíèþ � òîãäà è òîëüêî
òîãäà, êîãäà îäíó ìîæíî ïîëó÷èòü èç äðóãîé ïóòåì ïåðåñòàíîâîê ñîñåäíèõ
íåçàâèñèìûõ áóêâ. Êëàññû ýêâèâàëåíòíûõ ñòðîê èç �* ïî îòíîøåíèþ � íàçû-
âàþòñÿ òðåêàìè, à ìíîæåñòâî M M D� ( , )� ÿâëÿåòñÿ òðåêîâûì ìîíîèäîì. Íà
ýëåìåíòàõ M îïðåäåëåíî óìíîæåíèå — êîíêàòåíàöèÿ. Îáîçíà÷èì [ ]x òðåê t
äëÿ ëþáîé ïðåäñòàâëÿþùåé ñòðîêè x t� (îäíîáóêâåííûé òðåê íå áóäåì áðàòü
â êâàäðàòíûå ñêîáêè), | |t äëèíó òðåêà, êîòîðàÿ ÿâëÿåòñÿ äëèíîé ëþáîé ïðåä-
ñòàâëÿþùåé åãî ñòðîêè x t� , è Alph( )t ìíîæåñòâî áóêâ, âõîäÿùèõ â òðåê t.
Äëÿ çàäàííîãî òðåêà t M D� ( , )� ìíîæåñòâà ïðåôèêñîâ Pref ( )t , ñóôôèêñîâ
Suff ( )t è ôàêòîðîâ Fact( )t îïðåäåëÿþòñÿ îáû÷íûì îáðàçîì. Ïóñòü ( , , )� �1 � m —
ïîêðûòèå àëôàâèòà çàâèñèìîñòè ( , )� D êëèêàìè, ò.å. ñåìåéñòâî ïîäìíîæåñòâ �i
òàêèõ, ÷òî
� � � �i
i
m
i i D i m
�
�
� �
1
1 2� �, ( , , , ), ( , ) : ,a b D i a b i� � � �� .
Ëþáîé òðåê t M D� ( , )� ïðè çàäàííîì ïîêðûòèè ( , , )� �1 � m ìîæíî ïðåä-
ñòàâèòü m-êîé ñòðîê, êîòîðóþ îáîçíà÷èì � � �( ) ( ), , ( )t t tm� { }1 � . Çäåñü � i t( ) �
� �� �i in it t
i1 ( ), , ( ) *
� � , ãäå � i t( ) — ïðîåêöèÿ ñòðîêè y t� íà àëôàâèò �i , ni —
åå äëèíà.
Äëÿ êàæäîãî çàäàííîãî t M D� ( , )� ëþáîé ïðåôèêñ p t�Pref ( ) ìîæíî ïðåä-
ñòàâèòü c ïîìîùüþ m-êè öåëûõ ÷èñåë ïî îòíîøåíèþ ê �( )t :
p l lm� ( , , )1 � (1)
òàêîé, ÷òî � � �i il ilp t t
i
( ) ( ), , ( )� � [6].
Ïóñòü ( , )� D — àëôàâèò çàâèñèìîñòè òðåêîâîãî ìîíîèäà M D( , )� . Ãðàô çà-
âèñèìîñòè òðåêà t åñòü ïîìå÷åííûé àöèêëè÷åñêèé ãðàô G V Et � [ , , ]� , ãäå V —
ìíîæåñòâî âåðøèí, E V V�
— ìíîæåñòâî äóã, ãðàô ( , )V E àöèêëè÷åñêèé è èí-
äóöèðóåò ÷àñòè÷íûé ïîðÿäîê íà ñâîèõ âåðøèíàõ, � :V �— ìåòêè âåðøèí òà-
êèå, ÷òî ( ( ), ( ))� �v v D1 2 � òîãäà è òîëüêî òîãäà, êîãäà ( , )v v E E idV1 2
1� � �� .
Îòìåòèì, ÷òî ìíîæåñòâî âåðøèí ãðàôà Gt , ïîìå÷åííûõ îäíîé è òîé æå ìåòêîé
4 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3
V v V v bb � � �{ }| ( )� , óïîðÿäî÷åíî è ïîýòîìó èìååò ñìûñë ãîâîðèòü îá i-é
âåðøèíå âî ìíîæåñòâå Vb .
Åñëè çàäàí òðåê t a a M Dn� �[ ] ( , )1� � , òî ìîæíî ïîñòðîèòü ñîîòâåòñòâóþ-
ùèé åìó ãðàô çàâèñèìîñòè Gt . Âîçüìåì ìíîæåñòâî n âåðøèí, íàïðèìåð,
V n� { }1 2, , ,� . Ïîìåòèì âåðøèíó i áóêâîé ai è ïîëîæèì ( , ) ( , )i j E a a Di j� � � ,
i j� . Ýòîò ãðàô ñîîòâåòñòâóåò òðåêó t â òîì ñìûñëå, ÷òî êàæäûé ïîðÿäîê âåð-
øèí, èíäóöèðóåìûé ãðàôîì Gt , íåñåò ñòðîêó ìåòîê, ïðèíàäëåæàùóþ òðåêó t.
È îáðàòíî, êàæäîé ñòðîêå, ïðèíàäëåæàùåé òðåêó t, ñîîòâåòñòâóåò ïîðÿäîê íà
âåðøèíàõ ãðàôà Gt .
Äàëåå âåçäå áóäåì ñ÷èòàòü ôèêñèðîâàííûì ïîêðûòèå ( , , )� �1 � m êëèêàìè
àëôàâèòà çàâèñèìîñòè ( , )� D . Òîãäà m — ÷èñëî êëèê â ïîêðûòèè. Îáîçíà÷èì �
ðàçìåð íàèáîëüøåé êëèêè â ãðàôå íåçàâèñèìîñòè àëôàâèòà � .
ÇÀÏÐÅÙÅÍÍÛÅ ÒÐÅÊÈ
Ïóñòü M D( , )� — òðåêîâûé ìîíîèä; L M D� ( , )� íàçûâàåòñÿ ôàêòîðèàëü-
íûì ÿçûêîì, åñëè îí ñîäåðæèò âñå ôàêòîðû ñâîèõ òðåêîâ; L M D� ( , )� íà-
çûâàåòñÿ àíòèôàêòîðèàëüíûì ÿçûêîì, åñëè îí íå ñîäåðæèò íè îäíîãî ôàê-
òîðà ñâîèõ òðåêîâ.
Ïóñòü L — ôàêòîðèàëüíûé ÿçûê. Òðåê t íàçûâàåòñÿ çàïðåùåííûì òðåêîì äëÿ
L, åñëè t L� . Òðåê t íàçûâàåòñÿ ìèíèìàëüíûì çàïðåùåííûì òðåêîì äëÿ L, åñëè
t — çàïðåùåííûé òðåê äëÿ L, íî âñå ñîáñòâåííûå ôàêòîðû òðåêà t ïðèíàäëåæàò
L. Îáîçíà÷èì MFT L( ) ìíîæåñòâî ìèíèìàëüíûõ çàïðåùåííûõ òðåêîâ ÿçûêà L.
Ïóñòü L M D� ( , )� — ôàêòîðèàëüíûé ÿçûê òðåêîâ. Åãî äîïîëíåíèå Lc ÿâëÿåòñÿ
äâóõñòîðîííèì èäåàëîì â M D( , )� . Î÷åâèäíî, MFT L( ) — áàçèñ ýòîãî èäåàëà, ò.å.
L M D MFT L M Dc � � �( , ) ( ) ( , )� � ,
L MFT L� ��( ) ,
L M D M D MFT L M D� � �( , ) \ ( , ) ( ) ( , )� � � .
Ñëåäîâàòåëüíî, MFT L( ) îäíîçíà÷íî îïðåäåëÿåò L è îáðàòíî.
Ïðèìåð 1. Ðàññìîòðèì ìîíîèä M D( , )� , ãäå � � { }a b c d, , , , D d a� {( , ),
( , ), ( , )a c c b }, è ÿçûê L t� Fact( ), ãäå t dababc� [ ] (ðèñ. 1).
Òðåê s dabc� [ ] (ðèñ. 2) ÿâëÿåòñÿ çàïðåùåííûì òðåêîì äëÿ L, íî îí íå âõîäèò
â MFT L( ), òàê êàê îäèí èç åãî ñîáñòâåííûõ ôàêòîðîâ s dac L� � �[ ] . Ëåãêî âèäåòü,
÷òî âñå ñîáñòâåííûå ôàêòîðû s� ÿâëÿþòñÿ ôàêòîðàìè s. Ñëåäîâàòåëüíî,
s MFT L�� ( ).
Ïðèìåð 2. Ðàññìîòðèì ìîíîèä M D( , )� , ãäå � � { }a b c d e, , , , , D d a� {( , ),
( , ), ( , ), ( , )a c c b b e }. Ïóñòü L t t� �Fact Fact( ) ( )1 2 , ãäå t daabbca1 � [ ] , t dadcac2 � [ ]
(ðèñ. 3).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3 5
Ðèñ. 1. Ãðàô çàâèñèìîñòè òðåêà t dababc� [ ]
a a
bb
d
cGt :
Ðèñ. 2. Ãðàô çàâèñèìîñòè òðåêà s dabc� [ ]
a
cGs:
d
b
Î÷åâèäíî, ÷òî òðåê s daca� [ ] (ðèñ. 4) — çàïðåùåííûé äëÿ L, òàê êàê íå ÿâ-
ëÿåòñÿ ôàêòîðîì t1 èëè t2 . Åãî ñîáñòâåííûé ôàêòîð s dac1 � [ ] ÿâëÿåòñÿ ôàêòîðîì
t2 , à ñîáñòâåííûé ôàêòîð s aca2 � [ ] ÿâëÿåòñÿ ôàêòîðîì t1. Àíàëîãè÷íî è îñòàëü-
íûå ñîáñòâåííûå ôàêòîðû òðåêà s ÿâëÿþòñÿ ëèáî ôàêòîðàìè t1, ëèáî t2 è ïî
îïðåäåëåíèþ ïðèíàäëåæàò ÿçûêó L. Ñëåäîâàòåëüíî, s — ìèíèìàëüíûé
çàïðåùåííûé òðåê ÿçûêà L.
Îòìåòèì îñîáî, ÷òî òðåê e ÿâ-
ëÿåòñÿ ìèíèìàëüíûì çàïðåùåííûì
òðåêîì äëÿ L, òàê êàê áóêâà e íå
âõîäèò â àëôàâèòû òðåêîâ t1 è t2 .
ÏÐÎÁËÅÌÀ N L Nf ( )
Çàäàíû: ìîíîèä M D( , )� è êîíå÷íûé àíòèôàêòîðèàëüíûé ÿçûê N n� { 1, �
� , ( , )n M Dk }� � .
Ïîñòðîèòü àëãîðèòì, ðàñïîçíàþùèé òðåêè, ïðèíàäëåæàùèå ÿçûêó
L N M D M D N M Df ( ) ( , ) \ ( , ) ( , )� � �� � � , (2)
ò.å. ÿçûêó òðåêîâ L Nf ( ), äëÿ êîòîðîãî N ÿâëÿåòñÿ ìíîæåñòâîì ìèíèìàëüíûõ
çàïðåùåííûõ òðåêîâ.
Óòâåðæäåíèå 1. Ñóùåñòâóåò àëãîðèòì, ðàñïîçíàþùèé ïðèíàäëåæíîñòü òðå-
êà t ÿçûêó L Nf ( ) çà âðåìÿ, ëèíåéíîå ïî | | | |t n
i
k
i�
�1
.
Äîêàçàòåëüñòâî. Âîñïîëüçóåìñÿ àâòîìàòîì An Messner-à [11], êîòîðûé
ñòðîèòñÿ ïî òðåêó n M D� ( , )� çà âðåìÿ, ëèíåéíîå ïî | |nt , è ðàñïîçíàåò ÿçûê
M D n( , )� � . Àâòîìàò An ìèíèìàëüíûé. Ñîãëàñíî (2) äëÿ âûÿñíåíèÿ ïðèíàäëåæ-
íîñòè òðåêà t ÿçûêó L Nf ( ) äîñòàòî÷íî ïðîâåðèòü, ÷òî íè îäèí èç òðåêîâ
n nk1, ,� íå ÿâëÿåòñÿ ôàêòîðîì òðåêà t. Î÷åâèäíî, ÷òî âðåìÿ ýòîé ïðîâåðêè ëè-
íåéíîå ïî | | | |t ni
i
k
�
�
1
.
ÏÐÎÁËÅÌÀ L MFT L ( )
Ïî ôàêòîðèàëüíîìó ÿçûêó òðåêîâ L ïîñòðîèòü ìíîæåñòâî MFT L( ) ìèíèìàëü-
íûõ çàïðåùåííûõ òðåêîâ. Çäåñü ïðîáëåìà ðåøàåòñÿ äëÿ ÷àñòíîãî ñëó÷àÿ, êîã-
äà L ÿâëÿåòñÿ ìíîæåñòâîì ôàêòîðîâ îäíîãî òðåêà, ò.å. L t� Fact( ) ïðè çàäàí-
íîì t M D� ( , )� .
Îïðåäåëåíèå 1. Ïóñòü s t M D, ( , )� � è s t�Fact( ) . Åñëè áóêâû a b, �� òàêèå,
÷òî [ ] ( )as t�Fact , [ ] ( )sb t�Fact , [ ] ( )asb t�Fact , áóäåì ãîâîðèòü, ÷òî ôàêòîð s ïî-
ðîæäàåò ìèíèìàëüíûé çàïðåùåííûé òðåê [ ]asb .
Îïðåäåëåíèå 2. Ïóñòü s t�Fact( ) . Åñëè t psu� , ãäå u M D� ( , )� , òî ïàðó
( , )p s íàçîâåì âõîæäåíèåì ôàêòîðà s â òðåê t.
Ïóñòü ñóùåñòâóåò n ðàçëè÷íûõ âõîæäåíèé ôàêòîðà s â t s p s: ( ) (( , ),� � 1 �
� , ( , ))p sn , ãäå p p tn1, , ( )� �Pref . Äëÿ êàæäîãî âõîæäåíèÿ îïðåäåëèì ñëåäóþ-
6 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3
Ðèñ. 4. Ãðàô çàâèñèìîñòè òðåêà s daca� [ ]
a cd aGs:
Ðèñ. 3. Ãðàôû çàâèñèìîñòè òðåêîâ t daabbca1 � [ ] , t dadcac2 � [ ]
a a
bb
d
cGt1
: a Gt2
:
a d
c
d
a c
ùèå ìíîæåñòâà áóêâ:
�( , ) | ( ) ,p s a p sa ti i� � �{ Pref }� �( , ) | ( ) :p s a r p ra pi i i� � � � �{ Pref }� .
Íàçîâåì îêðåñòíîñòüþ ôàêòîðà s âî âõîæäåíèè ( , )p si ïàðó ìíîæåñòâ
( ( , ), ( , ))� �p s p si i .
Îòìåòèì, ÷òî äëÿ âñåõ i n�1, ,� èìååò ìåñòî | ( , )| , | ( , )|� �p s p s mi i � . Îïðå-
äåëèì ñîîòâåòñòâóþùèé ñïèñîê îêðåñòíîñòåé ôàêòîðà s: � * ( ) (( ( , ),s p s� � 1
� � �( , )), , ( ( , ), ( , )))p s p s p sn n1 � . Äëèíà ñïèñêà � * ( )s íå ïðåâûøàåò | |t � .
Óòâåðæäåíèå 2. Åñëè ( , )p s — âõîæäåíèå ôàêòîðà s â òðåê t è b p s��( , ),
a p s��( , ), òî asb t�Fact( ).
Ñëåäñòâèå 1. Åñëè òðåê s èìååò åäèíñòâåííîå âõîæäåíèå â òðåê t, òî äëÿ t íå
ñóùåñòâóåò çàïðåùåííîãî òðåêà, ïîðîæäåííîãî ôàêòîðîì s.
Óòâåðæäåíèå 3. Ôàêòîð s t�Fact( ) ïîðîæäàåò ìèíèìàëüíûé çàïðåùåííûé
òðåê asb t�Fact( ), ãäå a p si i�� �( , ), b p si i�� �( , ), òîãäà è òîëüêî òîãäà, êîãäà
íå ñóùåñòâóåò âõîæäåíèÿ ( , ) ( )p s s�� ôàêòîðà s òàêîãî, ÷òî b p s��( , ), a p s��( , ) .
Ïîðîæäàåò ëè äàííûé ôàêòîð s ìèíèìàëüíûé çàïðåùåííûé òðåê, óñòàíàâëèâàåò-
ñÿ ïî ñïèñêó � * ( )s çà âðåìÿ � �(| | | | )2 t � , ãäå � — ðàçìåð íàèáîëüøåé êëèêè
â ãðàôå íåçàâèñèìîñòè àëôàâèòà �.
Äîêàçàòåëüñòâî. Ïðåäïîëîæèì, ÷òî asb — çàïðåùåííûé òðåê t. Åñëè
� � �( , ) ( ) : ( , )p s s b p s� � , a p s��( , ), òî ïî óòâåðæäåíèþ 2 asb t�Fact( ), ÷òî ïðî-
òèâîðå÷èò ïðåäïîëîæåíèþ.
Ïóñòü b p si��( , ), a p si��( , ), i j� , íî �� � �( , ) ( ): ( , )p s s b p s� � , a p s��( , ).
Ïðåäïîëîæèì asb t�Fact( ). Òîãäà òðåê t ìîæíî ïðåäñòàâèòü â âèäå t w asbw� 1 2 ,
ò.å. ñóùåñòâóåò âõîæäåíèå ( , )w a s1 ñ îêðåñòíîñòüþ ( ( , ), ( , ))� �w a s w a s1 1 òàêîé, ÷òî
b s��( ), a s��( ), ÷òî ïðîòèâîðå÷èò ïðåäïîëîæåíèþ. Ïðèâåäåííàÿ îöåíêà îñíîâà-
íà íà òîì, ÷òî ÷èñëî ïðåôèêñîâ òðåêà t èìååò ïîðÿäîê � (| | )t � .
Ïðèìåð 3. Ðàññìîòðèì òðåê t èç ïðèìåðà 1. Â íåì ôàêòîð a èìååò äâà âõîæ-
äåíèÿ è ñîîòâåòñòâåííî äâå îêðåñòíîñòè: ( , ){ } { }d a è ( , ){ } { }a c . Ïî óòâåðæäåíèþ 3
òðåêè [ ], [ ]dac aaa ÿâëÿþòñÿ ìèíèìàëüíûìè çàïðåùåííûìè òðåêàìè, ïîðîæäàå-
ìûìè ôàêòîðîì a. Òðåê b èìååò îêðåñòíîñòè ( , )� { }b è ( , ){ } { }b c . Ñëåäîâàòåëüíî,
ôàêòîð b ïîðîæäàåò åäèíñòâåííûé ìèíèìàëüíûé çàïðåùåííûé òðåê [ ]bbb .
ÀËÃÎÐÈÒÌ ÐÅØÅÍÈß ÏÐÎÁËÅÌÛ N L Nf ( )
Àëãîðèòì íàêàïëèâàåò ìíîæåñòâî ôàêòîðîâ òðåêà t âìåñòå ñ îêðåñòíîñòÿìè
âñåõ âõîæäåíèé ôàêòîðîâ, à çàòåì ïðîâåðÿåò óñëîâèå óòâåðæäåíèÿ 3 äëÿ êàæ-
äîãî ôàêòîðà s t�Fact( ). Àëãîðèòì ñîñòîèò èç ÷åòûðåõ ýòàïîâ.
1. Ïîëó÷åíèå ãðàôà ïðåôèêñîâ òðåêà t ñ ïîìîùüþ àëãîðèòìà Avellon-à [5].
Ïóñòü t M D� ( , )� . Àëãîðèòì ñòðîèò ãðàô G t t U t tPref Pref( ) ( ( ), , )� � ïðåôèêñîâ
òðåêà t, ãäå U u r u r t a r uat � � � � �{ Pref }( , )| , ( ), :� , ìåòêa íà äóãe � t u r a( , ) � ,
åñëè r ua� . Âåðøèíàìè ãðàôà G tPref ( ) ÿâëÿþòñÿ íàáîðû p p pm� ( , , )1 � âèäà
(1), ïðåäñòàâëÿþùèå ñîîòâåòñòâóþùèå ïðåôèêñû u t�Pref ( ) äëèíîé ïðîåêöèé
ïðåôèêñà îòíîñèòåëüíî ïðîåêöèé �( )t . Äëÿ êàæäîãî ïðåôèêñà u t�Pref ( ) àëãî-
ðèòì ñòðîèò A u( ) — ñïèñîê äóã âèäà ( , )u r , ãäå u r t, ( )�Pref , èñõîäÿùèõ èç âåðøè-
íû u â ãðàôå Gt . Ïðè ýòîì â ñïèñêå âìåñòå ñ äóãîé ñîäåðæèòñÿ åå ìåòêà.
×èñëî ïðåôèêñîâ òðåêà t èìååò ïîðÿäîê � (| | )t � , ãäå �— ðàçìåð íàèáîëüøåé
êëèêè â ãðàôå íåçàâèñèìîñòè àëôàâèòà � è ñëîæíîñòü àëãîðèòìà åñòü � (| | )t � .
Ïðèìåð 4. Ðàññìîòðèì ìîíîèä M D( , )� , ãäå � � { }a b c d, ; , , D �
� {( , ), ( , ), ( , ), ( , )}d a a c d c c b è òðåê t dabac� [ ] (ðèñ. 5). Çàäàíî ïîêðûòèå ãðàôà
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3 7
( , )� D êëèêàìè � � �{ }d a c, , { }b c, .
Ïðîåêöèè òðåêà t íà êëèêè:
�1 ( )t daac� , � 2 ( )t bc� .
Òðåê [ ]ab èìååò äâà âõîæäå-
íèÿ â òðåê t:� ([ ]) (( , [ ]),ab d ab�
([ ], [ ]))da ab . Ëåãêî âèäåòü, ÷òî
�( , [ ])d ab a� { }, �( , [ ])d ab d� { },
�([ ],da [ ])ab c� { }, �([ ], [ ])da ab �{ }a . Â ãðàôå G tPref ( ) (ðèñ. 6) ýòèì äâóì âõîæäå-
íèÿì ñîîòâåòñòâóþò îêðåñòíîñòü ( , ){ } { }a d ôàêòîðà [ ]ab âî âõîæäåíèè ( , [ ])d ab è
îêðåñòíîñòü ( , ){ } { }c a ôàêòîðà [ ]ab âî âõîæäåíèè ([ ], [ ])da ab . Èç ðàññìîòðåíèÿ
ýòèõ îêðåñòíîñòåé ïî óòâåðæäåíèþ 3 ïîëó÷àåì, ÷òî ôàêòîð [ ]ab ïîðîæäàåò äâà
ìèíèìàëüíûõ çàïðåùåííûõ òðåêà äëÿ òðåêà t dabc:[ ] è [ ]aaba .
2. Ñáîð èíôîðìàöèè îá îêðåñòíîñòÿõ âõîæäåíèé êàæäîãî ôàêòîðà s
â òðåê t . Ïðè ñáîðå ýòîé èíôîðìàöèè ïåðåáèðàþòñÿ âñå ïàðû ( , )r s , ãäå r è rs —
âåðøèíû ãðàôà G tPref ( ) , ëåæàùèå íà îäíîì ïóòè èç íà÷àëüíîé âåðøèíû, ò.å.
r rs t, �Pref ( ), s t�Fact( ). Ïóñòü ïðåôèêñû r rs t, ( )�Pref . Òîãäà èçâåñòíû èõ
ïðåäñòàâëåíèÿ âèäà (1): r l lm� ( , , )1 � è rs k km� ( , , )1 � . Ïðè ýòîì î÷åâèäíî,
÷òî ïðîåêöèÿ ôàêòîðà s íà êëèêó �i åñòü � � �i i l i k is t t
i i
( ) ( ) ( ), ,
*� ��1 � � .
Ëåãêî âèäåòü, ÷òî åñëè çàäàíî âõîæäåíèå ( , ) ( )r s s�� , òî �( , )r s �
� � � � �{ }a u A rs u at� | ( ) : ( )� , ãäå A rs( ) âû÷èñëÿåòñÿ îäíîâðåìåííî ñ G tPref ( ) ;
�( , )r s ìîæíî âû÷èñëèòü ïî ñëåäóþùåé ôîðìóëå: åñëè r l lm� ( , , )1 � , òî
� � �( , ) { , , }r s l lm
�
1
� . Ñëåäîâàòåëüíî, ìíîæåñòâà �( , )r s è �( , )r s ìîæíî âû÷èñ-
ëèòü ïðè ðàññìîòðåíèè âõîæäåíèÿ ( , ) ( )r s s�� . ×èñëî ôàêòîðîâ òðåêà t èìååò ïî-
ðÿäîê � (| | )t 2� , ãäå � — ðàçìåð íàèáîëüøåé êëèêè â ãðàôå íåçàâèñèìîñòè àëôà-
âèòà � . Ïîñêîëüêó äëÿ ñðàâíåíèÿ ôàêòîðîâ è äëÿ âû÷èñëåíèÿ îäíîé îêðåñòíîñòè
( ( , ), ( , ))� �r s r s òðåáóåòñÿ � ( )t øàãîâ, ñëîæíîñòü ýòîãî ýòàïà åñòü � (| | )t 2 1�� .
3. Ñòðóêòóðà äëÿ ñáîðà èíôîðìàöèè îá îêðåñòíîñòÿõ âõîæäåíèé êàæäîãî
ôàêòîðà s â òðåê t . Ñîáðàííóþ èíôîðìàöèþ íåîáõîäèìî ñîõðàíÿòü â íåêîòîðîì
õðàíèëèùå èíôîðìàöèè, ïðèñïîñîáëåííîì äëÿ çàïîìèíàíèÿ ìíîæåñòâ òðåêîâ ñ ñî-
ïóòñòâóþùåé èíôîðìàöèåé. Ýòî õðàíèëèùå äîëæíî áûòü ñòðóêòóðîé, îáåñïå÷èâà-
þùåé áûñòðûé ïîèñê òðåêîâ âî ìíîæåñòâå, âêëþ÷åíèå íîâûõ òðåêîâ, èçìåíåíèå ñî-
ïóòñòâóþùåé èíôîðìàöèè. Â ðàáîòå [13] ïðåäëîæåíà ñïåöèàëüíàÿ ñòðóêòóðà F äëÿ
îïèñàíèÿ ìíîæåñòâ òðåêîâ. Ýòà ñòðóêòóðà ÿâëÿåòñÿ îáîáùåíèåì ïðåôèêñíûõ äå-
ðåâüåâ, èñïîëüçóåìûõ äëÿ õðàíåíèÿ ñòðîê. Íàïîìíèì, ÷òî â ïðåôèêñíûõ äåðåâüÿõ
èìååòñÿ îäíà âåðøèíà äëÿ êàæäîãî îáùåãî ïðåôèêñà è ñòðîêè çàïîìèíàþòñÿ êàê
ïîñëåäîâàòåëüíîñòè ìåòîê ïóòåé, âåäóùèõ îò êîðíÿ ê ôèíàëüíûì âåðøèíàì.
Äëÿ îïèñàíèÿ ìíîæåñòâ òðåêîâ ïðåäëîæåíà ñòðóêòóðà F m� ( , , , )� �1 � ,
ãäå � �i i i iV E� ( , , ), i m�1, ,� , — ïðåôèêñíîå äåðåâî äëÿ õðàíåíèÿ ìíîæåñòâà
ñòðîê �( )i â àëôàâèòå �i ;Vi — âåðøèíû äåðåâà; Ei — äóãè äåðåâà; � i — ôóíê-
8 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3
Ðèñ. 6. Ãðàô G tPref( )
b
ad a
(0,0) (1,0) (2,0) (3,0)
(3,1)(2,1)(1,1)(0,1)
ad a c
(3,2)
b b b
Ðèñ. 5. Ãðàô çàâèñèìîñòè òðåêà t dabac� [ ]
a a
b
d
cGt :
öèÿ ïîìåòêè äóã áóêâàìè èç �i ; — ïðåôèêñíoå äåðåâo äëÿ õðàíåíèÿ ìíîæåñ-
òâà ñòðîê äëèíû m â àëôàâèòå Vii
m
�1� . Êàæäàÿ òàêàÿ ñòðîêà ïðèíàäëåæèò
V Vm1
� .
Ñòðóêòóðà F èñïîëüçóåòñÿ äëÿ õðàíåíèÿ ìíîæåñòâà òðåêîâ ( )F â ñëåäóþ-
ùåì ñìûñëå. Òðåê s ïðèíàäëåæèò ìíîæåñòâó ( )F òîãäà è òîëüêî òîãäà, êîãäà
âûïîëíåíû óñëîâèÿ: â êàæäîì äåðåâå � i ñóùåñòâóåò ïóòü èç êîðíÿ â íåêîòîðóþ
âåðøèíó vi , íåñóùèé ñòðîêó � i s( ), i m�1, ,� , ïðè÷åì â äåðåâå ñóùåñòâóåò
ïóòü èç êîðíÿ â âèñÿ÷óþ âåðøèíó, íåñóùèé ñòðîêó v vm1� .
Ñòðóêòóðó F ìîæíî èñïîëüçîâàòü äëÿ õðàíåíèÿ ìíîæåñòâà âñåõ ôàêòîðîâ
òðåêà t è ñëîâàðÿ çàïðåùåííûõ òðåêîâ MTF t( ). Ñòðóêòóðà F ïîçâîëÿåò çà ëèíåé-
íîå âðåìÿ óñòàíàâëèâàòü ïðèíàäëåæíîñòü òðåêà ìíîæåñòâó ( )F èëè äîáàâëÿòü
íîâûé òðåê [13].
Äëÿ ñáîðà èíôîðìàöèè î âõîæäåíèÿõ êàæäîãî ôàêòîðà s â òðåê t èçìåíèì
ñòðóêòóðó F , äîáàâèâ â íåå âîçìîæíîñòü çàäàíèÿ îêðåñòíîñòåé òðåêîâ. À èìåííî,
ðàññìîòðèì ñòðóêòóðó F m� �( , , , )� �1 � , çäåñü � — äåðåâî , â êîòîðîì äî-
áàâëåíà âîçìîæíîñòü â êàæäîé âèñÿ÷åé âåðøèíå õðàíèòü ñïèñêè ïàð âèäà ( , )
� ,
ãäå
�, � � è | | , | |
� � m . Òîãäà, åñëè âèñÿ÷àÿ âåðøèíà äåðåâà ñîîòâåòñòâóåò
ôàêòîðó s , ñâÿæåì ñ íåþ ñïèñîê îêðåñòíîñòåé òðåêîâ � * ( ) (( ( , ),s p s� � 1
� � �( , )), , ( ( , ), ( , )))p s p s p sn n1 � . Ñïèñîê � * ( )s èñïîëüçóåòñÿ äëÿ ïðîâåðêè óñëî-
âèé óòâåðæäåíèÿ 3, ò.å. ïîðîæäàåò ëè ôàêòîð s ìèíèìàëüíûé çàïðåùåííûé òðåê,
è â ñëó÷àå ïîëîæèòåëüíîãî îòâåòà äëÿ íàõîæäåíèÿ ýòîãî çàïðåùåííîãî òðåêà.
4. Ñðàâíåíèå îêðåñòíîñòåé ôàêòîðîâ. Îòìåòèì, ÷òî êàæäûé ôàêòîð ìîæåò
èìåòü � (| | )t 2� âõîæäåíèé è ñîîòâåòñòâåííî ñòîëüêî æå îêðåñòíîñòåé. Äëÿ êàæ-
äîãî ôàêòîðà s îñóùåñòâëÿåòñÿ ïîèñê òàêèõ ïàð áóêâ ( , )a b àëôàâèòà � , äëÿ êîòî-
ðûõ âûïîëíÿåòñÿ óñëîâèå óòâåðæäåíèÿ 3.  ýòîì ñëó÷àå asb — ìèíèìàëüíûé çà-
ïðåùåííûé òðåê t.
Î÷åâèäíî, ýòîò ýòàï àëãîðèòìà òðåáóåò � (| | )t 2 1�� øàãîâ.
Óòâåðæäåíèå 4. Ñóùåñòâóåò àëãîðèòì ïîñòðîåíèÿ ìíîæåñòâà MTF L( ) çàïðå-
ùåííûõ òðåêîâ ÿçûêà L t� Fact( ) äëÿ òðåêà t M D� ( , )� ñî ñëîæíîñòüþ � (| | )t 2 1�� ,
ãäå � — ðàçìåð íàèáîëüøåé êëèêè â ãðàôå íåçàâèñèìîñòè àëôàâèòà � .
ÇÀÏÐÅÙÅÍÍÛÅ ÏÎÄÒÐÅÊÈ
Åñëè G1 — ïîäãðàô ãðàôà G2 , òî áóäåì ïèñàòü G G1 2� .
Îïðåäåëåíèå 3. Ïóñòü s t M D, ( , )� � òàêîâû, ÷òî âûïîëíåíî s s sn� 1� è
t t s t s tn n� 0 1 1� , ãäå s s t t M Dn n1 0, , , , , ( , )� � � � . Èç ýòîãî ðàâåíñòâà ñëåäóåò,
÷òî G Gs t� .  ýòîì ñëó÷àå s íàçîâåì ïîäòðåêîì òðåêà t è îáîçíà÷èì ýòî îòíîøå-
íèå s t� (îáîçíà÷èì �� îòðèöàíèå îòíîøåíèÿ �). Îòíîøåíèå s t� îçíà÷àåò s t� ,
íî s t� .
Òðåê s M D� ( , )� åñòü çàïðåùåííûé ïîäòðåê äëÿ òðåêà t M D� ( , )� , åñëè s t�� .
Òðåê s M D� ( , )� åñòü çàïðåùåííûé ïîäòðåê äëÿ ÿçûêà òðåêîâ L M D� ( , )� ,
åñëè s ÿâëÿåòñÿ çàïðåùåííûì ïîäòðåêîì äëÿ âñåõ t M D� ( , )� .
Çàïðåùåííûé òðåê s ÿâëÿåòñÿ ìèíèìàëüíûì çàïðåùåííûì ïîäòðåêîì äëÿ t,
åñëè êàæäûé ñîáñòâåííûé ïîäòðåê s ÿâëÿåòñÿ ïîäòðåêîì t, ò.å. u s u t� � äëÿ
êàæäîãî u M D� ( , )� .
Îáîçíà÷èì MFST t( ) ìíîæåñòâî âñåõ ìèíèìàëüíûõ çàïðåùåííûõ ïîäòðåêîâ
äëÿ t.
ßçûê L M D� ( , )� íàçûâàåòñÿ ïîäòðåêîâûì, åñëè îí ñîäåðæèò âñå ïîäòðåêè
ñâîèõ òðåêîâ, è àíòèïîäòðåêîâûì, åñëè íè îäèí èç åãî òðåêîâ íå ÿâëÿåòñÿ ïîä-
òðåêîì òðåêà, ïðèíàäëåæàùåãî L.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3 9
Ïðèìåð 5. Ðàññìîòðèì ìîíîèä òðåêîâ M D( , )� , ãäå � � { }a b c d, , , ,
D d a a c c b� { }( , ), ( , ), ( , ) , à òàêæå òðåêè t dababc� [ ] , u acb� [ ] . Î÷åâèäíî, ÷òî u t�� .
Îäíàêî u MFT v� ( ), òàê êàê [ ]cb t�� .
Ïóñòü L M D� ( , )� — ïîäòðåêîâûé ÿçûê. Îòìåòèì, ÷òî MFST L( ) îäíîçíà÷-
íî õàðàêòåðèçóåò L:
L M D e MFST L
MFST L u u L S u u L
�
� � �
�
�
�
( , ) \ ( ( )),
( ) { | , ( ) \ { } },
�
(3)
ãäå e MFST L( ( )) — ìíîæåñòâî òðåêîâ, èìåþùèõ ïîäòðåê, ïðèíàäëåæàùèé
MFST L( ), S u( ) — ìíîæåñòâî âñåõ ïîäòðåêîâ òðåêà u.
Ñëåäñòâèå 2. ßçûêè L è MFST L( ) ëèáî îäíîâðåìåííî ðàöèîíàëüíû, ëèáî
íåðàöèîíàëüíû.
Ñîîòíîøåíèÿ (3) óñòàíàâëèâàþò áèåêöèþ ìåæäó ïîäòðåêîâûìè è àíòèïîä-
òðåêîâûìè ÿçûêàìè.
ÏÐÎÁËÅÌÀ N L NST ( )
Äëÿ äàííîãî àíòèïîäòðåêîâîãî ÿçûêà N ïîñòðîèòü àâòîìàò, ðàñïîçíàþùèé
ÿçûê L L NST� ( ), äëÿ êîòîðîãî N MFST L� ( ).
Óòâåðæäåíèå 5. Äëÿ ëþáîãî êîíå÷íîãî ìíîæåñòâà N u un� { }1, ,� òðåêîâ
ìîíîèäà M D( , )� ñóùåñòâóåò êîíå÷íûé äåòåðìèíèðîâàííûé àâòîìàò B N( ), äî-
ïóñêàþùèé ÿçûê L L NST� ( ).
Äîêàçàòåëüñòâî. Â ðàáîòå [14] óòâåðæäåíèå 2 ñîñòîèò â òîì, ÷òî äëÿ ëþáîãî
òðåêà p M D� ( , )� ñóùåñòâóåò àâòîìàò Çåëåíêè A p( ), êîòîðûé äîïóñêàåò
t M D� ( , )� òîãäà è òîëüêî òîãäà, êîãäà p t� . Ñëåäîâàòåëüíî, ñóùåñòâóåò àâòî-
ìàò A p( ), äîïóñêàþùèé t M D� ( , )� òîãäà è òîëüêî òîãäà, êîãäà p t�� , à àâòîìàò
B N( ) — ïðÿìîå ïðîèçâåäåíèå àâòîìàòîâ A u A un( ), , ( )1 � , äîïóñêàåò ÿçûê
L NST ( ).
ÏÐÎÁËÅÌÀ t MFST t ( )
Çàäàí òðåê t M D� ( , )� . Ïîñòðîèòü ìíîæåñòâî MFST t( ) ìèíèìàëüíûõ çàïðå-
ùåííûõ ïîäòðåêîâ.
Óòâåðæäåíèå 6. Ïóñòü s t M D, ( , )� � . Òîãäà
îòíîøåíèå s t� èìååò ìåñòî òîãäà è òîëüêî òîãäà, êîãäà äëÿ êàæäîé ñòðî-
êè y òðåêà t ñóùåñòâóåò ñòðîêà x òðåêà s òàêàÿ, ÷òî x y� ;
îòíîøåíèå s t�� èìååò ìåñòî òîãäà è òîëüêî òîãäà, êîãäà äëÿ êàæäîé ñòðîêè
y òðåêà t è êàæäîé ñòðîêè x òðåêà s èìååò ìåñòî x y�� ;
îòíîøåíèå s MFST t� ( ) èìååò ìåñòî òîãäà è òîëüêî òîãäà, êîãäà äëÿ êàæ-
äîé ñòðîêè y t� è êàæäîé ñòðîêè x s� èìååò ìåñòî x MFS y� ( ), ò.å.
s MFST t y t x s x MFS y� � ! � ! � �( ) : ( ). Çäåñü MFS y( ) — ìíîæåñòâî ìèíè-
ìàëüíûõ çàïðåùåííûõ ïîäïîñëåäîâàòåëüíîñòåé ñòðîêè y [8].
Ïðèìåð 6. Ðàññìîòðèì ìîíîèä M D( , )� , ãäå � � { }a b c, , , D a c c b� { }( , ), ( , ) ,
à òàêæå òðåêè t acb� [ ] , s ba� [ ] . Î÷åâèäíî, ÷òî ba acb�� . Îäíàêî [ ] [ ]ba acb� .
Èç óòâåðæäåíèÿ 6 ñëåäóåò, ÷òî ìíîæåñòâî MFST t( ) ìîæíî ïîëó÷èòü â ïðî-
öåññå ïîðîæäåíèÿ ìíîæåñòâà MFS y( ), åñëè y t� . Íàäî òîëüêî èìåòü ìåòîä îòñå-
âà òåõ ñòðîê x MFS y� ( ), äëÿ êîòîðûõ [ ] ( )x MFST t� .
Äàëüíåéøèå ðàññóæäåíèÿ áàçèðóþòñÿ íà òåîðåìå î çàïðåùåííûõ ïîäïîñëå-
äîâàòåëüíîñòÿõ äëÿ ñòðîê, ïðèâåäåííîé â [8]. Ïðåæäå âñåãî ðàññìîòðèì íåêóþ
ïîäïîñëåäîâàòåëüíîñòü, ñâÿçàííóþ ñ êàæäîé ìèíèìàëüíîé çàïðåùåííîé ïîäïîñ-
10 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3
ëåäîâàòåëüíîñòüþ, êîòîðàÿ ïîçâîëèò ñòðîèòü MFST t( ) ïóòåì íåáîëüøîãî âèäî-
èçìåíåíèÿ ðåêóððåíòíûõ ôîðìóë, ïîëó÷åííûõ â [8] äëÿ ïîñòðîåíèÿ MFS y( ),
åñëè y t� .
 ðàáîòå [8] ïðèâåäåíà òåîðåìà 4.1, îïèñûâàþùàÿ ðåêóððåíòíûé ïðîöåññ ïî-
ñòðîåíèÿ ìèíèìàëüíûõ çàïðåùåííûõ ïîäïîñëåäîâàòåëüíîñòåé äàííîé ñòðîêè.
Ïðåäñòàâèì åå. Ïóñòü x X� è u X� * — ïðîèçâîëüíûå. Åñëè x u�Alph( ), òî
u u xu� 1 2 , ãäå u u X1 2, *� è x u�Alph( )2 . Åñëè z xu x�Alph( )2 , òî îáîçíà÷èì T z( )
ìíîæåñòâî âñåõ áóêâ, âõîäÿùèõ â ñòðîêó xu x2 ïîñëå z. Òîãäà
MFS ux MFS u X x MFS u X zx T zz xu( ) ( ) \ * ( ( ) * ) ( )( )� � ��� Alph 2
. (4)
Åñëè x u�Alph( ), òî
MFS ux MFS u x x ux( ) ( ) \ ( )� �{ } Alph . (5)
Ýòà òåîðåìà èñïîëüçîâàíà â on-line àëãîðèòìå [8] äëÿ âû÷èñëåíèÿ ìíîæåñòâà
çàïðåùåííûõ ïîäïîñëåäîâàòåëüíîñòåé MFS u( ) äëÿ ñòðîêè u. Àëãîðèòì ðàáîòàåò
ýêñïîíåíöèàëüíîå âðåìÿ ïî | |u .
Ïðåæäå âñåãî âûâåäåì ñëåäñòâèå èç ýòîé òåîðåìû, ñâÿçûâàþùåå ñòðóêòóðó
ñòðîêè u ñ åå ìèíèìàëüíûìè çàïðåùåííûìè ïîäïîñëåäîâàòåëüíîñòÿìè.
Ïóñòü u y y Xn� �0� *, x X� . Îáîçíà÷èì | |u n� �1 äëèíó ñòðîêè u, à | |u x
÷èñëî âõîæäåíèé áóêâû x â ñòðîêó u. Åñëè y xi � è | |y y ji x0 � � , òî áóäåì ÷èñëî
i íàçûâàòü êîîðäèíàòîé j-ãî âõîæäåíèÿ áóêâû x â ñòðîêó u.
Ëåììà. Ïóñòü u y y Xn� �0� *. Äëÿ òîãî ÷òîáû a a a MFS uk� �0� ( ) :
ïðè k � 0 íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû a u0 �Alph( ) ;
ïðè k " 1 íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû â ñòðîêó u âõîäèëà â êà÷åñòâå
ïîäïîñëåäîâàòåëüíîñòè ñòðîêà
A a u A a a u a a a a a a a a a ak k k k k( , ) ( , )� � � � �0 1 0 2 1 3 2 1 2 1� � ,
ïðè÷åì äëÿ ñîîòâåòñòâóþùèõ êîîðäèíàò áóêâ ýòîé ïîäïîñëåäîâàòåëüíîñòè
â ñòðîêå u:
i i i i i i i i i ik k k k1 0 2 1 3 2 1 2 1, , , , , , , , , ,� � � � �� � ��
äîëæíû âûïîëíÿòñÿ ïðèâåäåííûå äàëåå óñëîâèÿ.
1. Ïåðâîå âõîæäåíèå áóêâû a0 â ñòðîêó u èìååò êîîðäèíàòó �i0 , ïîñëåäíåå
âõîæäåíèå áóêâû ak â ñòðîêó u èìååò êîîðäèíàòó ik , ò. å. y ai � �0 0 , y ai kk
� .
2. ×èñëà i ij j, � — ñóòü êîîðäèíàòû äâóõ ïîñëåäîâàòåëüíûõ âõîæäåíèé îäíîé
è òîé æå áóêâû a j â ñòðîêó u, ò.å. y y ai i jj j
� �� è åñëè i l ij j� � �, òî y al j� ,
j k� �1 1, ,� .
3. Ìåæäó äâóìÿ ïîñëåäîâàòåëüíûìè âõîæäåíèÿìè áóêâû a j ñ êîîðäèíàòàìè
i ij j, � â ñòðîêó u íàõîäÿòñÿ âõîæäåíèÿ áóêâ a j�1 è a j�1: i i i ij j j j� � � � �� �1 1 ,
j k� �1 1, ,� . Ïðè ýòîì i j�1 — ñàìîå ïðàâîå èç âõîæäåíèé áóêâû a j�1 â ñòðîêó
a a a ai i i ij j j j� � � � � �� � �1 1 1
1 1
� .
4. Ðàâåíñòâî i ij j� � �1 âûïîëíÿåòñÿ òîãäà è òîëüêî òîãäà, êîãäà â ñòðîêå u
èìååò ìåñòî a aj j� �1.
Äîêàçàòåëüñòâî. Ñëó÷àé k � 0 î÷åâèäåí. Ðàññìîòðèì ñëó÷àé k " 1 . Ïóñòü
çàäàíà ñòðîêà u y y Xn� �0� * è ïóñòü ñòðîêà a a ak� 0� òàêîâà, ÷òî â ñòðîêå u
ñóùåñòâóåò ïîäïîñëåäîâàòåëüíîñòü A a u( , ), óäîâëåòâîðÿþùàÿ óñëîâèÿì ëåììû.
Ïóñòü a aj j� �1, j k� �0 1, ,� . Ïîêàæåì, ÷òî â ýòîì ñëó÷àå a MFS u� ( ). Ëåãêî
âèäåòü, ÷òî ñòðîêà a íå ÿâëÿåòñÿ ïîäïîñëåäîâàòåëüíîñòüþ ñòðîêè u. Ïóñòü òå-
ïåðü èç ñòðîêè a óäàëåíà ïðîèçâîëüíàÿ áóêâà a j . Î÷åâèäíî, ÷òî
y y y y y y a a a a a ui i i i i i j j kj j k k� � � � �� � �
� �
0 1 1 1 1 0 1 1 1� � � � .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3 11
Ñëåäîâàòåëüíî, êàæäàÿ ñîáñòâåííàÿ ïîäïîñëåäîâàòåëüíîñòü ñòðîêè a ÿâëÿåòñÿ
ïîäïîñëåäîâàòåëüíîñòüþ ñòðîêè u, ÷òî îçíà÷àåò a MFS u� ( ).
Ñëó÷àé, êîãäà ñóùåñòâóåò j òàêîå, ÷òî a aj j� �1, ðàññìàòðèâàåòñÿ àíàëîãè÷íî.
Ïîêàæåì òåïåðü îáðàòíîå. Ïðåäïîëîæèì, ÷òî ëåììà âåðíà äëÿ ñòðîêè u, ò.å.
êàæäîé ñòðîêå a a a MFS uk� �0� ( ) ñîîòâåòñòâóåò ñòðîêà A a u( , ), óäîâëåòâîðÿ-
þùàÿ óñëîâèÿì 1–4. Äîêàæåì, ÷òî ëåììà âåðíà äëÿ ñòðîêè ux, ãäå x X� .
Ðàññìîòðèì ïîäðîáíåå ðåêóððåíòíûé ïðîöåññ ïîñòðîåíèÿ ìíîæåñòâà
MFS ux( ) ïî ìíîæåñòâó MFS u( ), îïèñàííûé òåîðåìîé 4.1 â [8].
Î÷åâèäíî, ÷òî åñëè a a a MFS uk� �0� ( ) è a xk � , òî A a u( , ) óäîâëåòâîðÿåò
óñëîâèÿì ëåììû è íà ñòðîêå ux. Ñëåäîâàòåëüíî, â ýòîì ñëó÷àå a a ak� �0�
�MFS ux( ).
Ïóñòü òåïåðü a xk � . Ïðè ýòîì âîçìîæíû ñëåäóþùèå âàðèàíòû: u y yn� 0� ,
x u�Alph( ), ò.å. x íå âõîäèò â ñòðîêó u. Ñîãëàñíî (4) MFS ux MFS u( ) ( )� �
� xyi
n
0� . Òîãäà ñòðîêå a xyi� ñîîòâåòñòâóåò ñòðîêà A a ux y xi( , ) � , êîòîðàÿ î÷å-
âèäíî ÿâëÿåòñÿ ïîäïîñëåäîâàòåëüíîñòüþ ñòðîêè ux y y xn� 0� .
Ïóñòü u y y Xn� �0�
* , x X� è x âõîäèò â ñòðîêó u u xu� 1 2 , x u�Alph( )2 ,
ãäå âûäåëåíî ñàìîå ïðàâîå âõîæäåíèå áóêâû x â u. Ïðåäïîëîæèì, ÷òî óæå ïî-
ñòðîåíà ïîäïîñëåäîâàòåëüíîñòü A a u( , ) ñòðîêè u äëÿ êàæäîé ñòðîêè a MFS u� ( ).
Ôîðìóëà (3) òåîðåìû 4.1 èç [8] îïðåäåëÿåò ñëåäóþùèé ïîðÿäîê äåéñòâèé
äëÿ äîáàâëåíèÿ íîâûõ çàïðåùåííûõ ïîäïîñëåäîâàòåëüíîñòåé âî ìíîæåñòâî
MFS ux( ), êîòîðûå ñòðîÿòñÿ ïî ñòðîêàì èç MFS u( ), îêàí÷èâàþùèìñÿ áóêâîé x.
Ïóñòü a rzx MFS u� � ( ), ãäå r X� * , z X� . Òîãäà ñòðîêà A a u A rzx u sxz( , ) ( , )� � ,
ãäå s X� * .
Äëÿ êàæäîé áóêâû b, âõîäÿùåé â ñòðîêó xu x2 ïîñëå áóêâû z, ñòðîêà
ab rzxb MFS ux� � ( ) è ñîîòâåòñòâóþùàÿ ñòðîêà A ab ux sxzbx( , ) � . Äëÿ íåå
� � ��t nk 1 2, tk�1 ðàâíî êîîðäèíàòå ïîñëåäíåãî âõîæäåíèÿ áóêâû b â ñòðîêó u. Êî-
îðäèíàòû îñòàëüíûõ áóêâ íå ìåíÿþòñÿ. Î÷åâèäíî, ÷òî A ab ux( , ) óäîâëåòâîðÿåò
óñëîâèÿì ëåììû.
Âåðíåìñÿ ê òðåêàì t M D� ( , )� è ê ìèíèìàëüíûì çàïðåùåííûì ïîäòðåêàì,
âõîäÿùèì âî ìíîæåñòâî MFST t( ). Áóäåì íàçûâàòü öåïüþ ëèáî îäíîáóêâåííûé
òðåê, ëèáî òðåê a a a M Dk� �[ ] ( , )0� � , k " 1, äëÿ êîòîðîãî âûïîëíÿåòñÿ
( , )a a Di i� �1 ïðè âñåõ i k� �01 1, , ,� .
Òåîðåìà 1. Ïóñòü s t M D, ( , )� � . Åñëè s MFST t� ( ), òî s — öåïü.
Äîêàçàòåëüñòâî. Ïðåäïîëîæèì, ÷òî s MFST t� ( ). Ðàññìîòðèì ïðîèçâîëü-
íûå ñòðîêè u y y tn� �0� è a a a sk� �0� â òîì ñëó÷àå, êîãäà â ñòðîêå a íåò
ñòîÿùèõ ðÿäîì îäèíàêîâûõ áóêâ. (Åñëè òàêîâûå èìåþòñÿ, äîêàçàòåëüñòâî àíàëî-
ãè÷íî.) Ñîãëàñíî óòâåðæäåíèþ 6, åñëè a s� , òî a a MFS uk0� � ( ). Ñîãëàñíî ëåììå
ñòðîêà
A a u a a a a a a a a a a a a a ai i i i k k k k( , ) � � � � � � �1 0 2 1 3 2 1 2 1 1 2 1� �
ÿâëÿåòñÿ ïîäïîñëåäîâàòåëüíîñòüþ ñòðîêè u y yn� 0� .
Ïðåäïîëîæèì, ÷òî òðåê s — íå öåïü. Òîãäà ñóùåñòâóþò a ai i� �1 òàêèå, ÷òî
( , )a a Ii i� �1 . Ñëåäîâàòåëüíî, a a a a a si i k� � ��0 1� � . Îäíàêî, êàê ëåãêî âèäåòü,
ñòðîêà a� ÿâëÿåòñÿ ïîäïîñëåäîâàòåëüíîñòüþ ñòðîêè A a u( , ) è òåì ñàìûì ÿâëÿåòñÿ
ïîäïîñëåäîâàòåëüíîñòüþ ñòðîêè u y yn� 0� , ÷òî ïðîòèâîðå÷èò ïðåäïîëîæåíèþ.
Ñëåäñòâèå 3. Ïóñòü t M D� ( , )� è ñòðîêà u t� . Òîãäà MFST t( ) �
� �{x MFS u x( ) | [ ] — öåïü}.
Îòñþäà ñëåäóåò, ÷òî ôîðìóëû òåîðåìû 4.1 èç [8] ëåãêî èçìåíèòü òàê, ÷òîáû
îíè îïèñûâàëè ïðîöåññ ïîñòðîåíèÿ ìíîæåñòâà ìèíèìàëüíûõ çàïðåùåííûõ òðå-
12 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3
êîâ MFST t( ) , ãäå t M D� ( , )� . À èìåííî, íóæíî â ôîðìóëó (3) òåîðåìû 4.1 äî-
áàâèòü óñëîâèå, êîòîðîå ðàçðåøàåò ïîðîæäåíèå òîëüêî öåïåé. Äëÿ ýòîãî íåîáõî-
äèìî ïåðåîïðåäåëèòü T z( ) êàê ìíîæåñòâî òàêèõ áóêâ y, êîòîðûå âõîäÿò â ñòðîêó
xu x2 ïîñëå z, è òàêèõ, ÷òî ( , )y x D� . Êðîìå òîãî, â ñëó÷àå x u�Alph( ) íóæíî
âìåñòî (4) èñïîëüçîâàòü ôîðìóëó
MFST tx MFST t x xy y tx y x D( ) ( ) \ | ( ), ( , )� � � �{ } { Alph }.
ÇÀÊËÞ×ÅÍÈÅ
Ñòàòüÿ ñîäåðæèò ðåøåíèÿ íåñêîëüêèõ çàäà÷ î çàïðåùåííûõ òðåêàõ è ïîäòðå-
êàõ.  ÷àñòíîñòè, ïðåäëîæåíû àëãîðèòìû, ñòðîÿùèå ìíîæåñòâà ìèíèìàëüíûõ
çàïðåùåííûõ òðåêîâ è ìèíèìàëüíûõ çàïðåùåííûõ ïîäòðåêîâ äëÿ çàäàííîãî òðåêà.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. M i g n o s i F . , R e s t i v o A . , S c i o r t i n o M . Words and forbidden factors // Theoretical
Comput. Sci. – 2001. — 273, N 1–2. — P. 99–117.
2. C r o c h e m o r e M . , R y t t e r W . Jewels of stringology // World Sci. Publ. Co. Rtc. Ltd, 2002. –
320 p.
3. C o m p u t i n g forbidden words of regular languages / M. Beal, M. Crochemore, F. Mignosi at al. //
Fundamenta Inform. 2003. — 56, N 1–2. — P. 121–135.
4. C r o c h e m o r e M . , M i g n o s i F . , R e s t i v o A . Automata and forbidden words // Inform.
Process. Lett. — 1998. — 67. — P. 111–117.
5. P e t c o v i c T . , C i r i c v , B o g d a n o v i c S . Minimal forbidden subwords // Inform. Process.
Lett. — 2004. — 92. — P. 211–218.
6. D i k e r t V . , R o z e n b e r g G . The book of traces // Handbook Formal Languages, Beyond
Words. N.Y.: Springer-Verlag. — 1997. — 3. — 568 p.
7. C r o c h e m o r e M . , M i g n o s i F . , R e s t i v o A . , S a l e m i S . Data compression using
antidictionaries // Proc IEEE (Special issue on lossless data compression). — 2000. — 88, N 11. —
P. 1756–1768.
8. M i g n o s i F . , R e s t i v o A . , S c i o r t i n o M . Forbidden factors and fragment assembly //
LNCS. — 2002. — 2295. — P. 349–358.
9. B e a l M . , M i g n o s i F . , R e s t i v o A . , S c i o r t i n o M . Forbidden words in symbolic dy-
namics // Advances in Applied Mathematics. — 2000. — 25, N 2. — P. 163–193.
10. B e a l M . , M i g n o s i F . , R e s t i v o A . Minimal forbidden words and symbolic dynamics //
Proceedings of the 13th Annual Symp. on Theoretical Aspects of Comput. Sci. — 1996. —
N 22–24. — P. 555–566.
11. M e s s n e r J . Pattern Matching in trace monoids // STACS. — 1997. — 97. — P. 571–582.
12. A v e l l o n e A . , G o l d w u r m M . Analysis of algorithms for the recognition of rational ànd con-
text-free trace languages // Theoretical Inform. and Appl. — 1998. — 32. — N 4–6. — P. 141–152.
13. Ø à õ á à ç ÿ í Ê . Â . , Ø ó ê ó ð ÿ í Þ . Ã . Àñèíõðîííûå àâòîìàòû, ñðàâíèâàþùèå òðåêè //
Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2012. — ¹ 3. — P. 3–11.
14. Ø à õ á à ç ÿ í Ê . Â . , Ø ó ê ó ð ÿ í Þ . Ã . Âõîæäåíèÿ â ìîíîèäå òðåêîâ // Òàì æå. — 2010. —
¹ 4. — P. 31–38.
Ïîñòóïèëà 09.07.2012
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3 13
|