Асинхронные автоматы, сравнивающие треки
Наведено алгоритми розв’язання декiлькох задач порiвняння трекiв Мазуркевича. Алгоритми зводяться до побудови автоматiв, що розпiзнають вiдповiднi рацiональнi трековi мови. Розглянуто трековi мови, пов’язанi з розв’язанням конретних задач, що мають аналоги в науцi про рядки....
Gespeichert in:
| Datum: | 2012 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/84103 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Асинхронные автоматы, сравнивающие треки / К.В. Шахбазян, Ю.Г. Шукурян // Кибернетика и системный анализ. — 2012. — Т. 48, № 3. — С. 3-11. — Бібліогр.: 13 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-84103 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-841032015-07-04T03:01:17Z Асинхронные автоматы, сравнивающие треки Шахбазян, К.В. Шукурян, Ю.Г. Кибернетика Наведено алгоритми розв’язання декiлькох задач порiвняння трекiв Мазуркевича. Алгоритми зводяться до побудови автоматiв, що розпiзнають вiдповiднi рацiональнi трековi мови. Розглянуто трековi мови, пов’язанi з розв’язанням конретних задач, що мають аналоги в науцi про рядки. The paper presents algorithms for solving several matching problems of Mazurkiewicz traces. These algorithms are reduced to the construction of automata that recognize the corresponding rational trace languages. Rational trace languages and their properties were studies by many authors. The paper considers trace languages related to specific problems that have analogs in stringology 2012 Article Асинхронные автоматы, сравнивающие треки / К.В. Шахбазян, Ю.Г. Шукурян // Кибернетика и системный анализ. — 2012. — Т. 48, № 3. — С. 3-11. — Бібліогр.: 13 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/84103 519.6 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Кибернетика Кибернетика |
| spellingShingle |
Кибернетика Кибернетика Шахбазян, К.В. Шукурян, Ю.Г. Асинхронные автоматы, сравнивающие треки Кибернетика и системный анализ |
| description |
Наведено алгоритми розв’язання декiлькох задач порiвняння трекiв Мазуркевича. Алгоритми зводяться до побудови автоматiв, що розпiзнають вiдповiднi рацiональнi трековi мови. Розглянуто трековi мови, пов’язанi з розв’язанням конретних задач, що мають аналоги в науцi про рядки. |
| format |
Article |
| author |
Шахбазян, К.В. Шукурян, Ю.Г. |
| author_facet |
Шахбазян, К.В. Шукурян, Ю.Г. |
| author_sort |
Шахбазян, К.В. |
| title |
Асинхронные автоматы, сравнивающие треки |
| title_short |
Асинхронные автоматы, сравнивающие треки |
| title_full |
Асинхронные автоматы, сравнивающие треки |
| title_fullStr |
Асинхронные автоматы, сравнивающие треки |
| title_full_unstemmed |
Асинхронные автоматы, сравнивающие треки |
| title_sort |
асинхронные автоматы, сравнивающие треки |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2012 |
| topic_facet |
Кибернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/84103 |
| citation_txt |
Асинхронные автоматы, сравнивающие треки / К.В. Шахбазян, Ю.Г. Шукурян // Кибернетика и системный анализ. — 2012. — Т. 48, № 3. — С. 3-11. — Бібліогр.: 13 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT šahbazânkv asinhronnyeavtomatysravnivaûŝietreki AT šukurânûg asinhronnyeavtomatysravnivaûŝietreki |
| first_indexed |
2025-07-06T11:03:24Z |
| last_indexed |
2025-07-06T11:03:24Z |
| _version_ |
1836895231735234560 |
| fulltext |
Ê.Â. ØÀÕÁÀÇßÍ, Þ.Ã. ØÓÊÓÐßÍ
ÓÄÊ 519.6 ÀÑÈÍÕÐÎÍÍÛÅ ÀÂÒÎÌÀÒÛ,
ÑÐÀÂÍÈÂÀÞÙÈÅ ÒÐÅÊÈ
Êëþ÷åâûå ñëîâà: àñèíõðîííûé àâòîìàò, òðåê, ñðàâíåíèå.
Ðàññìîòðèì àëãîðèòìû ðåøåíèÿ íåñêîëüêèõ çàäà÷ ñðàâíåíèÿ òðåêîâ Ìàçóðêå-
âè÷à [1, 2], êîòîðûå ñâîäÿòñÿ ê ïîñòðîåíèþ àâòîìàòîâ, ðàñïîçíàþùèõ ñîîòâåò-
ñòâóþùèå ðàöèîíàëüíûå òðåêîâûå ÿçûêè. Ýòè ÿçûêè è èõ ñâîéñòâà èññëåäîâà-
ëèñü ìíîãèìè àâòîðàìè [1–7]. Íèæå ïðèâåäåíû òðåêîâûå ÿçûêè, ñâÿçàííûå
ñ ðåøåíèåì êîíêðåòíûõ çàäà÷, èìåþùèõ àíàëîãè â íàóêå î ñòðîêàõ
(stringology) [8–12]. Ïîñêîëüêó âñå îïèñàííûå ÿçûêè ðàöèîíàëüíûå, äëÿ íèõ
çàâåäîìî ñóùåñòâóþò äîïóñêàþùèå èõ àâòîìàòû Çåëåíêè. Àñèíõðîííûå àâ-
òîìàòû Çåëåíêè [3] ïðåäñòàâëÿþò ñîáîé ìíîæåñòâî ïîñëåäîâàòåëüíûõ êîìïî-
íåíòîâ, âçàèìîäåéñòâèå ìåæäó êîòîðûìè ìîäåëèðóåòñÿ ñëåäóþùèì ñèíõðîíèçà-
öèîííûì îãðàíè÷åíèåì: êîìïîíåíò ìîæåò âûïîëíÿòü ïåðåõîä ïî íåêîòîðîé
áóêâå òîãäà è òîëüêî òîãäà, êîãäà îäíîâðåìåííî âûïîëíÿþò ïåðåõîä ïî òîé æå
áóêâå âñå êîìïîíåíòû àñèíõðîííîãî àâòîìàòà, èìåþùèå åå â ñâîåì àëôàâèòå.
Èíòåðåñ âûçûâàþò âîïðîñû î ñëîæíîñòè àëãîðèòìîâ ïîñòðîåíèÿ àâòîìàòîâ,
ñðàâíèâàþùèõ òðåêè, è î ñëîæíîñòè ñðàâíåíèÿ òðåêîâ.
Èçâåñòíî, ÷òî äëÿ êàæäîãî ðàöèîíàëüíîãî ÿçûêà ñòðîê Lstr , ðàñïîçíàâàåìîãî
àâòîìàòîì Astr , ñóùåñòâóåò àëãîðèòì � tr , ðàñïîçíàþùèé òðåêîâûé ÿçûê
L L x y L y xItr str str{ }� � � � � � �[ ] |*� . Êàê ïîêàçàíî â [7], äëÿ ÿçûêà Ltr â îá-
ùåì ñëó÷àå àëãîðèòì ñâîäèòñÿ ê ïðèìåíåíèþ àâòîìàòà Astr êî âñåì ïðåôèêñàì
âõîäíîé ñòðîêè è èìååò ñëîæíîñòü â õóäøåì ñëó÷àå O(| | )x � , ãäå � — ÷èñëî âåð-
øèí ìàêñèìàëüíîé êëèêè ãðàôà íåçàâèñèìîñòè ( , )� I .
Íèæå èçëîæåíû ìåòîäû ïîñòðîåíèÿ àñèíõðîííûõ àâòîìàòîâ äëÿ ðåøåíèÿ
ñëåäóþùèõ çàäà÷:
� ðàñïîçíàâàíèå âëîæåííûõ òðåêîâ — ïî çàäàííîé ñòðîêå y�� ñòðîèòñÿ
àâòîìàò, ðàñïîçíàþùèé òðåêè, âëîæåííûå â òðåê [ ]y ;
� ðàñïîçíàâàíèå êîíå÷íîãî ÿçûêà òðåêîâ — ïî çàäàííûì ñòðîêàì
x xn1, , *
� � � ñòðîèòñÿ àâòîìàò, ðàñïîçíàþùèé òðåêîâûé ÿçûê [ ] [ ]x xn1
� ;
� ðàñïîçíàâàíèå ñóôôèêñîâ òðåêà — ïî çàäàííîé ñòðîêå x��* ñòðîèòñÿ àâ-
òîìàò, ðàñïîçíàþùèé ÿçûê Suff ([ ])x ;
� ïî «ñëîâàðþ» — ìíîæåñòâó ñòðîê { }x xn1, ,� , ñòðîèòñÿ àâòîìàò, ðàñïîçíà-
þùèé ÿçûê [ ]([ ] [ ])*� x xn1
� ;
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 3
� Ê.Â. Øàõáàçÿí, Þ.Ã. Øóêóðÿí, 2012
� ïî «ñëîâàðþ» — ìíîæåñòâó ñòðîê { }x xn1, ,� , ñòðîèòñÿ àâòîìàò, ðåøàþùèé
çàäà÷ó ïîèñêà â ñòðîêå y y y y� �1, , | |
*
� � âñåõ ïðåôèêñîâ y yk1, ,� ñòðîêè y,
äëÿ êîòîðûõ ñóùåñòâóåò x j òàêîå, ÷òî [ ] [ ... ]x y yj k�Suff 1 .
Äëÿ ðåøåíèÿ ïåðå÷èñëåííûõ çàäà÷ ïðåäëîæåíû àëãîðèòìû ñ ëèíåéíîé âðå-
ìåííîé ñëîæíîñòüþ. Ïðèâåäåíû îöåíêè ñëîæíîñòè ïîñòðîåíèÿ ñîîòâåòñòâóþ-
ùèõ àñèíõðîííûõ àâòîìàòîâ è çàäåðæêè íà êàæäîì øàãó èõ ðàáîòû.
Âñå àâòîìàòû, îïèñàííûå â ñòàòüå, îòíîñÿòñÿ ê êëàññó ñóïåðïîçèöèé ðàñïðåäå-
ëåííûõ àñèíõðîííûõ àâòîìàòîâ è àâòîìàòîâ, ðàñïîçíàþùèõ êîíå÷íûå ÿçûêè ñòðîê.
ÏÐÅÄÂÀÐÈÒÅËÜÍÛÅ ÑÂÅÄÅÍÈß È ÎÏÐÅÄÅËÅÍÈß
Ïóñòü � — êîíå÷íûé àëôàâèò, D �
� � — ðåôëåêñèâíîå è ñèììåòðè÷íîå îò-
íîøåíèå çàâèñèìîñòè, I D�
( ) \� � — îòíîøåíèå íåçàâèñèìîñòè èëè ïåðåñòà-
íîâî÷íîñòè. Îòíîøåíèå I èíäóöèðóåò îòíîøåíèå ýêâèâàëåíòíîñòè � I íà �* .
Äâå ñòðîêè x y, *�� ýêâèâàëåíòíû îòíîñèòåëüíî � I , åñëè ñóùåñòâóåò ïîñëåäî-
âàòåëüíîñòü 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 a b I
i i i i i
i i i i i i i
� � ��
� � �� �
�
�
� �
,
, ( , ) ,1 ãäå
ò.å. äâå ñòðîêè ýêâèâàëåíòíû ïî îòíîøåíèþ � I òîãäà è òîëüêî òîãäà, êîãäà
îäíó èç íèõ ìîæíî ïîëó÷èòü èç äðóãîé ïóòåì ïåðåñòàíîâîê ñîñåäíèõ íåçàâè-
ñèìûõ áóêâ. Òîãäà ìíîæåñòâî M M D� ( , )� êëàññîâ ýêâèâàëåíòíûõ ïî
îòíîøåíèþ � I ñòðîê â àëôàâèòå � íàçûâàåòñÿ òðåêîâûì ìîíîèäîì, à åãî
ýëåìåíòû — òðåêàìè. Íà ýëåìåíòàõ M îïðåäåëåíî óìíîæåíèå — êîíêàòåíà-
öèÿ. Òðåê t îáîçíà÷àåòñÿ [ ]x äëÿ ëþáîé ïðåäñòàâëÿþùåé ñòðîêè x t� . Äëèíà
òðåêà t åñòü äëèíà ëþáîãî åãî ïðåäñòàâèòåëÿ y t� è îáîçíà÷àåòñÿ | | | |t y� .
Ïóñòü ( , , )� �1 � m — ïîêðûòèå àëôàâèòà çàâèñèìîñòè ( )��D êëèêàìè, ò.å.
ñåìåéñòâî ïîäìíîæåñòâ � òàêèõ, ÷òî
� � � �i
i
m
i i D
�
�
�
1
� , ( , , , )i m�1 2 � ,
( , ) : ,a b D i a b i� � � �� .
Äàëåå âåçäå áóäåì ñ÷èòàòü ôèêñèðîâàííûìè òðåêîâûé ìîíîèä M D( )�� è
� �1 , ,� m — íàèìåíüøåå ïîêðûòèå êëèêàìè àëôàâèòà çàâèñèìîñòè ( )��D . Òîã-
äà m — ÷èñëî êëèê â íàèìåíüøåì ïîêðûòèè.
Ëþáîé òðåê t M D� ( )�� ìîæíî ïðåäñòàâèòü m-é ñòðîêîé [1], êîòîðóþ îáîçíà-
÷èì � � �( ) ( ), , ( ) .t t tm� { }1 � Çäåñü � i it( ) *�� — ïðîåêöèÿ ñòðîêè y t� íà �i .
Ïóñòü s t M D, ( )� �� . Òðåê s âëîæåí â òðåê t, åñëè ñóùåñòâóþò òðåêè
t t s s M Dl l0 1, , , , , ( )� � � �� òàêèå, ÷òî t t s t s tl l� 0 1 1 � è s s sl� 1� [13].
Äëÿ çàäàííîãî òðåêà t M D� ( )�� ãîâîðÿò, ÷òî p åñòü ïðåôèêñ t è q åñòü ñóô-
ôèêñ t, åñëè t pq� , ãäå p q M D, ( )� �� . Îáîçíà÷èì Pref ( )t ìíîæåñòâî ïðåôèêñîâ
òðåêà t è Suff ( )t — ìíîæåñòâî ñóôôèêñîâ òðåêà t.
Îïðåäåëåíèå 1. �-àâòîìàòîì (product automaton) íàä ìîíîèäîì M D( )�� íà-
çûâàåòñÿ ñòðóêòóðà B A Am� ( , , , )1 � � . Çäåñü A Am1, ,� — äåòåðìèíèðîâàííûå
êîíå÷íûå àâòîìàòû íàä ñòðîêàìè A Q q Fi i i i i i� ( , , , , )� 0 � , i m�1, ,� , íàçûâàåìûå
ëîêàëüíûìè êîìïîíåíòàìè, ãäå Qi — ìíîæåñòâî âíóòðåííèõ ñîñòîÿíèé, �i —
4 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
÷àñòè÷íî îïðåäåëåííàÿ ôóíêöèÿ ïåðåõîäà, Fi — ìíîæåñòâî ôèíàëüíûõ ñîñòîÿ-
íèé àâòîìàòà Ai , ��
F Fm1 � — ìíîæåñòâî ãëîáàëüíûõ ôèíàëüíûõ ñîñòîÿ-
íèé àâòîìàòà B. Ìíîæåñòâî Q Q Qm�
1 � íàçûâàåòñÿ ìíîæåñòâîì ãëîáàëüíûõ
ñîñòîÿíèé.
Åñëè ñ÷èòàòü ëîêàëüíûå êîìïîíåíòû ëèíåéíî óïîðÿäî÷åííûìè, òî ìíîæå-
ñòâî ��
F Fm1 � ìîæíî ðàññìàòðèâàòü êàê êîíå÷íûé ÿçûê ôèíàëüíûõ ñî-
ñòîÿíèé è, â ÷àñòíîñòè, ìîæíî ãîâîðèòü îá àâòîìàòå A�, ðàñïîçíàþùåì ïðèíàä-
ëåæíîñòü ñòðîê ÿçûêó �.
Ïðàâèëà ïåðåõîäîâ ìåæäó ãëîáàëüíûìè ñîñòîÿíèÿìè çàäàþò ñèíõðîíèçàöè-
îííûå îãðàíè÷åíèÿ ìåæäó ëîêàëüíûìè êîìïîíåíòàìè �-àâòîìàòà, ñôîðìóëèðî-
âàííûå â ñëåäóþùåì îïðåäåëåíèè.
Îïðåäåëåíèå 2. Ãëîáàëüíûé ïåðåõîä � åñòü ÷àñòè÷íî îïðåäåëåííàÿ ôóíêöèÿ
�:Q Q
�� , ãäå çíà÷åíèå �(( , , ), ) ( , ..., )q q a q qm m1 1� � � � îïðåäåëåíî òîãäà è
òîëüêî òîãäà, êîãäà îïðåäåëåíû ëîêàëüíûå ïåðåõîäû �i iq a( , ) äëÿ âñåõ 1� �i m
òàêèõ, ÷òî a i�� . Çíà÷åíèå (( , , ), )q q am1 � âû÷èñëÿåòñÿ ïî ôîðìóëå
� �
� � �
�
�
�
�
q
q q a a
q a
i
i i i i
i i
� ( , ), ,
.,
åñëè
åñëè
�
�
Îïðåäåëåíèå 3. Ïðîáåãîì �-àâòîìàòà B A Am� ( , , , )1 � � íà òðåêå t, çàäàí-
íîì ñòðîêîé y t� , íàçûâàåòñÿ îòîáðàæåíèå � : ( )Pref y Q� òàêîå, ÷òî
� �( ) ( , , )� q qm1
0 0
� è äëÿ âñåõ a �� , � � � � � �� �Pref ( ): ( ) ( ( ), )y a a , åñëè ãëîáàëü-
íûé ïåðåõîä îïðåäåëåí. Î÷åâèäíî, ÷òî åñëè ñòðîêè y yI� � , òî � �( ) ( )y y� � . Ãî-
âîðÿò, ÷òî �-àâòîìàò B äîïóñêàåò òðåê t, åñëè �( )y îïðåäåëåíî è �( )y ��.
Îïðåäåëåíèå 4. �-àâòîìàòû ñ óíèâåðñàëüíûì ôèíàëüíûì ìíîæåñòâîì
U F Fm�
1 ... â [6] íàçûâàþòñÿ äèñòðèáóòèâíûìè (ðàñïðåäåëåííûìè) �-àâòî-
ìàòàìè.
Ðàññìîòðèì �-àâòîìàò êàê ñóïåðïîçèöèþ ðàñïðåäåëåííîãî àâòîìàòà è àâòî-
ìàòà A�, îïðåäåëÿþùåãî ïðèíàäëåæíîñòü äîñòèãíóòîãî ãëîáàëüíîãî ñîñòîÿíèÿ
( , , )q qm1 � ÿçûêó ôèíàëüíûõ ãëîáàëüíûõ ñîñòîÿíèé. Ïîñêîëüêó êàæäîå ãëî-
áàëüíîå ñîñòîÿíèå ( , , )q qm1 � ìîæíî ðàññìàòðèâàòü êàê ñòðîêó q qm1... â àëôà-
âèòå Q Qm1
� , òî A� åñòü àâòîìàò, äîïóñêàþùèé ñòðîêè ÿçûêà ôèíàëüíûõ ñî-
ñòîÿíèé �.
Áóäåì ïîëàãàòü, ÷òî êàæäûé ãëîáàëüíûé ïåðåõîä �(( , , ), )q q am1 � �
� � �( , ..., )q qm1 ðàñïðåäåëåííîãî �-àâòîìàòà B ñîïðîâîæäàåòñÿ âûÿñíåíèåì ïðè-
íàäëåæíîñòè äîñòèãíóòîãî ñîñòîÿíèÿ ìíîæåñòâó ôèíàëüíûõ ñîñòîÿíèé, ò.å. ïðè-
ìåíåíèåì àâòîìàòà A� ê äîñòèãíóòîìó ñîñòîÿíèþ ( , ..., )� �q qm1 .
Óòî÷íèì ïîíÿòèå �-àâòîìàòà.
Îïðåäåëåíèå 5. �-àâòîìàò åñòü ëèáî ðàñïðåäåëåííûé �-àâòîìàò ( ,A1 �
� , , )A Um , ëèáî ñóïåðïîçèöèÿ ðàñïðåäåëåííîãî �-àâòîìàòà ( , , , )A A Um1 � è
àâòîìàòà A� íàä àëôàâèòîì Q Qm1
� , äîïóñêàþùèì ÿçûê ñòðîê
� �� �{ }q q q qm m1 1... | ( , , )� .
Îïðåäåëåíèå 6. Ïóñòü B A Am� ( , , , )1 � � — ïðîèçâîëüíûé àâòîìàò. Áóäåì
íàçûâàòü çàäåðæêîé àâòîìàòà B ñóììàðíóþ ñëîæíîñòü âû÷èñëåíèÿ ôóíêöèè ïå-
ðåõîäà � è âû÷èñëåíèÿ ïðåäèêàòà ( , , )q qm1 � ��. Îáîçíà÷èì Z A( )� çàäåðæêó
àâòîìàòà A�.
Äëÿ ïðîèçâîëüíîãî àâòîìàòà A çàäåðæêà Z A( ) åñòü òîò ìèíèìàëüíûé èíòåðâàë
âðåìåíè, êîòîðûé äîëæåí ðàçäåëÿòü ïîñëåäîâàòåëüíûå ñèìâîëû, ïîñòóïàþùèå íà
âõîä àâòîìàòà A, ò.å. âõîäíàÿ ñòðîêà y äîïóñêàåòñÿ àâòîìàòîì A çà âðåìÿ | | ( )y Z A .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 5
Äëÿ �-àâòîìàòà B F A Am� ( , , , )1 � � ïðè ïîñëåäîâàòåëüíîé ðåàëèçàöèè èìå-
åò ìåñòî Z B Z A Z Am
i( ) ( ) ( )� �� �
1
, à ïðè ïàðàëëåëüíîé ðåàëèçàöèè î÷åâèäíî, ÷òî
Z B Z A Z Ai i( ) ( ) max ( )� �� . Íèæå âñå îöåíêè çàäåðæåê Z B( ) ïðèâåäåíû äëÿ ïî-
ñëåäîâàòåëüíîé ðåàëèçàöèè.
Óòâåðæäåíèå 1. Ïóñòü çàäàíû àâòîìàòû A Q q Fi i i i i i� ( , , , )� 0 � � , i m�1, ,� ,
ðàñïîçíàþùèå ÿçûêè ñòðîê L Ai( ). Ðàñïðåäåëåííûé �-àâòîìàò B A A Um� ( , , , )1 �
ðàñïîçíàåò ÿçûê L B( ) òåõ è òîëüêî òåõ òðåêîâ t M D� ( )�� , äëÿ êîòîðûõ
� i it L A( ) ( )� , ãäå � i t( ) — ïðîåêöèÿ òðåêà t íà àëôàâèò �i . Åñëè âñå àâòîìàòû Ai
ìèíèìàëüíû è ( , , )� �1 � m — íàèìåíüøåå ïîêðûòèå êëèêàìè àëôàâèòà çàâèñè-
ìîñòè ( )��D , òî àâòîìàò B òàêæå ìèíèìàëåí. Çàäåðæêà àâòîìàòà ñ óíèâåðñàëü-
íûì ôèíàëüíûì ìíîæåñòâîì åñòü Z B Z Am
i( ) ( )� �
1
.
Äîêàçàòåëüñòâî. Ïóñòü íà âõîä àâòîìàòà B ïîñòóïàåò ñòðîêà y. Ñîãëàñíî
îïðåäåëåíèþ íà âõîä ëîêàëüíîãî êîìïîíåíòà Ai ( , , )i m�1 � ïîïàäåò ïîäïîñëå-
äîâàòåëüíîñòü ñòðîêè y, âñå ñèìâîëû êîòîðîé ïðèíàäëåæàò �i , ò.å. ïðîåêöèÿ
� i y( ). Îòñþäà ñëåäóåò, ÷òî åñëè ñòðîêà äîïóñêàåòñÿ àâòîìàòîì B, òî è êàæäàÿ
ñòðîêà, âõîäÿùàÿ â òðåê [ ]y , òîæå äîïóñêàåòñÿ èì, òàê êàê òðåê îäíîçíà÷íî îïðå-
äåëÿåòñÿ íàáîðîì ïðîåêöèé ëþáîãî åãî ïðåäñòàâèòåëÿ.
ÐÀÑÏÎÇÍÀÂÀÍÈÅ ÂËÎÆÅÍÍÛÕ ÒÐÅÊÎÂ
Ïðèâåäåì ïðèìåðû ÿçûêîâ, ðàñïîçíàâàåìûõ ñ ïîìîùüþ ðàñïðåäåëåííûõ �-àâ-
òîìàòîâ.
Çàäà÷à 1. Çàäàíà ñòðîêà y. Ïîñòðîèòü �-àâòîìàò S ytr ( ), ðàñïîçíàþùèé ÿçûê
òðåêîâ L y t M D t ytr { }( ) ( , )| [ ]� � �� , âëîæåííûõ â òðåê [ ]y .
Çàìå÷àíèå. Äàëåå íèæíèå èíäåêñû tr è st èñïîëüçóþòñÿ ñîîòâåòñòâåííî äëÿ
ÿçûêîâ òðåêîâ è ñòðîê è àâòîìàòîâ, ðàñïîçíàþùèõ ýòè ÿçûêè.
Óòâåðæäåíèå 2. ßçûê L ytr ( ) ðàñïîçíàåòñÿ ðàñïðåäåëåííûì �-àâòîìàòîì
S y S y S y Umtr st st( ) ( ( ( )), , ( ( )), )� � �1 � , ãäå àâòîìàò S yist ( ( ))� ðàñïîçíàåò ïîä-
ïîñëåäîâàòåëüíîñòè ïðîåêöèè � i y( ). Àâòîìàò S ytr ( ) ìîæíî ïîñòðîèòü çà âðåìÿ
O m y y( | | | | )
log . Îí èìååò çàäåðæêó O m( ).
Äîêàçàòåëüñòâî. Èçâåñòíî, ÷òî àâòîìàò S y yst DASG( ) ( )� [8] ðàñïîçíàåò
ÿçûê L yst ( ) âñåõ ñòðîê, ÿâëÿþùèõñÿ ïîäïîñëåäîâàòåëüíîñòÿìè ñòðîêè y. Åãî
ìîæíî ïîñòðîèòü çà âðåìÿ O y y(| | | | )
log . Âîñïîëüçóåìñÿ àâòîìàòîì S yst ( ) äëÿ
ñòðîê ïðè ïîñòðîåíèè �-àâòîìàòà S ytr ( ) äëÿ òðåêîâ. Èç îïðåäåëåíèÿ âëîæåí-
íîñòè òðåêîâ ñëåäóåò, ÷òî äëÿ òîãî ÷òîáû òðåê t M D� ( , )� áûë âëîæåí â òðåê
[ ],y íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû äëÿ âñåõ i m�{ }1, ,� áûëî âûïîëíåíî
� �i ix L y( ) ( ( ))� st , ïðè÷åì äëÿ âñåõ a �� êàæäîå j-å âõîæäåíèå áóêâû a â � i x( )
ñèíõðîíèçèðóåòñÿ ñ j-ì âõîæäåíèåì áóêâû a â � i y( ), à ýòî, â ñâîþ î÷åðåäü, ñî-
ãëàñóåòñÿ ñ ñèíõðîíèçàöèîííûì îãðàíè÷åíèåì äëÿ �-àâòîìàòà. Ñëåäîâàòåëüíî,
ðàñïðåäåëåííûé �-àâòîìàò S y S y S y Umtr st st( ) ( ( ( )), , ( ( )), )� � �1 � ðàñïîçíàåò
ÿçûê L ytr ( ). Ñëîæíîñòü ïîñòðîåíèÿ âûòåêàåò èç îöåíêè ñëîæíîñòè ïîñòðîåíèÿ
àâòîìàòà S y yst DASG( ) ( )� . Àâòîìàò èìååò çàäåðæêó Z S y O m( ( )) ( )tr � .
ÐÀÑÏÎÇÍÀÂÀÍÈÅ ÑÓÔÔÈÊÑÎÂ ÒÐÅÊÀ
Çàäà÷à 2. Çàäàíà ñòðîêà y. Ïîñòðîèòü �-àâòîìàò, ðàñïîçíàþùèé ÿçûê Suff ([ ])y
ñóôôèêñîâ òðåêà [ ]y .
Çàäà÷à ïîñòðîåíèÿ àâòîìàòà, ðàñïîçíàþùåãî ñóôôèêñû ñòðîêè y, èìååò èç-
âåñòíîå ðåøåíèå â âèäå ìèíèìàëüíîãî àâòîìàòà �st ( )t [9–11], êîòîðûé ìîæíî
ïîñòðîèòü çà âðåìÿ O y(| | ) .
6 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
Óòâåðæäåíèå 3. Ïóñòü òðåê t M D� ( , )� ïðåäñòàâëåí ñòðîêîé y t� è ïóñòü
�st ( ( ))� i y , i m�1, ,� , — ìèíèìàëüíûå àâòîìàòû, ðàñïîçíàþùèå ÿçûêè
Suff ( ( ))� i y . Ðàñïðåäåëåííûé �-àâòîìàò � �tr st( ) ( ( ( )),t y� �1 � , �st ( ( )), )� m y U
ðàñïîçíàåò ÿçûê Suff ([ ])y ñóôôèêñîâ òðåêà t y M D� �[ ] ( , )� . Àâòîìàò �tr ( )t
ìîæíî ïîñòðîèòü çà âðåìÿ O m t( | | ), ïðè ýòîì îí èìååò çàäåðæêó Z t O m( ( )) ( )�tr � .
Äîêàçàòåëüñòâî. Êàê èçâåñòíî [9–11], ìèíèìàëüíûé àâòîìàò
�st Suff( (( )))y , ðàñïîçíàþùèé ÿçûê Suff ( )y ñóôôèêñîâ ñòðîêè y, ìîæíî ïîñòðî-
èòü çà âðåìÿ O y(| | ), ïðè ýòîì îí èìååò çàäåðæêó O( )1 . Î÷åâèäíî, ÷òî òðåê �t ÿâëÿ-
åòñÿ ñóôôèêñîì òðåêà t òîãäà è òîëüêî òîãäà, êîãäà äëÿ âñåõ i m�1, ,� ñòðîêà
� i t( )� ÿâëÿåòñÿ ñóôôèêñîì ñòðîêè � i t( ). Îòñþäà ñëåäóåò, ÷òî àâòîìàò �tr ( )t äå-
éñòâèòåëüíî ðàñïîçíàåò ÿçûê Suff ( )t ñóôôèêñîâ òðåêà t. Î÷åâèäíî, ÷òî àâòîìàò
�tr ( )t ìîæíî ïîñòðîèòü çà âðåìÿ O m y( | | ) è Z t O m( ( )) ( )�tr � .
ÐÀÑÏÎÇÍÀÂÀÍÈÅ ÊÎÍÅ×ÍÎÃÎ ßÇÛÊÀ ÒÐÅÊÎÂ
Ìíîæåñòâî ñòðîê { }x xn1, , *
� �� ìîæíî, ñ îäíîé ñòîðîíû, ðàññìàòðèâàòü êàê
ýëåìåíòû ñâîáîäíîé ïîëóãðóïïû, à ñ äðóãîé — êàê ìíîæåñòâî ïðåäñòàâèòå-
ëåé òðåêîâ t x t xn n1 1� �[ ], , [ ]� . Ìíîæåñòâî ñòðîê îáîçíà÷èì X x xn� { }1, ,� ,
à ìíîæåñòâî ñîîòâåòñòâóþùèõ òðåêîâ [ ] [ ]|X x x X� �{ }.
Çàäà÷à 3. Ïî çàäàííîìó ìíîæåñòâó ñòðîê X x xn� { }1, ,� — ïðåäñòàâèòåëåé
òðåêîâ, ïîñòðîèòü �-àâòîìàò, ðàñïîçíàþùèé ïðèíàäëåæíîñòü ïðîèçâîëüíîé
ñòðîêè y ÿçûêó [ ] [ ] [ ]x x Xn1
�� .
Ðåøåíèå çàäà÷è èñïîëüçóåò èçâåñòíûé [11, Prop. 5.3] àëãîðèòì ïîñòðîåíèÿ
ìèíèìàëüíîãî àâòîìàòà T Xst ( ), äîïóñêàþùåãî ÿçûê ñòðîê X x xn� { }1, ,� .
Î÷åâèäíî, ÷òî àâòîìàò T X X p a pa Xst Pref( ) ( ( ), , {( , , )}, )� � äîïóñêàåò ÿçûê X .
Çäåñü � — íà÷àëüíîå ñîñòîÿíèå, a �� , p pa X, ( )�Pref , ãäå Pref ( )X �
� � � � � �{ { } }u i v i n v x uvi� �* *| , : , , , ,1 � åñòü ìíîæåñòâî ïðåôèêñîâ âñåõ ñòðîê
x Xi � .
ßçûêó òðåêîâ [ ] [ ] [ ]X x xn�
1 � ïîñòàâèì â ñîîòâåòñòâèå m ÿçûêîâ
ñòðîê — ïðîåêöèé íà àëôàâèòû �i , i m�1, ,� , òðåêîâ, âõîäÿùèõ â [ ]X : � i X( ) �
� { }� �i i nx x( ), , ( )1 � , i m�1, ,� .
Ðàññìîòðèì ðàñïðåäåëåííûé �-àâòîìàò, ïîñòðîåííûé èç àâòîìàòîâ
T Xist ( ( ))� . Òàêîé �-àâòîìàò íå ðåøàåò äàííîé çàäà÷è, ÷òî âèäíî èç ñëåäóþùåãî
ïðèìåðà.
Ïðèìåð. Ïóñòü � � { }a b c, , , D a b b c� { }( , ), ( , ) , �1 � { }a b, , �2 � { }c b, ,
X abc cba� { }, . Òîãäà �� ( ) ,X ab ba� { }, �2 ( ) ,X bc cb� { }. Ðàñïðåäåëåííûé �-àâ-
òîìàò ñ êîìïîíåíòàìè T Xst ( ( ))�1 è T Xst ( ( ))�2 äîïóñòèò òàêæå òðåêè
[ ], [ ] [ ]acb bca X� . Ñëåäîâàòåëüíî, êîíå÷íûå ÿçûêè òðåêîâ, âîîáùå ãîâîðÿ, íåëüçÿ
ðàñïîçíàòü ðàñïðåäåëåííûìè àâòîìàòàìè, è ìåõàíèçì îòñåâà ëèøíèõ òðåêîâ
îáåñïå÷èâàåòñÿ ñóïåðïîçèöèåé ðàñïðåäåëåííîãî �-àâòîìàòà ñ àâòîìàòîì A�.
Óòâåðæäåíèå 4. Ïóñòü àâòîìàò T Xst ( ) äîïóñêàåò ÿçûê ñòðîê
X x xn� { }1, ,� . Òîãäà �-àâòîìàò T X T X T Xm Ttr st st tr
( ) ( ( ( )), , ( ( )), )� � � �1 �
äîïóñêàåò ÿçûê òðåêîâ [ ] [ ] [ ] ( , )X x x M Dn�
�1 � � .
Çäåñü � i i nX x x( ) ( ), , ( )� { }� �1 � , i m�1, ,� , — ÿçûêè ïðîåêöèé ñòðîê èç
ìíîæåñòâà X íà êëèêè, è ôèíàëüíîå ìíîæåñòâî èìååò âèä
� � �T m mq q X X x X
tr
{� �
� �( , , ) ( ) ( )| :1 1� �
�
�
i
x
i
i q i m
( )
, , , .� ��� �1 � } (1)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 7
Àâòîìàò T Xtr ( ) ìîæíî ïîñòðîèòü çà âðåìÿ O ( | | )m X d� log , ãäå | | | |X x
i
n
i� �� 1
,
d — ìàêñèìàëüíàÿ ñòåïåíü ñîñòîÿíèé àâòîìàòîâ T X T Xmst st( ( )), , ( ( ))� �1 � .
Çàäåðæêà àâòîìàòà Z T X m d( ( )) ( )tr log�O .
Äîêàçàòåëüñòâî. Èç ôîðìóëû (1) òðèâèàëüíî ñëåäóåò, ÷òî àâòîìàò T Xtr ( )
äîïóñêàåò ÿçûê òðåêîâ [ ] ( , )X M D� � , òàê êàê ñîñòîÿíèå ( , , )q qm T1 � ��
tr
äîñ-
òèãàåòñÿ òîãäà è òîëüêî òîãäà, êîãäà íà âõîä àâòîìàòà T Xtr ( ) ïîäàåòñÿ ñòðîêà y,
ïðåäñòàâëÿþùàÿ îäèí èç òðåêîâ ÿçûêà [ ]X .
Ðàññìîòðèì àâòîìàò TRIE tr , ñòðîÿùèé àâòîìàò T Xtr ( ). Â [11, Prop. 5.3] îïè-
ñàí àâòîìàò TRIE st , ñòðîÿùèé òàêîé ìèíèìàëüíûé àâòîìàò T Xst ( ) äëÿ ñòðîê, êî-
òîðûé äîïóñêàåò ÿçûê ñòðîê X x xn� { }1, ,� â àëôàâèòå � . Àâòîìàò TRIE st ïî
îêîí÷àíèè ÷òåíèÿ ïîñëåäîâàòåëüíîñòè ñòðîê X x xn� { }1, ,� ïîïàäàåò â ôèíàëü-
íîå ñîñòîÿíèå T X Q Fst ( ) ( , , , )� � � , ãäå Q — ìíîæåñòâî ñîñòîÿíèé, � — íà÷àëüíîå
ñîñòîÿíèå, F — ìíîæåñòâî ôèíàëüíûõ ñîñòîÿíèé, � — ôóíêöèÿ ïåðåõîäà àâòî-
ìàòà T Xst ( ). Àâòîìàò TRIE st ñòðîèò àâòîìàò T Xst ( ) çà âðåìÿ O (| | )X d� log . Çàäåð-
æêà àâòîìàòà Z T X d( ( )) ( )st log�O è ÷èñëî ñîñòîÿíèé card( ) (| | )Q X�O .
Äëÿ òîãî ÷òîáû â äàëüíåéøåì ïîñòðîèòü àâòîìàò äëÿ âû÷èñëåíèÿ ïðåäèêàòà
�Ttr
, ìîäèôèöèðóåì àâòîìàò TRIE st òàê, ÷òîáû âìåñòî ìíîæåñòâà ôèíàëüíûõ ñî-
ñòîÿíèé ïîëó÷àëàñü ñòðóêòóðà — óïîðÿäî÷åííûé ñïèñîê ôèíàëüíûõ ñîñòîÿíèé
F x xn
* ( , , )� 1 � , ñîîòâåòñòâóþùèé ÷òåíèþ ïîñëåäîâàòåëüíîñòè X . Îáîçíà÷èì
ýòîò ìîäèôèöèðîâàííûé àâòîìàò TRIE st
� .
Ïîëîæèì TRIE TRIE TRIEtr st st� � �( , , , )� U — ðàñïðåäåëåííûé �-àâòîìàò.
Àâòîìàò TRIE tr ïðè ÷òåíèè ïîñëåäîâàòåëüíîñòè ñòðîê x xn1, ,� ñòðîèò âñå ëî-
êàëüíûå êîìïîíåíòû äëÿ òðåáóåìîãî àâòîìàòà T Xtr ( ), ò.å. ïðèõîäèò â ñîñòîÿ-
íèå (( , , , ), , ( , , , ))* *Q F Q Fm m m1 1 1� � � �� , ãäå ( , , , ) ( ( )),*Q F T X1 1 1 1� � � st � �
� , ( , , , ) ( ( ))*Q F T Xm m m m� � � st � — èñêîìûå ëîêàëüíûå êîìïîíåíòû è
F q qi i in
* ( , , )� 1 � , i m�1, ,� , — ñïèñîê ôèíàëüíûõ ñîñòîÿíèé àâòîìàòà
T Xist ( ( ))� . Êàæäûé ñïèñîê ôèíàëüíûõ ñîñòîÿíèé ñîîòâåòñòâóåò ïîðÿäêó ñòðîê
â X x xn� { }1, ,� , ò.å. àâòîìàò T Xist ( ( ))� ïîïàäàåò â ñîñòîÿíèå qij ïîñëå ïðî÷òå-
íèÿ ñòðîêè x j .
Òîãäà ôèíàëüíîå ìíîæåñòâî �-àâòîìàòà T Xtr ( ) åñòü �T jq
tr
{� ( ,1 �
� �, )| , ,q j nmj �1 }, ãäå n X� card( ), ò.å. �Ttr
— ìíîæåñòâî íàáîðîâ ñîñòîÿíèé
÷àñòè÷íûõ àâòîìàòîâ, âõîäÿùèõ â ñïèñêè ôèíàëüíûõ ñîñòîÿíèé àâòîìàòîâ
T X T Xmst st( ( )), , ( ( ))� �1 � ñ îäèíàêîâûìè íîìåðàìè. Åãî ìîæíî ëåãêî ïîñòðî-
èòü ïî ñïèñêàì F Fm1
* *, ,� , ïîëó÷åííûì �-àâòîìàòîì TRIE tr , è ïðåäèêàò
( , , )q qj mj T1 � ��
tr
ìîæíî âû÷èñëèòü çà âðåìÿ O ( )m ñ ïîìîùüþ àâòîìàòà
A T
T T� �
tr trst� ( ), ðàñïîçíàþùåãî ÿçûê ñòðîê �Ttr
.
Àëãîðèòì ïîñòðîåíèÿ T Xtr ( )
Øàã 1. Ïðèìåíÿåòñÿ àâòîìàò TRIE tr ê ïîñëåäîâàòåëüíîñòè X . Çà âðåìÿ
O ( | | )m X� áóäóò ïîñòðîåíû àâòîìàòû ( , , , ) ( ( )),*U F T X1 1 1 1� � � st � �
� , ( , , , ) ( ( ))*U F T Xm m m m� � � st � ñî ñïèñêàìè F Fm1
* *, ,� .
Øàã 2. Ïî ñïèñêàì F Fm1
* *, ,� ñòðîèòñÿ ìíîæåñòâî ñòðîê �Ttr
�
� �{ }q q j nj mj1 1... | , ,� , ê êîòîðîìó ïðèìåíÿåòñÿ àâòîìàò TRIE tr . Ðåçóëüòàòîì ÿâ-
ëÿåòñÿ àâòîìàò A T
T T� �
tr trst� ( ), ðàñïîçíàþùèé ôèíàëüíûå ñîñòîÿíèÿ àâòîìàòà
T Xtr ( ) çà âðåìÿ O ( )m .
8 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
Ñëåäîâàòåëüíî, çàäåðæêà Z T X m d( ( )) ( )tr log�O . Îöåíêà âðåìåíè ïîñòðî-
åíèÿ T Xtr ( ) âûòåêàåò èç îöåíêè âðåìåíè ïîñòðîåíèÿ T Xst ( ).
ÏÎÈÑÊ ÑÓÔÔÈÊÑÀ ÒÐÅÊÀ Â ÑËÎÂÀÐÅ
Çàäà÷à 4. Ïî ñëîâàðþ, ò.å. ìíîæåñòâó ñòðîê X x xn� { }1, ,� â àëôàâèòå �, ïî-
ñòðîèòü �-àâòîìàò, äîïóñêàþùèé ÿçûê [ ]([ ] [ ])*� x xn1
� .
Äàííîå ðåøåíèå çàäà÷è òàêæå îñíîâàíî íà èçâåñòíîì [11] àëãîðèòìå ðåøå-
íèÿ çàäà÷è ïîñòðîåíèÿ àâòîìàòà äëÿ ÿçûêà ñòðîê �* X . Ðàññìîòðèì åãî ïîäðîá-
íåå. Êàê èçâåñòíî [10,11], àâòîìàò
D X X X X p a h pa pXst Pref Pref Pref( ) ( ( ), , ( ) , {( , , ( ))|*� �� � ( ), })X a ��
äîïóñêàåò ÿçûê �* X . Çäåñü h vX ( ) — äëèííåéøèé ñóôôèêñ ñòðîêè v, ïðèíàä-
ëåæàùèé Pref Pref( ) ( )X U x
i
n
i� �1
.
Ñîãëàñíî [11, Th. 5.2] àâòîìàò D Xst ( ) ìîæíî ïîñòðîèòü çà âðåìÿ
O (| | )X d� log , ãäå d — ìàêñèìàëüíàÿ ñòåïåíü ñîñòîÿíèé àâòîìàòà D Xst ( ) . Çà-
äåðæêà Z D X l d( ( )) ( )st log�
O , ãäå l — ìàêñèìàëüíàÿ äëèíà ñòðîê ñëîâàðÿ X .
×èñëî ñîñòîÿíèé card( ) (| | )Q X�O .
Èçâåñòíî, ÷òî ãðàô ïåðåõîäîâ àâòîìàòà D Xst ( ) ìîæíî ïîëó÷èòü èç ãðàôà ïå-
ðåõîäîâ àâòîìàòà T X X p a pa Xst Pref { }( ) ( ( ), , ( , , ) , )� � , äîïóñêàþùåãî ÿçûê X ,
åñëè ê íåìó äîáàâèòü ññûëêè è ôèíàëüíûå âåðøèíû. Ññûëêà ( , )q q1 2 — íåïî-
ìå÷åííàÿ äóãà, ãäå q q X1, ( )�Pref , äîáàâëÿåòñÿ, åñëè âûïîëíåíî óñëîâèå; q2 —
íàèáîëüøèé ñîáñòâåííûé ñóôôèêñ ñòðîêè q1.
Ìíîæåñòâî ôèíàëüíûõ âåðøèí àâòîìàòà D Xst ( ) íàðàùèâàåòñÿ, íà÷èíàÿ ñ
ìíîæåñòâà F X� ôèíàëüíûõ âåðøèí àâòîìàòà T X Q Fst ( ) ( , , , )� � � , ñ ïîìîùüþ
ñëåäóþùåé èòåðàòèâíîé ïðîöåäóðû äîïîëíåíèÿ. Åñëè ( , )q q1 2 — ññûëêà è ñî-
ñòîÿíèå q X2 ��
* — ôèíàëüíîå, òî ñîñòîÿíèå q1 äîáàâëÿåòñÿ ê ìíîæåñòâó
ôèíàëüíûõ âåðøèí.
Ññûëêè îáðàçóþò íà ìíîæåñòâå Q äåðåâî ññûëîê ! ( ) ( , )X Q� �� ñ êîðíåì �.
Îáîçíà÷èì ! X q( ) ìíîæåñòâî ñîñòîÿíèé, äîñòèæèìûõ èç ñîñòîÿíèÿ q â äå-
ðåâå ññûëîê ! ( )X .
Ïóñòü ÷èñëà k k k n X i ll i1 1 1, , ( ( ), , , )� �� � � �card òàêîâû, ÷òî
x x x xk k k kl l1 2 1
� �
"
Suff Suff, ,� è äëÿ âñÿêîãî j k k l�{ }1, ,� èìååò ìåñòî
x xk jl
�Suff . Ëåãêî âèäåòü, ÷òî ïåðåõîä ��
y
kx
s
â àâòîìàòå D Xst ( ) äëÿ íåêîòîðî-
ãî 1� �s l èìååò ìåñòî òîãäà è òîëüêî òîãäà, êîãäà y A x� * äëÿ âñåõ
x x x xX k k ks s
� �! ( ) , ,{ }
1
� è y A x j� * äëÿ j k k l�{ }1, ,� .
Ìîäèôèöèðóåì àâòîìàò D Xst ( ), äîáàâèâ ê êàæäîìó åãî ñîñòîÿíèþ q èíôîð-
ìàöèþ î ôèíàëüíûõ ñîñòîÿíèÿõ, ïðèíàäëåæàùèõ ìíîæåñòâó ! X q( ): ñ êàæäûì
ñîñòîÿíèåì q Q� ñâÿæåì âåêòîð P q p q x p q xD X D X D X nst st st( ) ( ) ( )( ) ( ( , ), , ( , ))� 1 � ,
ãäå äëÿ j n�1, ,�
p q x
x q
D X j
j X
st
1, åñëè
0 â ïðîòèâíîì ñëó( )
( , )
( ),
�
��
�
�
!
÷àå.
Âåêòîðû P qD Xst ( ) ( ) ìîãóò áûòü ïîëó÷åíû â ïðîöåññå ïîñòðîåíèÿ àâòîìàòà
D Xst ( ). Êàæäîå ñîñòîÿíèå q â D Xst ( ) çàìåíèì ïàðîé a qD Xst ( ) ( ) �
� ( , ( ))( )q P qD Xst
, ñîõðàíèâ ñîîòâåòñòâóþùèå ïåðåõîäû. Èìåííî ýòè ïàðû áóäåì
ñ÷èòàòü ñîñòîÿíèÿìè ïðåîáðàçîâàííîãî àâòîìàòà D X Q Fst
� � � �( ) ( , , , )� � . Ìíîæåñòâîì
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 9
ôèíàëüíûõ ñîñòîÿíèé àâòîìàòà D Xst
� ( ) áóäåò ìíîæåñòâî F
D Xst
� �
( )
� �{ }
st
a q q XD X( ) ( )| . Âû÷èñëÿåòñÿ àâòîìàò D Xst
� ( ) çà âðåìÿ O ( | | )n X d� log .
Òåïåðü ðàññìîòðèì çàäàííîå ìíîæåñòâî ñòðîê X � �* êàê ìíîæåñòâî ïðåä-
ñòàâèòåëåé òðåêîâ èç ñëîâàðÿ [ ] [ ]| , , ( , )X x i n M Di� � �{ }1 � � . Íàøà öåëü — ïî-
ñòðîåíèå �-àâòîìàòà D Xtr ( ), äîïóñêàþùåãî ÿçûê òðåêîâ [ ]*� X .
Óòâåðæäåíèå 6. Ïóñòü àâòîìàò D Xst ( ) äîïóñêàåò ÿçûê ñòðîê X �
� { }x xn1, ,� . ßçûê òðåêîâ [ ]*� X ðàñïîçíàåòñÿ �-àâòîìàòîì D Xtr ( ) �
� � �( ( ( )), , ( ( )), )D X D Xm Dst st tr
� � �1 � . Çäåñü � i i i nX x x( ) ( ), , ( )� { }� �1 � ,
i m�1, ,� , — ÿçûêè ïðîåêöèé íà êëèêè è ôèíàëüíîå ìíîæåñòâî èìååò âèä
� � � �D D D m m D X
a x a x q j p
itr st st st
( ( ( )), , ( ( ))( ))| :
( ( ))1 � � ( , ) .q xi j
i
m
�
�
�
�
#
$
%�
& 1
1
(2)
Äëÿ ïîñòðîåíèÿ àâòîìàòà íåîáõîäèìî âðåìÿ O ( | | )mn X d� log , ãäå
| | | |X x
i
n
i� �� 1
, d — ìàêñèìàëüíàÿ ñòåïåíü ñîñòîÿíèé àâòîìàòîâ D Xst ( ( )),�1 �
� , ( ( ))D Xmst � , l — ìàêñèìàëüíàÿ äëèíà ñòðîê â X . Çàäåðæêà Z D X( ( ))tr �
�
O (max , ){ log }l d mn . ×èñëî ñîñòîÿíèé O (| | )X .
Äîêàçàòåëüñòâî. Ïðèâåäåì àëãîðèòì ïîñòðîåíèÿ àâòîìàòà D Xtr ( ). Îí ñâî-
äèòñÿ ê ïîñòðîåíèþ àâòîìàòîâ D X D Xmst st
� �( ( )), , ( ( ))� �1 � è ïîñòðîåíèþ àâòî-
ìàòà A
D� tr
.
Øàã 1. Â ïðîöåññå ÷òåíèÿ ñòðîê ìíîæåñòâà X ñòðîÿòñÿ m àâòîìàòîâ
D X Q Fi i i i D Xi
st
st
� � � �( ( )) ( , , , )
( ( ))
�
�
� � , i m�1, ,� .
Øàã 2. Ëåãêî âèäåòü, ÷òî ãëîáàëüíîå ñîñòîÿíèå ( ( ),( ( ))a qD Xst �1 1 �
� , ( ))( ( ))a qD X mmst �
àâòîìàòà D Xtr ( ) ÿâëÿåòñÿ ôèíàëüíûì òîãäà è òîëüêî òîãäà,
êîãäà ñóùåñòâóåò ÷èñëî 1� �j n òàêîå, ÷òî äëÿ âñåõ i m�1, ,� èìååò ìåñòî
p q xD X i jist ( ( )) ( , )� �1. Àâòîìàò A
D� tr
, ïðîâåðÿþùèé ýòî óñëîâèå, ìîæíî ïîñòðî-
èòü çà âðåìÿ O ( )mn .
Àâòîìàò D Xtr ( ) ïîñòðîåí çà âðåìÿ O ( | | )mn X d� log . Çàäåðæêà Z D X( ( ))tr �
�
O (max , ){ log }l d mn .
Àâòîìàò íàä ñòðîêàìè D Xst ( ) ìîæíî èñïîëüçîâàòü äëÿ íàõîæäåíèÿ â ïðîèç-
âîëüíîé ñòðîêå y âñåõ âõîæäåíèé ñòðîê èç ÿçûêà X â êà÷åñòâå ôàêòîðîâ ñòðîêè y,
òàê êàê â ïðîöåññå ÷òåíèÿ âõîäíîé ñòðîêè y àâòîìàò ïðèõîäèò â ôèíàëüíîå ñî-
ñòîÿíèå êàæäûé ðàç, êîãäà ÷èòàåòñÿ ïîñëåäíÿÿ áóêâà âõîæäåíèÿ êàêîé-ëèáî
ñòðîêè x X� â y. Îäíàêî àâòîìàò D Xtr ( ) íåëüçÿ èñïîëüçîâàòü äëÿ íàõîæäåíèÿ â
ïðîèçâîëüíîì òðåêå [ ]y âñåõ ôàêòîðîâ — òðåêîâ ÿçûêà [ ]X . Åãî ìîæíî èñïîëü-
çîâàòü äëÿ áîëåå ÷àñòíîé çàäà÷è: äëÿ ïîèñêà â ïðîèçâîëüíîé ñòðîêå
y y y y� �1, ... | |
*� âñåõ ïðåôèêñîâ y y yk� 1, ..., ñòðîêè y, äëÿ êîòîðûõ ñóùåñòâóåò
x Xj � [ ] òàêîå, ÷òî [ ] [ ... ]x y yj k�Suff 1 .
Óòâåðæäåíèå 7. �-àâòîìàò D Xtr ( ), ïîñòðîåííûé äëÿ ñëîâàðÿ X , ðàñïîçíàåò
â ïðîèçâîëüíîé ñòðîêå y��* âñå ïðåôèêñû y y yk1 2 ... òàêèå, ÷òî ñóùåñòâóåò
x Xj �[ ] òàêîå, ÷òî [ ] [ ... ]x y yj k�Suff 1 . À èìåííî D Xtr ( ) ïåðåðàáàòûâàåò ñòðîêó y
â ïîñëåäîâàòåëüíîñòü ãëîáàëüíûõ âíóòðåííèõ ñîñòîÿíèé q q y1, , | |� òàêóþ, ÷òî
q k y
k D� ��
tr
, | | , òîãäà è òîëüêî òîãäà, êîãäà ñóùåñòâóåò öåëîå ÷èñëî j n� òà-
êîå, ÷òî [ ] [ ... ]x y yj k�Suff 1 .
10 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
Çàìåòèì, ÷òî òåì ñàìûì D Xtr ( ) íàõîäèò ôàêòîðû (íå âñå!) òðåêà [ ]y , êîòî-
ðûå ïðèíàäëåæàò [ ]X .
Ïðåäñòàâëÿåò èíòåðåñ çàäà÷à, ñâÿçàííàÿ ñ ïðåäûäóùåé: ïîñòðîèòü àâòîìàò,
íàõîäÿùèé âñå âõîæäåíèÿ òðåêîâ èç ñëîâàðÿ [ ]X â êà÷åñòâå ôàêòîðîâ â òðåê [ ]y ,
çàäàííûé ñâîèì ïðåäñòàâèòåëåì y. Îäíàêî äëÿ ýòîãî íåîáõîäèì ïðîñìîòð âñåõ
ïðåôèêñîâ òðåêà [ ]y , ÷èñëî êîòîðûõ îöåíèâàåòñÿ êàê O (| | )y � , ãäå � — ÷èñëî
ñèìâîëîâ, âõîäÿùèõ â íàèáîëüøóþ êëèêó ãðàôà íåçàâèñèìîñòè àëôàâèòà � [7].
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. D i k e r t V . , R o z e n b e r g G . The book of traces // Handbook of Formal Languages. 3. Beyond
Words. — N.Y.: Springer-Verlag — 1997. — 390 p.
2. M a z u r k i e w i c z A . Concurrent program schemes and their interpretations // DAIMI Rep. PB.
— Aarhus: Aarhus University, 1977. — 78. — P. 16–23.
3. Z i e l o n k a W . Notes on finite asynchronous automata // RAIRO Inf. Th. Appl. — 1987. — 21,
N 2. — P. 99–135.
4. D u b o c C . Mixed product and asynchronous automata // TCS. — 1986. — 48. — P. 183–199.
5. M o r i n R . Decompositions of asynchronous systems // CONCUR, LNCS–1466, 1998. —
P. 549–564.
6. M o r i n R . Concurrent automata vs. asynchronous systems // LNCS–3618, 2005. — P. 686–698.
7. 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. — 32M. — P. 141–152.
8. B a e z a - Y a t e s R . A . Searching sequences // Theoretical Comput. Sci. — 1991. — 78, N 2. —
P. 363–376.
9. C r o c h e m o r e M . , H a n c a r t C . , L e c r o q T . Algorithms on strings // Cambridge Univ.
Press, 2007. — 58 p.
10. 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.
11. C r o c h e m o r e M . , H a n c a r t C . Automata for matching patterns. // Handbook of Formal Lan-
guages. 2. Linear Modeling. — N.Y.: Springer-Verlag, 1997. — P. 399–462.
12. A h o A . V . , C o r a s i c k M . J . Efficient string matching: an aid to bibliographic research //
Comm. of the ACM. — 1975. — 18. — P. 333–340.
13. S h a h b a z y a n K . V . , S h o u k o u r i a n Y u . H . Inclusion problems in trace monoids // CSIT.
— 2009. — P. 65–69.
Ïîñòóïèëà 07.07.2011
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 11
|