О сложности анализа автоматов над конечным кольцом
Досліджено загальну схему, призначену для обчислювання оцінок, що базуються на потужності підмножини заданої множини автоматів над скінченним комутативно-асоціативним кільцем з одиницею. Запропоновано схему розв’язку систем поліноміальних рівнянь, що базується на класах асоційованих елементів кільця...
Saved in:
| Date: | 2010 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Series: | Кибернетика и системный анализ |
| Subjects: | |
| Online Access: | http://dspace.nbuv.gov.ua/handle/123456789/45240 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | О сложности анализа автоматов над конечным кольцом / В.В. Скобелев, В.Г. Скобелев // Кибернетика и системный анализ. — 2010. — № 4. — С. 17-30. — Бібліогр.: 17 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-45240 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-452402013-06-11T03:08:47Z О сложности анализа автоматов над конечным кольцом Скобелев, В.В. Скобелев, В.Г. Кибернетика Досліджено загальну схему, призначену для обчислювання оцінок, що базуються на потужності підмножини заданої множини автоматів над скінченним комутативно-асоціативним кільцем з одиницею. Запропоновано схему розв’язку систем поліноміальних рівнянь, що базується на класах асоційованих елементів кільця. Встановлено низку загальних характеристик автоматів над цим кільцем. The paper considers a general scheme to obtain estimates based on the cardinality of subsets of a fixed set of automata over some finite commutative-associative ring with unit element. A scheme is proposed to solve parametric systems of polynomial equations based on classes of associated elements of the ring. Some general characteristics of automata over the ring are established. 2010 Article О сложности анализа автоматов над конечным кольцом / В.В. Скобелев, В.Г. Скобелев // Кибернетика и системный анализ. — 2010. — № 4. — С. 17-30. — Бібліогр.: 17 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/45240 519.713+512.552 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 |
2010 |
| topic_facet |
Кибернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/45240 |
| citation_txt |
О сложности анализа автоматов над конечным кольцом / В.В. Скобелев, В.Г. Скобелев // Кибернетика и системный анализ. — 2010. — № 4. — С. 17-30. — Бібліогр.: 17 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT skobelevvv osložnostianalizaavtomatovnadkonečnymkolʹcom AT skobelevvg osložnostianalizaavtomatovnadkonečnymkolʹcom |
| first_indexed |
2025-07-04T03:55:18Z |
| last_indexed |
2025-07-04T03:55:18Z |
| _version_ |
1836687107186229248 |
| fulltext |
ÓÄÊ 519.713+512.552
Â.Â. ÑÊÎÁÅËÅÂ, Â.Ã. ÑÊÎÁÅËÅÂ
Î ÑËÎÆÍÎÑÒÈ ÀÍÀËÈÇÀ ÀÂÒÎÌÀÒÎÂ
ÍÀÄ ÊÎÍÅ×ÍÛÌ ÊÎËÜÖÎÌ
Êëþ÷åâûå ñëîâà: êîíå÷íûå àâòîìàòû, êîíå÷íûå êîëüöà, ñèììåòðè÷íûå ïîòî÷-
íûå øèôðû.
ÂÂÅÄÅÍÈÅ
Íåñìîòðÿ íà áîëüøîå ìíîãîîáðàçèå èñïîëüçóåìûõ ìàòåìàòè÷åñêèõ ìîäåëåé
(÷àñòî íå ñðàâíèìûõ ìåæäó ñîáîé) â ïîñëåäíåå âðåìÿ â êðèïòîãðàôèè íàìåòè-
ëàñü óñòîé÷èâàÿ òåíäåíöèÿ ïåðåõîäà îò ÷èñòî êîìáèíàòîðíûõ ìîäåëåé ê ìàòåìà-
òè÷åñêèì ìîäåëÿì, ïîñòðîåííûì íà îñíîâå êîíå÷íûõ àëãåáðàè÷åñêèõ ñèñòåì.
 òî æå âðåìÿ ìíîãî÷èñëåííûå ïîïûòêè íåïîñðåäñòâåííîãî ïðèìåíåíèÿ õàîòè-
÷åñêèõ äèíàìè÷åñêèõ ñèñòåì [1] ïðè ðåøåíèè çàäà÷ êðèïòîãðàôèè ïîêàçàëè, ÷òî
ïðè ýòîì âîçíèêàåò çàäà÷à âûáîðà òî÷íîñòè âû÷èñëåíèé, îáåñïå÷èâàþùåé êîð-
ðåêòíîñòü ïðîöåññà «øèôðîâàíèå – ðàñøèôðîâêà». Ñ ìàòåìàòè÷åñêîé òî÷êè çðå-
íèÿ äëÿ êóñî÷íî-ëèíåéíûõ õàîòè÷åñêèõ îòîáðàæåíèé åå ðåøåíèå íå î÷åíü ñëîæ-
íî [2, 3]. Îäíàêî äàæå äëÿ êîíêðåòíûõ òèïîâ íåëèíåéíûõ õàîòè÷åñêèõ äèíàìè-
÷åñêèõ ñèñòåì ðåøåíèå ýòîé çàäà÷è ïîêà íå íàéäåíî. Åñòåñòâåííûì ñïîñîáîì
èçáåæàòü îøèáîê, ñâÿçàííûõ ñ îêðóãëåíèåì, ÿâëÿåòñÿ ïåðåõîä â óðàâíåíèÿõ,
îïðåäåëÿþùèõ õàîòè÷åñêóþ äèíàìè÷åñêóþ ñèñòåìó, ê îïåðàöèÿì â êîíå÷íîé àë-
ãåáðàè÷åñêîé ñèñòåìå. Ïåðå÷èñëåííûå ôàêòîðû ñòèìóëèðîâàëè â ïîñëåäíåå âðå-
ìÿ èíòåðåñ ê èññëåäîâàíèþ àâòîìàòîâ, ïðåäñòàâëåííûõ ñèñòåìàìè óðàâíåíèé
íàä êîíå÷íûìè àëãåáðàè÷åñêèìè ñèñòåìàìè.
Îñíîâû òåîðèè ëèíåéíûõ àâòîìàòîâ íàä ïîëåì GF pk( ) (ãäå p — ïðîñòîå ÷èñ-
ëî, k �N) ñ ïîçèöèè òåîðèè ñèñòåì ðàçðàáîòàíû ïî÷òè 40 ëåò òîìó íàçàä [4, 5].
Îäíàêî ýòè èññëåäîâàíèÿ íå äàëè ýôôåêòèâíûõ ðåçóëüòàòîâ äëÿ ðåøåíèÿ çàäà÷
êðèïòîãðàôèè â ñèëó ñëåäóþùèõ ïðè÷èí.
Ñâîéñòâî «áûòü ëèíåéíûì àâòîìàòîì» íàêëàäûâàåò ñóùåñòâåííûå îãðàíè÷å-
íèÿ íà àâòîìàòíîå îòîáðàæåíèå, ðåàëèçóåìîå èíèöèàëüíûì àâòîìàòîì (ïî-âèäèìî-
ìó, íàèáîëåå çíà÷èìûì ïðèëîæåíèåì ëèíåéíûõ àâòîíîìíûõ àâòîìàòîâ ÿâëÿåòñÿ
èõ èñïîëüçîâàíèå â êà÷åñòâå ãåíåðàòîðîâ ïñåâäîñëó÷àéíûõ ïîñëåäîâàòåëüíîñòåé).
 ðàáîòàõ [4, 5] íå ðàññìàòðèâàëèñü çàäà÷è, êîòîðûå áû ñ ïîçèöèè òåîðèè àëãîðèò-
ìîâ îáîñíîâûâàëè âû÷èñëèòåëüíóþ ñòîéêîñòü ïîòî÷íûõ øèôðîâ, ïîñòðîåííûõ íà
îñíîâå àâòîìàòîâ íàä ïîëåì GF pk( ). Òàêèå çàäà÷è ôîðìèðóþò ñïåöèàëüíîå íà-
ïðàâëåíèå â òåîðèè ýêñïåðèìåíòîâ ñ àâòîìàòàìè (íåêîòîðûå òèïû ýêñïåðèìåíòîâ
ñ àâòîìàòàìè íàä êîíå÷íûìè ïîëÿìè ðàññìîòðåíû â [6–8]). Ïðåäìåòîì åãî èññëå-
äîâàíèÿ ÿâëÿåòñÿ àíàëèç ñëîæíîñòè èäåíòèôèêàöèè ïàðàìåòðè÷åñêè íàñòðàèâàå-
ìûõ îáðàòèìûõ àâòîìàòîâ, ìíîæåñòâà íåïîäâèæíûõ òî÷åê îòîáðàæåíèÿ,
ðåàëèçóåìîãî èíèöèàëüíûì îáðàòèìûì àâòîìàòîì, à òàêæå èçìåíåíèÿ ïîâåäåíèÿ
îáðàòèìîãî àâòîìàòà ïðè âàðèàöèè åãî ïàðàìåòðîâ è/èëè íà÷àëüíîãî ñîñòîÿíèÿ.
Èçâåñòíî, ÷òî ïîëå — ñïåöèàëüíûé ñëó÷àé êîììóòàòèâíî-àññîöèàòèâíîãî êîëüöà
ñ åäèíèöåé [9]. Ïðè ýòîì â êîëüöå (â îòëè÷èå îò ïîëÿ) íàëè÷èå äåëèòåëåé íóëÿ ñóùåñ-
òâåííî óñëîæíÿåò ñòðóêòóðó ìíîæåñòâ ðåøåíèé óðàâíåíèé (äàæå ëèíåéíîå óðàâíåíèå
ìîæåò èìåòü ýêñïîíåíöèàëüíîå ÷èñëî ðåøåíèé), à òàêæå äàåò âîçìîæíîñòü îõàðàêòå-
ðèçîâàòü ñëîæíîñòü ïîèñêà ïðè ðåøåíèè çàäà÷ èäåíòèôèêàöèè â òåðìèíàõ ìîùíîñòè
ìíîæåñòâ ðåøåíèé ñîîòâåòñòâóþùèõ óðàâíåíèé. Ïî-âèäèìîìó, èìåííî ýòî îáñòîÿ-
òåëüñòâî è ïîñëóæèëî îñíîâíûì ñòèìóëîì äëÿ èññëåäîâàíèÿ êëàññîâ àâòîìàòîâ íàä
êîíå÷íûìè êîììóòàòèâíî-àññîöèàòèâíûìè êîëüöàìè ñ åäèíèöåé.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4 17
� Â.Â. Ñêîáåëåâ, Â.Ã. Ñêîáåëåâ, 2010
Ñèñòåìàòè÷åñêèé àíàëèç àâòîíîìíûõ ëèíåéíûõ è ïîëèëèíåéíûõ àâòîìàòîâ
íàä êîíå÷íûìè êîëüöàìè ïðåäñòàâëåí â [10, 11].  ðàáîòàõ [12–15] ñ ïîçèöèè êðèï-
òîãðàôèè èññëåäîâàíû ìíîæåñòâà àâòîìàòîâ Ìèëè è Ìóðà íàä êîëüöîì
�m m� �( , , )Z � (ãäå m�N, a b a b m� � � ( )mod è a b a b m� � � ( )mod ) â ñëó÷àå,
êîãäà m pk� (ãäå p — ïðîñòîå ÷èñëî, k �N).  [12] èññëåäîâàíû ëèíåéíûå àâòî-
ìàòû, à â [13] — ëèíåéíûå îäíîìåðíûå àâòîìàòû ñ ëàãîì l. Â [14] ðàññìîòðåíû íåëè-
íåéíûå àâòîìàòû, ó êîòîðûõ «íåëèíåéíîñòü» õàðàêòåðèçóåòñÿ òåì, ÷òî èçìåíåíèå çíà-
÷åíèé ïåðåìåííûõ ñîñòîÿíèé è âûõîäíûõ ïåðåìåííûõ ïðåäñòàâëåíî àëãåáðàè÷åñêîé
ñóììîé êâàäðàòè÷íîé è ëèíåéíîé ôîðì îò ïåðåìåííûõ ñîñòîÿíèé ñ ëèíåéíîé ôîðìîé
îò âõîäíûõ ïåðåìåííûõ.  [15] èññëåäîâàíû íåëèíåéíûå îáðàòèìûå ñèììåòðè÷íûå
àâòîìàòû, ïîñòðîåííûå íà îñíîâå Guckenheimer and Holms cycle è free-running
system — äâóõ ìîäåëüíûõ õàîòè÷åñêèõ äèíàìè÷åñêèõ ñèììåòðè÷íûõ ñèñòåì.
Íåñìîòðÿ íà òî ÷òî â [12–15] âûáðàíî êîëüöî �
pk , ïîëó÷åííûå ðåçóëüòàòû ìîãóò
áûòü åñòåñòâåííûì îáðàçîì îáîáùåíû íà ëþáîå êîíå÷íîå êîììóòàòèâíî-àññîöèàòèâ-
íîå êîëüöî ñ åäèíèöåé � � � �( , , )K (â äàëüíåéøåì, äëÿ êðàòêîñòè, — êîëüöî � ). Íà-
ñòîÿùàÿ ðàáîòà ïîñâÿùåíà àíàëèçó ìîäåëåé è ìåòîäîâ, ëåæàùèõ â îñíîâå ïîñòðîåíèÿ
òàêèõ îáîáùåíèé. Â ðàçä. 1 ñ ïîçèöèè òåîðèè àëãîðèòìîâ îõàðàêòåðèçîâàíà îáùàÿ
ñõåìà, ïðåäíàçíà÷åííàÿ äëÿ âû÷èñëåíèÿ îöåíîê, îñíîâàííûõ íà ìîùíîñòè ïîäìíî-
æåñòâ çàäàííîãî ìíîæåñòâà àâòîìàòîâ íàä êîëüöîì � . Â ðàçä. 2 ïðåäëîæåí ïîäõîä
ê ðåøåíèþ íàä êîëüöîì � ñèñòåì ïîëèíîìèàëüíûõ óðàâíåíèé ñ ïàðàìåòðàìè, îñíî-
âàííûé íà èñïîëüçîâàíèè êëàññîâ àññîöèèðîâàííûõ ýëåìåíòîâ êîëüöà. Íåêîòîðûå
îñîáåííîñòè ïðèìåíåíèÿ ýòîé ñõåìû ïðîèëëþñòðèðîâàíû íà ïðèìåðå ðåøåíèÿ êîí-
êðåòíîé ñèñòåìû. Â ðàçä. 3 óñòàíîâëåí ðÿä îáùèõ õàðàêòåðèñòèê àâòîìàòîâ íàä êîëü-
öîì � . Çàêëþ÷åíèå ñîäåðæèò ðÿä âûâîäîâ.
1. ÑÕÅÌÀ ÀÍÀËÈÇÀ ÊÎÍÅ×ÍÎ-ÀÂÒÎÌÀÒÍÛÕ
ÕÀÐÀÊÒÅÐÈÑÒÈÊ ÌÎÄÅËÅÉ
Ïóñòü ìíîæåñòâî A àâòîìàòîâ íàä êîëüöîì � îïðåäåëÿåòñÿ êîíå÷íûì ìíîæåñ-
òâîì S ïàðàìåòðîâ, ïðè÷åì âûáîð çíà÷åíèÿ êàæäîãî ïàðàìåòðà îñóùåñòâëÿåòñÿ
íåçàâèñèìî èç êîíå÷íîãî ìíîæåñòâà � âîçìîæíûõ çíà÷åíèé. Òîãäà
| | | || |A � � S . (1)
Àíàëèç ïðèíàäëåæíîñòè àâòîìàòîâ íåòðèâèàëüíûì ïîäìíîæåñòâàì ìíîæåñ-
òâà A, õàðàêòåðèçóåìûì â òåðìèíàõ òåîðèè àâòîìàòîâ («áûòü ïåðåñòàíîâî÷íûì àâ-
òîìàòîì», «áûòü ïðèâåäåííûì àâòîìàòîì», «áûòü ñèëüíîñâÿçíûì àâòîìàòîì»,
«èìåòü äàííóþ ñòåïåíü ðàçëè÷èìîñòè ñîñòîÿíèé», «èìåòü äàííûé äèàìåòð ãðàôà
ïåðåõîäîâ», «áûòü îáðàòèìûì àâòîìàòîì» è ò.ä.), óêëàäûâàåòñÿ â ðàìêè ñëåäóþ-
ùåé ñõåìû.
Ñõåìà 1. Ôèêñèðóþòñÿ íåïóñòûå ïîïàðíî íåïåðåñåêàþùèåñÿ ïîäìíîæåñòâà
� i ( , , )i l�1 � ìíîæåñòâà �, à òàêæå íåïóñòûå ïîïàðíî íåïåðåñåêàþùèåñÿ ïîäìíî-
æåñòâà S i ( , , )i l�1 � ìíîæåñòâà S . Äàëåå äîêàçûâàåòñÿ îäíî èç ñëåäóþùèõ òðåõ
óòâåðæäåíèé.
Óòâåðæäåíèå 1 (äîñòàòî÷íîå óñëîâèå). Åñëè ïàðàìåòðû, ïðèíàäëåæàùèå ïîä-
ìíîæåñòâó S i ( , , )i l�1 � , ïðèíèìàþò çíà÷åíèÿ èç ìíîæåñòâà � i , òî àâòîìàò M �A
ïðèíàäëåæèò ïîäìíîæåñòâó A1 ìíîæåñòâà A.
Óòâåðæäåíèå 2 (íåîáõîäèìîå óñëîâèå). Åñëè àâòîìàò M �A ïðèíàäëåæèò
ïîäìíîæåñòâó A1 ìíîæåñòâà A, òî ïàðàìåòðû, ïðèíàäëåæàùèå ïîäìíîæåñòâó S i
( , , )i l�1 � , ïðèíèìàþò çíà÷åíèÿ èç ìíîæåñòâà � i .
Óòâåðæäåíèå 3 (êðèòåðèé). Àâòîìàò M �A ïðèíàäëåæèò ïîäìíîæåñòâó A1
ìíîæåñòâà A òîãäà è òîëüêî òîãäà, êîãäà ïàðàìåòðû, ïðèíàäëåæàùèå ïîäìíîæåñ-
òâó S i ( , , )i l�1 � , ïðèíèìàþò çíà÷åíèÿ èç ìíîæåñòâà � i .
Èç ñõåìû 1 âûòåêàåò ñëåäóþùàÿ õàðàêòåðèñòèêà ìíîæåñòâà A1.
18 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4
Òåîðåìà 1. Åñëè èñòèííî óòâåðæäåíèå i (i �1 2 3, , ), òî èñòèííà îöåíêà
| | | |
| |
| |
| |
A A1
1
�
��
�
��
�
�
�
�
i
S
i
l i
, (2)
ãäå
�
�
�
, ,
,
åñëè èñòèííî óòâåðæäåíèå
åñëè èñòèííî óò
1
âåðæäåíèå
åñëè èñòèííî óòâåðæäåíèå
2
3
,
, .�
�
�
�
�
�
(3)
Äîêàçàòåëüñòâî. Èç ôîðìóëèðîâêè óòâåðæäåíèé 1–3, à òàêæå îïðåäåëåíèÿ
ìíîæåñòâà àâòîìàòîâ A âûòåêàåò, ÷òî ïðè ïîñòðîåíèè àâòîìàòà M �A1 îñóùå-
ñòâëÿåòñÿ íåçàâèñèìûé âûáîð èç ìíîæåñòâà � i ( , , )i l�1 � çíà÷åíèé ïàðàìåòðîâ,
ïðèíàäëåæàùèõ ïîäìíîæåñòâó S i , à òàêæå íåçàâèñèìûé âûáîð èç ìíîæåñòâà �
çíà÷åíèé ïàðàìåòðîâ, ïðèíàäëåæàùèõ ïîäìíîæåñòâó S S
i
l
i\ ( )�
�1
. Ïðè ýòîì S i
( , , )i l�1 � — ïîïàðíî íåïåðåñåêàþùèåñÿ ïîäìíîæåñòâà. Ïîýòîìó
| | | | | | | |
| |
| |
| |
| | | |
| |A1
1
1
�
�
��
�
� �� � �
�
�
i
S
i
l S S
S ii
i
i
l
��
�
��
�
�
| |S
i
l i
1
, (4)
ãäå îïðåäåëÿåòñÿ ôîðìóëîé (3). Âîñïîëüçîâàâøèñü â (4) ôîðìóëîé (1), ïîëó-
÷èì (2).
Òåîðåìà äîêàçàíà.
Ñëåäñòâèå 1. Åñëè íà ìíîæåñòâå � çàäàíî ðàâíîìåðíîå ðàñïðåäåëåíèå,
à PA 1
— âåðîÿòíîñòü òîãî, ÷òî ñëó÷àéíî âûáðàííûé àâòîìàò M �A ïðèíàäëåæèò
ìíîæåñòâó A1, òî
PA 1
1
�
��
�
��
�
�
| |
| |
| |
�
�
i
S
i
l i
, (5)
ãäå îïðåäåëÿåòñÿ ôîðìóëîé (3).
Äîêàçàòåëüñòâî. Òàê êàê âûáîð çíà÷åíèÿ êàæäîãî ïàðàìåòðà, ïðèíàäëåæàùå-
ãî ìíîæåñòâó S , îñóùåñòâëÿåòñÿ íåçàâèñèìî èç êîíå÷íîãî ìíîæåñòâà �, íà êîòî-
ðîì çàäàíî ðàâíîìåðíîå ðàñïðåäåëåíèå, òî íà ìíîæåñòâå A òàêæå çàäàíî ðàâíîìåð-
íîå ðàñïðåäåëåíèå. Ñëåäîâàòåëüíî,
P
A
A
A 1
1�
| |
| |
. (6)
Ïîäñòàâèâ (1) è (2) â (6), ïîëó÷èì (5).
Ñëåäñòâèå äîêàçàíî.
Ïîä «âðåìåííîé ñëîæíîñòüþ» áóäåì ïîíèìàòü «âðåìåííóþ ñëîæíîñòü â õóä-
øåì ñëó÷àå», ò.å. íàèáîëüøåå âðåìÿ, íåîáõîäèìîå àëãîðèòìó äëÿ àíàëèçà îáúåêòà,
åñëè îáúåêò ïðèíàäëåæèò çàäàííîìó êîíå÷íîìó ìíîæåñòâó îáúåêòîâ.
Îáîçíà÷èì TS i
( , , )i l�1 � âðåìåííóþ ñëîæíîñòü ïðîâåðêè ïðèíàäëåæíîñòè
ïàðàìåòðà s S� ìíîæåñòâó S i (ò.å. âðåìåííóþ ñëîæíîñòü ïðîâåðêè òîãî, ÷òî çíà÷å-
íèå ïàðàìåòðà s S� ïðèíàäëåæèò ìíîæåñòâó � i ), à TA 1
— âðåìåííóþ ñëîæíîñòü
ïðîâåðêè ïðèíàäëåæíîñòè àâòîìàòà M �A ìíîæåñòâó A1. Èç ôîðìóëèðîâêè
óòâåðæäåíèé 2 è 3 âûòåêàåò
T
S T
S
i S
i
l
i
i
A 1
1
2�
�
�
� | | , ,
| |
åñëè èñòèííî óòâåðæäåíèå
TS
i
l
i
�
�
�
�
�
�
�
�
�
1
3, .åñëè èñòèííî óòâåðæäåíèå
(7)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4 19
Âûäåëèì äâà ñïåöèàëüíûõ ñëó÷àÿ ðàññìîòðåííîé ñõåìû.
Ñëó÷àé 1. Ïóñòü l �1. Òîãäà ôîðìóëû (2), (5) è (7) ïðèíèìàþò ñîîòâåòñòâåííî âèä
| | | |
| |
| |
| |
A A1
1
1
�
��
�
��
�
�
S
, (8)
PA 1
1
1
�
��
�
��
| |
| |
| |
�
�
S
, (9)
T
S T
S T
S
S
A 1
1
1
1
1
2�
�
| | , ,
| | ,
åñëè èñòèííî óòâåðæäåíèå
åñëè èñòèííî óòâåðæäåíèå 3.
�
�
�
��
(10)
Ñëó÷àé 2. Ïóñòü l � 2 è� � �1 2� � . Òîãäà ôîðìóëû (2), (5) è (7) ïðèíèìàþò
ñîîòâåòñòâåííî âèä
| | | |
| |
| |
| |
| |
| | | |
A A1
1 1
1 2
1
�
��
�
�� �
�
��
�
��
�
�
�
�
S S
, (11)
PA 1
1 2
1 11
�
��
�
�� �
�
��
�
��
| |
| |
| |
| |
| | | |
�
�
�
�
S S
, (12)
T
S S T TS S
A 1
1 21 2� �(| | | | )min , ,{ } åñëè èñòèííî óòâåðæäåíèå
{ } åñëè èñòèííî óòâåðæ
2
1 2 1 2
,
(| | | | )min , ,� �S S T TS S äåíèå 3.
�
�
�
��
(13)
Ïîä÷åðêíåì, ÷òî âñå óñòàíîâëåííûå â [12–15] îöåíêè ìîùíîñòåé íåòðèâèàëü-
íûõ ïîäìíîæåñòâ àâòîìàòîâ ïîëó÷åíû â ðåçóëüòàòå äåòàëèçàöèè ôîðìóë (8) è (10)
ïðèìåíèòåëüíî ê ñîîòâåòñòâóþùåìó ïîäìíîæåñòâó àâòîìàòîâ íàä êîëüöîì �
pk .
Ïðîèëëþñòðèðóåì ñõåìó àíàëèçà êîíå÷íî-àâòîìàòíûõ õàðàêòåðèñòèê íà ïðè-
ìåðå îáîáùåíèÿ ðÿäà ðåçóëüòàòîâ, ïîëó÷åííûõ â [12].
Ïðèìåð 1. Ïóñòü m p
i
k
i
h
i�
�
�
1
, ãäå pi ( , , )i h�1 � — ïîïàðíî ðàçëè÷íûå ïðîñòûå
÷èñëà, ki �N ( , , )i h�1 � , à A — ìíîæåñòâî âñåõ ëèíåéíûõ àâòîìàòîâ Ìèëè íàä
êîëüöîì �m , èìåþùèõ âèä
q q x
y q x Z
t t t
t t t
A B
C D t
� �
� � �
� �
� � �
�
�
�
1 1
1 1
� �
� �
,
( ),
ãäå A B C D, , , — ( )n n� -ìàòðèöû íàä êîëüöîì �m , à q x yt t t m
n, , �� — âåê-
òîð-ñòîëáöû, ïðåäñòàâëÿþùèå ñîñòîÿíèå àâòîìàòà, âõîäíîé è âûõîäíîé ñèìâîë
â ìîìåíò t.
 äàííîì ñëó÷àå S A B C D�{ }, , , , à � — ìíîæåñòâî âñåõ ( )n n� -ìàòðèö íàä
êîëüöîì �m . Ñëåäîâàòåëüíî, | |� � mn2
, îòêóäà âûòåêàåò | |A � m n4 2
.
Íåñëîæíî ïîêàçàòü, ÷òî àâòîìàò M �A ÿâëÿåòñÿ îáðàòèìûì àâòîìàòîì òîãäà
è òîëüêî òîãäà, êîãäà D — îáðàòèìàÿ ìàòðèöà íàä êîëüöîì �m . Îáîçíà÷èì �1
ìíîæåñòâî âñåõ îáðàòèìûõ ( )n n� -ìàòðèö íàä êîëüöîì �m . Òàê êàê
| | ( )�1
11
2
1� � �
��
��m pn
i
j
j
n
i
h
(ñì., íàïðèìåð, [16]), èìååì
| |
| |
( )
�
�
1
11
1� � �
��
�� p
i
j
j
n
i
h
.
Ïóñòü A1 — ìíîæåñòâî âñåõ îáðàòèìûõ ïåðåñòàíîâî÷íûõ àâòîìàòîâ M �A.
20 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4
Íåñëîæíî ïîêàçàòü, ÷òî àâòîìàò M �A ÿâëÿåòñÿ ïåðåñòàíîâî÷íûì àâòîìàòîì òîã-
äà è òîëüêî òîãäà, êîãäà A — îáðàòèìàÿ ìàòðèöà íàä êîëüöîì �m . Ñëåäîâàòåëüíî,
M �A1 òîãäà è òîëüêî òîãäà, êîãäà A D, — îáðàòèìûå ìàòðèöû íàä êîëüöîì �m .
Èìååò ìåñòî ñëó÷àé 1, ãäå S A D1 �{ }, . Èç (8)–(10) (ñ ó÷åòîì òîãî, ÷òî ñïðàâåäëèâî
óòâåðæäåíèå 3) âûòåêàåò
| |A1
4
11
22
1� � �
��
��m pn
i
j
j
n
i
h
( ( )) , PA 1
1
11
2� � �
��
��( ( ))p
i
j
j
n
i
h
,
T TSA 1 1
2� ,
ãäå TS 1
— âðåìÿ, íåîáõîäèìîå äëÿ ïðîâåðêè ïðèíàäëåæíîñòè ( )n n� -ìàòðèöû
ìíîæåñòâó îáðàòèìûõ ìàòðèö íàä êîëüöîì �m , ò.å. âðåìÿ, íåîáõîäèìîå äëÿ âû-
÷èñëåíèÿ îïðåäåëèòåëÿ ìàòðèöû è ïðîâåðêè åãî âçàèìíîé ïðîñòîòû ñ êàæäûì
èç ïðîñòûõ ÷èñåë pi ( , , )i h�1 � .
Ïóñòü A1 — ìíîæåñòâî âñåõ îáðàòèìûõ àâòîìàòîâ M �A, èìåþùèõ ñîñòîÿ-
íèÿ-áëèçíåöû. Íåñëîæíî ïîêàçàòü, ÷òî åñëè àâòîìàò M �A èìååò ñîñòîÿíèÿ-áëèç-
íåöû, òî A C, — íåîáðàòèìûå ìàòðèöû íàä êîëüöîì �m . Ñëåäîâàòåëüíî, åñëè àâòî-
ìàò M �A ïðèíàäëåæèò ïîäìíîæåñòâó A1, òî D — îáðàòèìàÿ ìàòðèöà, à A C, —
íåîáðàòèìûå ìàòðèöû íàä êîëüöîì �m . Îáîçíà÷èì � 2 ìíîæåñòâî âñåõ íåîáðàòè-
ìûõ ( )n n� -ìàòðèö íàä êîëüöîì �m . Òàê êàê � � �1 2� � , èìååò ìåñòî ñëó÷àé 2,
ãäå S D1 �{ } è S A C2 �{ }, . Èç (11)–(13) (ñ ó÷åòîì òîãî, ÷òî ñïðàâåäëèâî óòâåðæäå-
íèå 2) âûòåêàåò
| | 1A1
4
11 11
2
1 1� � � �
�
��
��
�
��
�� ��m p pn
i
j
j
n
i
h
i
j
j
n
i
h
( ) ( )
�
�
�
�
2
,
PA 1
1 1
11 11
� � � �
�
�
�
�
�
�
�
��
�
��
�� ��( ) ( )p p
i
j
j
n
i
h
i
j
j
n
i
h
1
2
,
T T TS SA 1 1 2
3� min { , },
ãäå TS 2
— âðåìÿ, íåîáõîäèìîå äëÿ ïðîâåðêè ïðèíàäëåæíîñòè ( )n n� -ìàòðèöû
ìíîæåñòâó íåîáðàòèìûõ ìàòðèö íàä êîëüöîì �m , ò.å. âðåìÿ, íåîáõîäèìîå äëÿ
âû÷èñëåíèÿ îïðåäåëèòåëÿ ìàòðèöû è ïðîâåðêè åãî äåëèìîñòè õîòÿ áû íà îäíî
ïðîñòîå ÷èñëî pi ( , , )i h�1 � . Ïîñêîëüêó T TS S1 2
� , èìååì T TSA 1 1
3� .
2. ÐÅØÅÍÈÅ ÑÈÑÒÅÌ ÏÎËÈÍÎÌÈÀËÜÍÛÕ ÓÐÀÂÍÅÍÈÉ ÍÀÄ ÊÎÍÅ×ÍÛÌ ÊÎËÜÖÎÌ
Äëÿ àâòîìàòîâ íàä êîëüöîì � � � �( , , )K çàäà÷è ïîñòðîåíèÿ êëàññîâ ýêâèâàëåíò-
íûõ ñîñòîÿíèé àâòîìàòà, èäåíòèôèêàöèè íà÷àëüíîãî ñîñòîÿíèÿ àâòîìàòà, ïàðà-
ìåòðè÷åñêîé èäåíòèôèêàöèè, à òàêæå ïîñòðîåíèÿ ìíîæåñòâ íåïîäâèæíûõ òî÷åê
àâòîìàòíûõ îòîáðàæåíèé ñâîäÿòñÿ ê ðåøåíèþ ñîîòâåòñòâóþùèõ ñèñòåì (ëèíåéíûõ
èëè íåëèíåéíûõ) óðàâíåíèé (êàê ïðàâèëî, ñ ïàðàìåòðàìè) íàä êîëüöîì � (÷òî
ïðîèëëþñòðèðîâàíî â [12–15] ïðè èññëåäîâàíèè àâòîìàòîâ íàä êîëüöîì �
pk ).
Ðåøåíèå ëèíåéíîé ñèñòåìû óðàâíåíèé íàä ïîëåì GF pk( ) íå âûçûâàåò îñîáûõ çà-
òðóäíåíèé. Îäíàêî ñèòóàöèÿ èçìåíÿåòñÿ ïðè ðåøåíèè ñèñòåì íåëèíåéíûõ óðàâíåíèé
íàä ýòèì ïîëåì (èçâåñòíî, ÷òî äàæå ïðè p � 2 çàäà÷à ðåøåíèÿ ñèñòåì êâàäðàòíûõ óðàâ-
íåíèé îò ìíîãèõ ïåðåìåííûõ — NP-ïîëíàÿ). Çíà÷èòåëüíî áîëåå ñëîæíîé ÿâëÿåòñÿ ðàç-
ðàáîòêà ìåòîäîâ ðåøåíèÿ ñèñòåì íåëèíåéíûõ óðàâíåíèé íàä êîëüöîì � � � �( , , )K (÷òî
îáóñëîâëåíî, ïðåæäå âñåãî, íàëè÷èåì â êîëüöå äåëèòåëåé íóëÿ).
 ðÿäå ñëó÷àåâ ìîæíî óïðîñòèòü ïîèñê ðåøåíèÿ ïîëèíîìèàëüíîé ñèñòåìû
óðàâíåíèé
f u u a an h1 1 1 0( , , , , , ) ,� � �
�������������������������������������
�
�
�
�
�
� f u u a al n h( , , , , , )1 1 0� �
(14)
íàä êîëüöîì � � � �( , , )K , ãäå u un1 , ,� — ïåðåìåííûå, à a ah1 , ,� — ïàðàìåòðû.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4 21
Îáîçíà÷èì B ìíîæåñòâî êëàññîâ àññîöèèðîâàííûõ ýëåìåíòîâ êîëüöà � ,
� � �x x K( ) — êëàññ ýëåìåíòîâ, àññîöèèðîâàííûõ ñ ýëåìåíòîì x, à G � �( , )G
( \ { })G K� 0 — ìóëüòèïëèêàòèâíóþ ãðóïïó êîëüöà � . Òîãäà B B� � � � � � �{ }0 1, ,
ãäå � ��0 0{ }, � ��1 G, à B� � � � �{ { } }x x K G| ( \ ) \0 — ìíîæåñòâî êëàññîâ, àññîöè-
èðîâàííûõ ñ íåîáðàòèìûìè ýëåìåíòàìè êîëüöà � . Äàëåå áóäåì ñ÷èòàòü, ÷òî
| |G �1 è | |� �B 1.
Îïðåäåëèì íà ìíîæåñòâå B îïåðàöèþ óìíîæåíèÿ:
� � � � ��� � �x y x y ( , )x y K� . (15)
Òàêîå îïðåäåëåíèå êîððåêòíî, ïîñêîëüêó � �� �x G x ( )x K� . Ñëåäîâàòåëüíî,
( , )B � — ïîëóãðóïïà. Ïîëîæèì
B0 � � �{ íåïðèâîäèìûé ýëåìåíò êîëüöà }x x| — � .
 äàëüíåéøåì ïðåäïîëàãàåòñÿ, ÷òî êàæäûé ýëåìåíò ìíîæåñòâà B� åäèíñòâåí-
íûì îáðàçîì (ñ òî÷íîñòüþ äî àññîöèèðîâàííîãî ðàçëîæåíèÿ) ìîæåò áûòü ïðåä-
ñòàâëåí â âèäå ïðîèçâåäåíèÿ ýëåìåíòîâ ìíîæåñòâà B0 . Îòìåòèì, ÷òî ýòî òðåáîâà-
íèå áîëåå ñëàáîå, ÷åì òðåáîâàíèå «B — ãàóññîâà ïîëóãðóïïà», òàê êàê íå òðåáóåòñÿ
âûïîëíåíèÿ «çàêîíà ñîêðàùåíèÿ», êîòîðûé íå èìååò ìåñòà äàæå â ñëó÷àå
� ��
pk ( )k � 3 .
Îïðåäåëèì ñóììó ýëåìåíòîâ ìíîæåñòâà B:
� � � � �� � �� � �� � � �� � � �� �x y a x b y a b z{ z }B | ( )( )( ) (x y K, � ). (16)
Ðàâåíñòâî (16) îïðåäåëÿåò íà ìíîæåñòâå B òåðíàðíîå îòíîøåíèå, à íå áèíàð-
íóþ îïåðàöèþ (â àëãåáðàè÷åñêîì ñìûñëå ýòîãî ñëîâà), ÷òî, â ÷àñòíîñòè, èñòèííî,
äàæå åñëè � ��
pk .
Òàêèì îáðàçîì, îñóùåñòâëåí ïåðåõîä îò êîëüöà � � � �( , , )K ê àëãåáðàè÷åñêîé
ñèñòåìå � � � �( , , )B , ÷òî äàåò âîçìîæíîñòü ïðåäëîæèòü ñëåäóþùóþ ñõåìó ðåøå-
íèÿ ñèñòåìû óðàâíåíèé (14).
Ñõåìà 2. Çàìåíèâ â (14) ýëåìåíòû êîëüöà � ýëåìåíòàìè ìíîæåñòâà B, à îïåðà-
öèè â êîëüöå � — äåéñòâèÿìè â àëãåáðàè÷åñêîé ñèñòåìå �, îïðåäåëÿåìûìè ðàâå-
íñòâàìè (15) è (16), ïîëó÷èì ñèñòåìó óðàâíåíèé
f u u a an h1 1 1 0( , , , , , ) ,� � � � � � � � �� �
������������������
� �
������������������������������������
� � � �f u ul n( , ,1 � , , , )� � � � �� �
�
�
�
�
� a ah1 0�
(17)
íàä àëãåáðàè÷åñêîé ñèñòåìîé �. Ïðåäñòàâèì ýëåìåíòû � � � ��a ah1 , ,� B
â âèäå ïðîèçâåäåíèÿ ýëåìåíòîâ, ïðèíàäëåæàùèõ ìíîæåñòâó B0 . Íàéäåì ìíîæåñ-
òâî S ðåøåíèé ñèñòåìû óðàâíåíèé (17) (ãäå äëÿ êàæäîãî ðåøåíèÿ ( ,� �u1 �
� , )� � �un S êàæäûé ýëåìåíò � ��ui B ïðåäñòàâëåí â âèäå ïðîèçâåäåíèÿ ýëå-
ìåíòîâ, ïðèíàäëåæàùèõ ìíîæåñòâó B0 ). Èñõîäÿ èç ìíîæåñòâà S, ïîñòðîèì ìíî-
æåñòâî S ðåøåíèé ñèñòåìû óðàâíåíèé (14). Äëÿ ýòîãî äîñòàòî÷íî äëÿ êàæäîãî
çíà÷åíèÿ u S� � � � � �( , , )u un1 � ïîñòðîèòü ìíîæåñòâî
S u u u u i nn i iu � �� � �{ }( , , )| ( , , )( ) ( ) ( )
1
0 0 0 1� �
è âûäåëèòü â íåì ýëåìåíòû ìíîæåñòâà S .
Î÷åâèäíî, ÷òî ñëîæíîñòü ñõåìû 2 îïðåäåëÿåòñÿ èìåííî ñëîæíîñòüþ ïîèñêà,
îñóùåñòâëÿåìîãî ïðè ïîñòðîåíèè ìíîæåñòâà S èç ìíîæåñòâà S. Îòñþäà âûòåêàåò,
÷òî ñõåìà 2 áóäåò ýôôåêòèâíîé ïðè ïîñòðîåíèè ðåøåíèé ñèñòåìû óðàâíåíèé (14),
åñëè óêàçàííûé ïîèñê îòñóòñòâóåò ëèáî åãî ñëîæíîñòü íåâåëèêà.
Ñëåäóþùèé ïðèìåð ïîêàçûâàåò, ÷òî ñõåìà 2 äàåò âîçìîæíîñòü ýôôåêòèâíî
ñòðîèòü ìíîæåñòâî ðåøåíèé ïî êðàéíåé ìåðå äëÿ íåêîòîðûõ òèïîâ ïîëèíîìèàëü-
íûõ ñèñòåì óðàâíåíèé íàä êîíå÷íûìè êîëüöàìè.
22 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4
Ïðèìåð 2. Íàéäåì ìíîæåñòâî S ðåøåíèé ( , , )u u u1 2 3 ñèñòåìû óðàâíåíèé
a u u a u
a u
1 1 2 2 3
2 1
0
0
� � �
�
� �
�
�
�
�
,
(18)
ñ ïàðàìåòðàìè a a a
pk1 2 3, , �Z íàä êîëüöîì �
pk .
Çàìå÷àíèå 1. Íåñëîæíî ïîêàçàòü, ÷òî íåîáõîäèìîñòü ðåøåíèÿ ñèñòåìû óðàâ-
íåíèé (18) âîçíèêàåò ïðè èññëåäîâàíèè ñòðóêòóðû êëàññîâ ýêâèâàëåíòíûõ ñîñòîÿ-
íèé òàêîãî îáðàòèìîãî àâòîìàòà Ìóðà
q a b q c q d x
y e q t
t t t t
t t
� � �
� � �
� � � �
� �
�
�
�
��
2 1
2
1
1 2
� � �
�
,
( )Z
íàä êîëüöîì �
pk , ÷òî ïàðàìåòðû e è f — îáðàòèìûå ýëåìåíòû êîëüöà �
pk .
Îòìåòèì, ÷òî óðàâíåíèå q a b q c qt t t� �
� � �2 1
2
� � ïðåäñòàâëÿåò ñîáîé àíàëîã
íàä êîëüöîì �
pk
ðÿäà ìîäåëüíûõ õàîòè÷åñêèõ îòîáðàæåíèé, â òîì ÷èñëå îòî-
áðàæåíèÿ Ýíî [1].
Êëàññàìè àññîöèèðîâàííûõ ýëåìåíòîâ êîëüöà �
pk ÿâëÿþòñÿ ìíîæåñòâî { }0 ,
ìíîæåñòâî Z
pk
inv âñåõ îáðàòèìûõ ýëåìåíòîâ, à òàêæå ìíîæåñòâà { }inva p ar
pk r
� | � �Z
( , , )r k� �1 1� .
 ñîîòâåòñòâèè ñ [17] îïðåäåëèì p-òèï t p z( ) ýëåìåíòà z
pk�Z ðàâåíñòâîì
t
Z
p
p
rz r r k z p z
k
( )
, ,
( ), )�
�
� � � !
0
1 1
åñëè z
åñëè 0(mod è
inv
0(mod
åñëè
p
k z
r�
�
�
�
�
�
�
�
�
1
0
),
, .
Èç äàííîãî îïðåäåëåíèÿ ñëåäóþò óòâåðæäåíèÿ:
1) t t tp p pu v k u v( ) min , ( ) ( )� � �{ } ( , )u v
pk�Z ;
2) t t tp p pu v u v( ) min ( ), ( )� � { } ( , )u v
pk�Z ;
3) t p u v( )� � 0 ( , )u v
pk�Z , åñëè min ( ), ( ){ }t tp pu v � 0 , à 0 � max{t p u( ),
t p v k( )}� ;
4) t tp pu v( ) ( )� ( , )u v
pk�Z òîãäà è òîëüêî òîãäà, êîãäà ýëåìåíòû u è v ïðèíàä-
ëåæàò îäíîìó è òîìó æå êëàññó àññîöèèðîâàííûõ ýëåìåíòîâ êîëüöà �
pk .
Çàìå÷àíèå 2. Èç ïîñëåäíåãî ñâîéñòâà âûòåêàåò, ÷òî ïîíÿòèå p-òèï ýëåìåíòà
êîëüöà �
pk îïðåäåëÿåò áèåêöèþ êëàññîâ àññîöèèðîâàííûõ ýëåìåíòîâ êîëüöà
�
pk íà ìíîæåñòâî Zk�1. Ïîýòîìó äëÿ òîãî ÷òîáû çàäàòü êëàññ àññîöèèðîâàííûõ
ýëåìåíòîâ êîëüöà �
pk , äîñòàòî÷íî çàôèêñèðîâàòü p-òèï ýëåìåíòà, ïðèíàäëåæàùå-
ãî ýòîìó êëàññó. Òàêîé ïîäõîä äàåò âîçìîæíîñòü âûäåëÿòü ýëåìåíòû ìíîæåñòâà S
íåïîñðåäñòâåííî â ïðîöåññå ïîñòðîåíèÿ ìíîæåñòâà S è òåì ñàìûì èçáåæàòü ïîèñêà
èëè ñóùåñòâåííî åãî ñîêðàòèòü ïðè èñïîëüçîâàíèè ñõåìû 2.
Äëÿ ïîñòðîåíèÿ ìíîæåñòâà S ðàññìîòðèì ñëåäóþùèå ñëó÷àè.
Ñëó÷àé 3. Ïóñòü t p a k( )1 � , ò.å. a1 0� . Ñèñòåìà óðàâíåíèé (18) ïðèíèìàåò âèä
0 0
0
1 2 2 3
2 1
� � �
�
u u a u
a u
� �
�
�
�
�
,
,
îòêóäà âûòåêàåò
S
z z a
z z z k
p p
p
k
k
�
� �
� �
{( , , )| , ( ) ,
( , , ) |
0 0 02
1 2
3
Z t
Z t
} åñëè
{ p p i p
p
a z k i a k
k
( ) ( ) ( , ) , ( ) ,
,
2 2
3
1 2 1 1� � � � � �t t
Z t
} åñëè
åñëè p a k( ) .2 �
�
�
�
��
�
�
�
�
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4 23
Ñëó÷àé 4. Ïóñòü t p a k( )1 " è t p a( )2 0� . Òîãäà
a u u a u
a u
a u u a u
u
1 1 2 2 3
2 1
1 1 2 2 3
1
0
0
0
0
� � �
�
� � �� �
�
�
�
�
#
� �
�
�
�
�
#
� �
�
�
�
�
0 0
0
2 2 3
1
� �u a u
u
,
,
îòêóäà ñëåäóåò S z z
pk� �{ }( , , ) |0 0 Z .
Ñëó÷àé 5. Ïóñòü t p a k( )1 " è t p a k( )2 � (ò.å. a2 0� ). Ñèñòåìà óðàâíåíèé (18)
ïðèíèìàåò âèä
a u u u
u
1 1 2 3
1
0 0
0 0
� � �
�
� �
�
�
�
�
,
,
îòêóäà âûòåêàåò S u u u k a u u k
p
p p pk
� � � � � �{ }( , , ) | ( ) ( ) ( )1 2 3
3
1 1 2Z t t t .
Ñëó÷àé 6. Ïóñòü t p a k( )1 " è t p a k( ) , ,2 1 1� �{ }� . Ïðåäñòàâèì ìíîæåñòâî S
â âèäå S S S� �1 2 , ãäå
S u u u S u kp1 1 2 3 1� � �{ }( , , ) | ( )t ,
S u u u S k a u kp p2 1 2 3 2 1 1� � � � � �{ }( , , ) | ( ) ( )t t .
Íàéäåì ìíîæåñòâî S1. Òàê êàê t p u k( )1 � (ò.å. u1 0� ), ñèñòåìà óðàâíåíèé (18)
ïðèíèìàåò âèä
0 0
0
2 2 3
1
� �u a u
u
� �
�
�
�
�
,
,
îòêóäà âûòåêàåò S z z k a z k
p
p pk1 1 2
3
2 20� � � � �{ }( , , ) | ( ) ( )Z t t .
Íàéäåì ìíîæåñòâî S 2 . Ïðåäñòàâèì ìíîæåñòâî S 2 â âèäå S S S2 2 2� � � �� , ãäå
� � � � � � � �S u u u S k a k a u kp p p2 1 2 3 1 2 1{ max{ }( , , ) | ( ), ( ) ( )t t t 1},
�� � � � � � � �S u u u S k a u k a kp p p2 1 2 3 2 1 1{ max{( , , ) | ( ) ( ) ( ),t t t t p a( )2 }}. (19)
Èç (18) ñëåäóåò
� � � � � �S u u u k a k a
p
p pk2 1 2 3
3
1 2{ max{ }( , , ) | ( ), ( )Z t t
� � � � �t t tp p pu k u k a( ) , ( ) ( )1 3 21 },
à èç (18) è (19) âûòåêàåò
�� �
$ � �
� �S
a a
u u u k a
p p
p
pk2
2 1
1 2 3
3
, ( ) ( ),
( , , ) | (
åñëè 1
{
t t
Z t 2 1 1
1 1 2 2 3 10
) ( ) ( ),
}, ( )
� � �
� � �
t t
t t
p p
p p
u k a
a u u a u a� � � åñëè ( ) .a k2 1� �
�
�
�
�
�
�
�
Ïðåäñòàâèì ìíîæåñòâî ��S 2 â ÿâíîì âèäå â ñëó÷àå, êîãäà t tp pa a( ) ( )1 2� �
� �k 1. Ïîëîæèâ a p p a
1
1� � �
t ( )
( )
( )
�� �Z t
p
k p a1
inv , a p p a
2
2� � �
t ( )
( )
( )
�� �Z t
p
k p a2
inv è
u p p u
1 1
1� � �
t ( )
( )
( )
�1 1
� �Z t
p
k p u
inv , ïîëó÷èì
�� � ��
� �
�
� �
S S p
l k a
k a
l
p
p
p
k l
2 2 1
1 2
1
1 1
1� � �
t
t
Z( )
( )
( )
�
� ,
ãäå
�� � �S p p u u
l l
2 1 1 2 3
1 1( ) ( , , )� �� �{
� � �
�
Z
t t
p
a l a
k
p pp u p u3
2 3
1 1 2 0|
( ) ( )
� � �� � � � �1 }. (20)
24 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4
Íàéäåì ìíîæåñòâî ��S p
l
2 1
1( )� � . Âîçìîæíû ñëåäóþùèå äâà ñëó÷àÿ.
Ñëó÷àé 6.1. Ïóñòü k a l a ap p p� � � �t t t( ) ( ) ( )2 1 2 1 (÷òî âîçìîæíî òîãäà è
òîëüêî òîãäà, êîãäà t tp pa k a( ) , ( ( ))2 10 5� � ). Èç (20) âûòåêàåò
�� � � � �
S p p p
l l a a lp p
2 1 1 1
11 1 2 1( ) ( , ( )
( ) ( )
� � � � �� � � � �{ O
t t 1
3 3 3� u u u
pk, ) | � �Z }
�
� � �
�
� �
� � � �
l k a l
k
l l
p
p
k l
p p
2 1 1 2 2
1 2
1
1 2
t Z( )
( , (
�
� � �
inv
{ O � ��1
1)�
� � �� p u u up p
k
a a l
p
t t
Z
( ) ( )
, ) |2 1 1
3 3 3
� �
� },
ãäå O — îïåðàöèÿ, îáðàòíàÿ îïåðàöèè �.
Ñëó÷àé 6.2. Ïóñòü l a a k ap p p1 2 1 2� � �max{ }t t t( ) ( ), ( ) . Èç (20) ñëåäóåò
�� � � � �
S p p u p
l l a l ap p
2 1 1 2 1
11 1 1 1( ) ( , ,
( ) (
� � � � �� � � � �{ O
t t 2
2 2
)
) |� u u
pk� �Z }
�
� �
�
� �
� � � � �
l k a
k
l l
p
p
k l
p u p
3 2 3 3
1 3
1
1 2 3
t Z( )
( , ,
�
� � �
inv
{ O � �1
1
� �
�
� �p u up p
k
a l a
p
t t
Z
( ) ( )
) |1 1 2
2 2
� �
� }.
3. ÕÀÐÀÊÒÅÐÈÑÒÈÊÈ ÀÂÒÎÌÀÒΠÍÀÄ ÊÎÍÅ×ÍÛÌ ÊÎËÜÖÎÌ
Çàôèêñèðóåì â êîëüöå � � � �( , , )K ñåìåéñòâî òàêèõ îòîáðàæåíèé f K Ki
n: %
( , , )i n�1 � , ÷òî | |Val fi �1 äëÿ âñåõ i n�1, ,� . Îáîçíà÷èì ~i ( , , )i n�1 � ÿäåðíóþ
ýêâèâàëåíòíîñòü îòîáðàæåíèÿ fi (ò.å. a ~ bi ( , )a b�K n òîãäà è òîëüêî òîãäà,
êîãäà f fi i( ) ( )a b� ), à � i ( , , )i n�1 � — ðàçáèåíèå K
n
i/ ~ ìíîæåñòâà K n ,
îïðåäåëÿåìîå ÿäåðíîé ýêâèâàëåíòíîñòüþ ~i , è ïîëîæèì � ��
�
� i
i
n
1
. Îïðåäå-
ëèì îòîáðàæåíèå f : K Kn n% ðàâåíñòâîì f a( ) ( , , )� b bn
T
1 � , ãäå b fi i� ( )a
( , , )i n�1 � . Òàê êàê äëÿ ëþáûõ ýëåìåíòîâ a b, �K n ( )a b" ðàâåíñòâî f a f b( ) ( )�
èñòèííî òîãäà è òîëüêî òîãäà, êîãäà a b ( )mod � , òî f — ïåðåñòàíîâêà ýëå-
ìåíòîâ ìíîæåñòâà K n òîãäà è òîëüêî òîãäà, êîãäà � — íóëåâîå ðàçáèåíèå
ìíîæåñòâà K n . Îòìåòèì, ÷òî äëÿ ëþáîãî ýëåìåíòà a�K n ðåøåíèå ñèñòåìû
óðàâíåíèé f u a( ) � ýêâèâàëåíòíî ïîèñêó áëîêà ðàçáèåíèÿ �, îáðàçîì êîòîðîãî
ÿâëÿåòñÿ ýëåìåíò a. Áóäåì ãîâîðèòü, ÷òî îòîáðàæåíèå f ñòàáèëüíî íà (íåïóñòîì)
ïîäìíîæåñòâå S ìíîæåñòâà K n , åñëè f ( )S S& .
Äëÿ ëþáîãî ôèêñèðîâàííîãî ýëåìåíòà
�
�� �� � �
... , n
T nK� îïðåäåëèì
îòîáðàæåíèå g �
�
:K Kn n% ðàâåíñòâîì g u� �
�
� �( ) ( , , )� � �1 1u un n
T ( ( ,u � u1 �
� , ) )u Kn
T n� . Èç îïðåäåëåíèÿ îòîáðàæåíèÿ g �
�
âûòåêàåò, ÷òî: 1) g �
�
— ëèíåéíîå
îòîáðàæåíèå (ò.å. g u v g u g v� � �
� � �
( ) ( ) ( )� � � è g u g u� �
� �
� �( ) ( )� � � äëÿ ëþáûõ
u v, �K n è ��K) ; 2)g 1�
�
�
�( ) � , ãäå 1 � �( , , )1 1�
T nK ; 3) g 0 0�
�
( ) � , ãäå
0 � �( , , )0 0�
T nK ; 4) g �
�
— ïåðåñòàíîâêà ýëåìåíòîâ ìíîæåñòâà K n òîãäà è òîëüêî
òîãäà, êîãäà âñå êîìïîíåíòû âåêòîðà
�
� — îáðàòèìûå ýëåìåíòû êîëüöà � .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4 25
Îáîçíà÷èì An,1 è An,2 ìíîæåñòâî àâòîìàòîâ Ìèëè è Ìóðà íàä êîëüöîì � ,
îïðåäåëåííûõ ñèñòåìàìè óðàâíåíèé
q f q
y g q Z
t t t
t t t
x
x t
� �
� � �
� � �
� � � �
�
�
�
�
1 1
1 1
( ) ,
( ) ( ),
�
�
�
�
�
��
(21)
q f q
y g q Z
t t t
t t
x
t
� �
� � �
� � �
� �
�
�
�
��
1 1
1 1
( ) ,
( ) ( ),
�
�
�
�
(22)
ãäå qt t t
n T nq q K� �( , , )( ) ( )1
� , x Kt � è y t
nK� — ñîîòâåòñòâåííî ñîñòîÿíèå àâ-
òîìàòà, âõîäíîé è âûõîäíîé ñèìâîë â ìîìåíò t, à
� � �
� � �, , \�K n { }0 (ãäå
0 � ( , , )0 0� ) — ïàðàìåòðû. Ïîëîæèì A A An n n� �, ,1 2 .
Óñòàíîâèì îñíîâíûå õàðàêòåðèñòèêè àâòîìàòîâ, ïðèíàäëåæàùèõ ìíîæåñòâó An .
Ïðåäëîæåíèå 1. Åñëè äëÿ àâòîìàòà M n�A õîòÿ áû îäíà êîìïîíåíòà âåêòîðà
�
��K n \ { }0 — îáðàòèìûé ýëåìåíò êîëüöà � , òî ëþáîå ñîñòîÿíèå q�K n àâòîìàòà M
ïîä äåéñòâèåì ðàçëè÷íûõ âõîäíûõ ñèìâîëîâ ïåðåõîäèò â ðàçëè÷íûå ñîñòîÿíèÿ.
Äîêàçàòåëüñòâî. Ïðåäïîëîæèì, ÷òî êîìïîíåíòà � i âåêòîðà
�
��K n \ { }0 — îá-
ðàòèìûé ýëåìåíò êîëüöà � . Òîãäà ñèñòåìà óðàâíåíèé
�
� � �u 0 èìååò åäèíñòâåííîå
ðåøåíèå u � 0. Äëÿ ëþáîãî ñîñòîÿíèÿ q�K n àâòîìàòà M è ëþáûõ âõîäíûõ ñèìâî-
ëîâ x x K, ~� èç ïåðâîãî óðàâíåíèÿ ñèñòåì (21) è (22) ïîëó÷èì
f q f q 0( ) ( ) ~ ( ~) ~ ~� � � � � # � � # � � # �
� � �
� � �x x x x x x x x0 .
Ïðåäëîæåíèå äîêàçàíî.
Ïðåäëîæåíèå 2. Åñëè äëÿ àâòîìàòà M n�A âñå êîìïîíåíòû âåêòîðà
�
��K n \ { }0 — íåîáðàòèìûå ýëåìåíòû êîëüöà � , èìåþùèå îáùèé äåëèòåëü, ÿâëÿþ-
ùèéñÿ äåëèòåëåì íóëÿ, òî ñóùåñòâóåò òàêîå ïîäìíîæåñòâî S K& (| | )S �1 , ÷òî ëþ-
áîå ñîñòîÿíèå q�K n àâòîìàòà M ïîä äåéñòâèåì âõîäíûõ ñèìâîëîâ, ïðèíàäëåæà-
ùèõ ìíîæåñòâó S , ïåðåõîäèò â îäíî è òî æå ñîñòîÿíèå.
Äîêàçàòåëüñòâî. Ïóñòü
�
�� � �� �( , , ) \1 n
T nK { }0 è a K� — îáùèé äåëèòåëü
ýëåìåíòîâ � �1 , ,� n , ÿâëÿþùèéñÿ äåëèòåëåì íóëÿ. Òîãäà ñóùåñòâóåò òàêîé ýëå-
ìåíò � �� � �b B \ { }>0 , ÷òî a b� � ��� �0 . Ïîëîæèì S b�� �. Òàê êàê � �� �b G b è
| |G �1, òî | |S �1. Ëþáîé ýëåìåíò u S� ÿâëÿåòñÿ ðåøåíèåì ñèñòåìû óðàâíåíèé
�
� � �u 0. Ñëåäîâàòåëüíî, äëÿ ëþáîãî ñîñòîÿíèÿ q�K n àâòîìàòà M è ëþáûõ âõîä-
íûõ ñèìâîëîâ x x S, ~�
f q f q 0( ) ( ( ) ~) ( ~)� � � � � � � � �
� � �
� � �x x x x .
Ïðåäëîæåíèå äîêàçàíî.
Ïðåäëîæåíèå 3. Äèàìåòð àâòîìàòíîãî ãðàôà ëþáîãî àâòîìàòà M n�A íå
ìåíüøå, ÷åì n.
Äîêàçàòåëüñòâî. Çà îäèí òàêò èç êàæäîãî ñîñòîÿíèÿ q�K n àâòîìàòà M n�A
äîñòèæèìî íå áîëåå ÷åì | |K ñîñòîÿíèé. Ñëåäîâàòåëüíî, â òå÷åíèå l�N òàêòîâ èç ñî-
ñòîÿíèÿ q äîñòèæèìî íå áîëåå ÷åì 1 1 11 1� � � � � �� �| | | | (| | )(| | )K K K Kl l
� ñîñòîÿ-
íèé. Ìîùíîñòü ìíîæåñòâà ñîñòîÿíèé àâòîìàòà M ðàâíà | |K n . Èç íåðàâåíñòâà
(| | )(| | ) | |K K Kl n� �� � �1 11 1 âûòåêàåò, ÷òî l n� �1 , ò.å. l n� .
Ïðåäëîæåíèå äîêàçàíî.
Ïðåäëîæåíèå 4. Äëÿ àâòîìàòà M n�A áëîêè ðàçáèåíèÿ � ïðåäñòàâëÿþò ñîáîé
ìíîæåñòâà ñîñòîÿíèé àâòîìàòà M, ïåðåõîäÿùèå ïî ëþáîìó âõîäíîìó ñèìâîëó
â îäíî è òî æå ñîñòîÿíèå, à ñîñòîÿíèÿ àâòîìàòà M, ïðèíàäëåæàùèå ðàçíûì áëîêàì
ðàçáèåíèÿ �, ïî ëþáîìó âõîäíîìó ñèìâîëó ïåðåõîäÿò â ðàçëè÷íûå ñîñòîÿíèÿ.
26 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4
Äîêàçàòåëüñòâî. Åñëè q q ~( )mod � ( , ~ )q q�K n , òî f q f q( ) (~)� . Ñëåäîâàòåëüíî,
f q f q( ) (~)� � � � �
� �
� �x x äëÿ ëþáîãî âõîäíîãî ñèìâîëà x K� .
Åñëè q q! ~ ( )mod � ( , ~ )q q�K n , òî f q f q( ) (~)" . Òàêèì îáðàçîì, f q( )� � "
�
� x
" � �f q(~)
�
� x äëÿ ëþáîãî âõîäíîãî ñèìâîëà x K� .
Ïðåäëîæåíèå äîêàçàíî.
Ñëåäóÿ [17], íàçîâåì ñîñòîÿíèÿ q q, ~�K n ( ~)q q" àâòîìàòà M n�A áëèçíåöàìè,
åñëè àâòîìàò M èç ýòèõ ñîñòîÿíèé ïîä äåéñòâèåì ëþáîãî âõîäíîãî ñèìâîëà îñóùå-
ñòâëÿåò ïåðåõîä â îäíî è òî æå ñîñòîÿíèå è ïðè ýòîì ñîâïàäàþò âûõîäíûå ñèìâî-
ëû, âûäàâàåìûå àâòîìàòîì M.
Ïðåäëîæåíèå 5. Â àâòîìàòå M n�A ,2 ñóùåñòâóþò ñîñòîÿíèÿ-áëèçíåöû òîãäà
è òîëüêî òîãäà, êîãäà � — íåíóëåâîå ðàçáèåíèå ìíîæåñòâà K n . Ïðè ýòîì ìíîæåñ-
òâàìè ñîñòîÿíèé-áëèçíåöîâ ÿâëÿþòñÿ âñå íåîäíîýëåìåíòíûå áëîêè ðàçáèåíèÿ �.
Äîêàçàòåëüñòâî. Â ñèëó ïðåäëîæåíèÿ 4, åñëè � — íóëåâîå ðàçáèåíèå ìíîæåñòâà
K n , òî â àâòîìàòå M áëèçíåöîâ íåò (òàê êàê ñîñòîÿíèÿ, ïðèíàäëåæàùèå ðàçíûì áëî-
êàì ðàçáèåíèÿ �, ïî ëþáîìó âõîäíîìó ñèìâîëó ïåðåõîäÿò â ðàçëè÷íûå ñîñòîÿíèÿ).
Ïðåäïîëîæèì, ÷òî � — íåíóëåâîå ðàçáèåíèå ìíîæåñòâà K n è S — ïðîèçâîëü-
íûé áëîê ðàçáèåíèÿ �, ñîäåðæàùèé ïî êðàéíåé ìåðå äâà ýëåìåíòà: q q, ~�K n
( ~)q q" . Â ñèëó ïðåäëîæåíèÿ 4 ñîñòîÿíèÿ q q, ~ ïåðåõîäÿò ïî ëþáîìó âõîäíîìó ñèì-
âîëó â îäíî è òî æå ñîñòîÿíèå. Ïðè ýòîì g f q g f q� �
� �
( ( )) ( (~))� (òàê êàê f q f q( ) (~)� ).
Ïðåäëîæåíèå äîêàçàíî.
Îáîçíà÷èì D
K n ìíîæåñòâî âñåõ òàêèõ a � �( , , )a a Kn
T n
1 � , ÷òî a an1 � �� .
Ïðåäëîæåíèå 6. Åñëè äëÿ àâòîìàòà M n�A ( )n � 2 âñå êîìïîíåíòû âåêòîðà
�
��K n \ { }0 ðàâíû ìåæäó ñîáîé, à îòîáðàæåíèå f ñòàáèëüíî íà ìíîæåñòâå D
K n , òî
àâòîìàò M íå ÿâëÿåòñÿ ñèëüíîñâÿçíûì.
Äîêàçàòåëüñòâî. Ïðåäïîëîæèì, ÷òî îòîáðàæåíèå f ñòàáèëüíî íà ìíîæåñòâå
D
K n . Òîãäà f q D( )�
K n äëÿ âñåõ q D�
K n . Òàê êàê âñå êîìïîíåíòû âåêòîðà
�
��K n \ { }0 ðàâíû ìåæäó ñîáîé, òî
�
� � �u
K nD äëÿ âñåõ u K n� . Ñëåäîâàòåëüíî,
f q D( )� � �
�
� u
K n äëÿ âñåõ q D�
K n è u K n� . Îòñþäà âûòåêàåò, ÷òî ñîáñòâåííîå
ïîäìíîæåñòâî D
K n ìíîæåñòâà ñîñòîÿíèé K n àâòîìàòà M îïðåäåëÿåò ïîäàâòîìàò
àâòîìàòà M.
Ïðåäëîæåíèå äîêàçàíî.
Ñëåäñòâèå 2. Åñëè äëÿ àâòîìàòà M n�A âñå êîìïîíåíòû âåêòîðà
�
��K n \ —{ }0
ðàâíûå ìåæäó ñîáîé îáðàòèìûå ýëåìåíòû êîëüöà � , à îòîáðàæåíèå f ñòàáèëüíî íà
ìíîæåñòâå D
K n , òî ïîäàâòîìàò àâòîìàòà M, îïðåäåëÿåìûé ìíîæåñòâîì ñîñòîÿíèé
D
K n , ÿâëÿåòñÿ ñèëüíîñâÿçíûì ïåðåñòàíîâî÷íûì àâòîìàòîì, äèàìåòð ãðàôà ïåðåõî-
äîâ êîòîðîãî ðàâåí 1.
Äîêàçàòåëüñòâî. Ïðåäïîëîæèì, ÷òî âñå êîìïîíåíòû âåêòîðà
�
��K n \ { }0 —
ðàâíûå ìåæäó ñîáîé îáðàòèìûå ýëåìåíòû êîëüöà � , à îòîáðàæåíèå f ñòàáèëüíî íà
ìíîæåñòâå D
K n . Òîãäà äëÿ ëþáûõ ôèêñèðîâàííûõ ñîñòîÿíèé q q, ~�K n àâòîìàòà M
óðàâíåíèå
�
� � � �x ~ ( )q f q èìååò åäèíñòâåííîå ðåøåíèå x K n� .
Ñëåäñòâèå äîêàçàíî.
Îõàðàêòåðèçóåì ñëîæíîñòü èäåíòèôèêàöèè ïàðàìåòðîâ
� � �
� � �, , \�K n { }0 àâòî-
ìàòà M n�A â ïðåäïîëîæåíèè, ÷òî ýêñïåðèìåíòàòîð ìîæåò óïðàâëÿòü âõîäîì àâ-
òîìàòà M, óñòàíàâëèâàòü àâòîìàò M â ñîñòîÿíèå, óäîâëåòâîðÿþùåå çàäàííûì
óñëîâèÿì, à òàêæå ïîëíîñòüþ íàáëþäàòü âûõîä àâòîìàòà M.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4 27
Òåîðåìà 2. Åñëè ýêñïåðèìåíòàòîð ìîæåò óïðàâëÿòü âõîäîì àâòîìàòà M n�A ,1,
óñòàíàâëèâàòü àâòîìàò M â ñîñòîÿíèå, óäîâëåòâîðÿþùåå çàäàííûì óñëîâèÿì,
à òàêæå ïîëíîñòüþ íàáëþäàòü âûõîä àâòîìàòà M, òî ïàðàìåòðû
� � �
�� � �
�
, , ( ) \g 0�K n { }èäåíòèôèöèðóþòñÿ êðàòíûì ýêñïåðèìåíòîì êðàòíîñòè 3 è âû-
ñîòû 2 .
Äîêàçàòåëüñòâî. Óñòàíîâèì àâòîìàò M â ñîñòîÿíèå q 00 � è ïîäàäèì íà íåãî
âõîäíîé ñèìâîë x1 1� . Èç âòîðîãî óðàâíåíèÿ ñèñòåìû óðàâíåíèé (21) ïîëó÷èì
y g 0 y1 11� � � # ��
� �
�
� �( ) .
Óñòàíîâèì àâòîìàò M â ñîñòîÿíèå q 10 � è ïîäàäèì íà íåãî âõîäíîé ñèìâîë
x1 0� . Èç âòîðîãî óðàâíåíèÿ ñèñòåìû (21) ñëåäóåò
y g 1 y1 10� � � # ��
� �
�
� �( ) .
Óñòàíîâèì àâòîìàò M â òàêîå ñîñòîÿíèå q0 , ÷òî f q 0( )0 � , è ïîäàäèì íà íåãî
âõîäíóþ ïîñëåäîâàòåëüíîñòü x x1 2 10� . Èç ïåðâîãî óðàâíåíèÿ ñèñòåìû (21)
âûòåêàåò
q f q1 0 1� � � �( )
� �
� �,
èç âòîðîãî —
y g q g g y2 1 20� � � � # �� � �
� � �
� � �
� � �( ) ( ) ( ) .
Òåîðåìà äîêàçàíà.
Òåîðåìà 3. Åñëè ýêñïåðèìåíòàòîð ìîæåò óïðàâëÿòü âõîäîì àâòîìàòà
M n�A ,2 , óñòàíàâëèâàòü àâòîìàò M â ñîñòîÿíèå, óäîâëåòâîðÿþùåå çàäàííûì óñëî-
âèÿì, à òàêæå ïîëíîñòüþ íàáëþäàòü âûõîä àâòîìàòà M, òî ïàðàìåòðû
� �
�� �
�
, ( )g �
�K n \ { }0 èäåíòèôèöèðóþòñÿ êðàòíûì ýêñïåðèìåíòîì êðàòíîñòè 2 è âûñîòû 1.
Äîêàçàòåëüñòâî. Óñòàíîâèì àâòîìàò M â òàêîå ñîñòîÿíèå q0 , ÷òî f q 1( )0 � ,
è ïîäàäèì íà íåãî âõîäíîé ñèìâîë x1 0� . Èç ñèñòåìû óðàâíåíèé (22) ïîëó÷èì
y g q y g f q y g 1 y1 1 1 0 1 1 1� # � � � # � # �� � �
� �
� � �
� �( ) ( ( ) ) ( )x .
Óñòàíîâèì àâòîìàò M â òàêîå ñîñòîÿíèå q0 , ÷òî f q 0( )0 � , è ïîäàäèì íà íåãî
âõîäíîé ñèìâîë x1 1� . Èç ñèñòåìû óðàâíåíèé (22) ñëåäóåò
y g q y g f q y g g1 1 1 0 1 1� # � � � # � # �� � � �
� � �
� � � �
� � �( ) ( ( ) ) ( ) ( )x y1.
Ñëåäñòâèå 3. Ïàðàìåòð
�
��K n \ { }0 àâòîìàòà M n�A îäíîçíà÷íî èäåíòèôèöè-
ðóåòñÿ òîãäà è òîëüêî òîãäà, êîãäà âñå êîìïîíåíòû âåêòîðà
�
��K n \ { }0 — îáðàòè-
ìûå ýëåìåíòû êîëüöà � .
Äîêàçàòåëüñòâî. Ïðè ôèêñèðîâàííîì âåêòîðå
�
��K n \ { }0 óðàâíåíèå
g a�
�
�
�( ) � (ãäå a y� 2 , åñëè M n�A ,1, è a y� 1, åñëè M n�A ,2 ) èìååò åäèíñòâåííîå ðå-
øåíèå
�
��K n \ { }0 òîãäà è òîëüêî òîãäà, êîãäà âñå êîìïîíåíòû âåêòîðà
�
��K n \ { }0 —
îáðàòèìûå ýëåìåíòû êîëüöà � .
Ñëåäñòâèå äîêàçàíî.
Èç òåîðåì 2 è 3 âûòåêàåò, ÷òî èäåíòèôèêàöèÿ ïàðàìåòðîâ
� � �
�� � �
�
, , ( ) \g 0�K n { }
íå âûçûâàåò çàòðóäíåíèé, åñëè ýêñïåðèìåíòàòîð ìîæåò óñòàíàâëèâàòü àâòîìàò
â ñîñòîÿíèå, óäîâëåòâîðÿþùåå çàäàííûì óñëîâèÿì. Îäíàêî ÷àñòî èìåííî ýòî óñëî-
âèå íåâûïîëíèìî èç-çà íàëè÷èÿ ïàðàìåòðîâ, îïðåäåëÿþùèõ êîíêðåòíûé âèä îòî-
áðàæåíèÿ f :K Kn n% . Èäåíòèôèêàöèÿ òàêèõ ïàðàìåòðîâ, êàê ïðàâèëî, ïðåäñòàâëÿ-
åò îñíîâíóþ ñëîæíîñòü ðåøåíèÿ çàäà÷ ïàðàìåòðè÷åñêîé èäåíòèôèêàöèè äëÿ
àâòîìàòîâ íàä êîëüöîì � .
28 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4
Îáîçíà÷èì A
n,1
inv ìíîæåñòâî âñåõ îáðàòèìûõ àâòîìàòîâ M n�A ,1 (õàðàêòåðèçóå-
ìûõ òåì, ÷òî âñå êîìïîíåíòû âåêòîðà
�
� �K n \ { }0 — îáðàòèìûå ýëåìåíòû êîëüöà � ),
à A
n,2
inv — ìíîæåñòâî âñåõ îáðàòèìûõ àâòîìàòîâ M n�A ,2 (âñå êîìïîíåíòû âåêòî-
ðîâ
� �
� �, \�K n { }0 — îáðàòèìûå ýëåìåíòû êîëüöà � ). Ïîëîæèì An
inv �
� �A A
n n, ,1 2
inv inv . Äëÿ ëþáîãî àâòîìàòà M n�A inv èñòèííû ïðåäëîæåíèÿ 1, 3–6, òåîðå-
ìû 2, 3, à òàêæå ñëåäñòâèÿ 2, 3. Ýòè óòâåðæäåíèÿ ïðåäñòàâëÿþò ñîáîé îáùèå êîíå÷-
íî-àâòîìàòíûå õàðàêòåðèñòèêè ñèììåòðè÷íîãî ïîòî÷íîãî øèôðà, ïîñòðîåííîãî íà
îñíîâå àâòîìàòà M n�A inv .
Ìíîæåñòâî àâòîìàòîâ An ïîñòðîåíî íà îñíîâå ïðîèçâîëüíîãî ôèêñèðîâàííî-
ãî ñåìåéñòâà òàêèõ îòîáðàæåíèé f K Ki
n: % ( , , )i n�1 � , ÷òî | |Val fi �1 äëÿ âñåõ
i n�1, ,� . Ðàññìîòðèì òåïåðü ñåìåéñòâî îòîáðàæåíèé f K Ki
n: % ( , , )i n�1 � . Çà-
ôèêñèðóåì òàêîå ïðîèçâîëüíîå îòîáðàæåíèå f K Kn: % , ÷òî | |Val f �1, è ïðîèç-
âîëüíóþ öèêëè÷åñêóþ ïîäñòàíîâêó ��S n (ãäå S n — ñèììåòðè÷åñêàÿ ãðóïïà).
Ïîëîæèì
f u u f u ui n ni i( , , ) ( , , )
( ) ( )1 11 1� �� � �� �
( , , )i n�1 � ,
ãäå �0 — òîæäåñòâåííàÿ ïîäñòàíîâêà (ò.å. åäèíèöà ãðóïïû S n ). Îòîáðàæåíèå
f : K Kn n% , îïðåäåëÿåìîå ñåìåéñòâîì îòîáðàæåíèé f K Ki
n: % ( , , )i n�1 � , õà-
ðàêòåðèçóåòñÿ òåì, ÷òî îíî ÿâëÿåòñÿ:
1) ñèììåòðè÷íûì îòîáðàæåíèåì îòíîñèòåëüíî ïðåîáðàçîâàíèé êîîðäèíàò,
îïðåäåëÿåìûõ öèêëè÷åñêîé ãðóïïîé, ïîðîæäåííîé ïîäñòàíîâêîé �;
2) ñòàáèëüíûì îòîáðàæåíèåì íà ìíîæåñòâå D
K n .
Ìíîæåñòâî àâòîìàòîâ An , ïîñòðîåííîå íà îñíîâå îòîáðàæåíèÿ f :K Kn n% ,
íàçîâåì ìíîæåñòâîì ñèììåòðè÷åñêèõ àâòîìàòîâ íàä êîëüöîì � .  ñèëó ïðåäëîæå-
íèÿ 6 ëþáîé ñèììåòðè÷åñêèé àâòîìàò M n�A ( )n � 2 íå ÿâëÿåòñÿ ñèëüíîñâÿçíûì
àâòîìàòîì, åñëè âñå êîìïîíåíòû âåêòîðà
�
��K n \ { }0 ðàâíû ìåæäó ñîáîé. Îòìåòèì,
÷òî ñèììåòðè÷åñêèå àâòîìàòû íàä êîëüöîì �
pk , èññëåäîâàííûå â [15], ÿâëÿþòñÿ
ñïåöèàëüíûì ñëó÷àåì òàêèõ àâòîìàòîâ.
ÇÀÊËÞ×ÅÍÈÅ
 ðàáîòå ñ ïîçèöèè ñëîæíîñòè âû÷èñëåíèé ðàññìîòðåíû ìåòîäû àíàëèçà àâòîìà-
òîâ íàä êîíå÷íûì êîììóòàòèâíî-àññîöèàòèâíûì êîëüöîì � ñ åäèíèöåé.
Ïðåäëîæåííàÿ ñõåìà âû÷èñëåíèÿ îöåíîê, îñíîâàííûõ íà ìîùíîñòè ïîäìíî-
æåñòâ çàäàííîãî ìíîæåñòâà àâòîìàòîâ íàä êîíå÷íûì êîëüöîì, ÿâëÿåòñÿ îñíîâîé
äëÿ èññëåäîâàíèÿ ñâîéñòâ, ôîðìóëèðóåìûõ â òåðìèíàõ «äëÿ ïî÷òè âñåõ àâòîìà-
òîâ …», «äîëÿ àâòîìàòîâ …» è ò.ä., äîêàçàòåëüñòâî êîòîðûõ ÷àñòî îñóùåñòâëÿåòñÿ
ñ ïðèìåíåíèåì ìåòîäîâ òåîðèè âåðîÿòíîñòåé. Ïðîðàáîòêà ýòîé ñõåìû äëÿ ðåøåíèÿ
òàêèõ çàäà÷ — îäíî èç âîçìîæíûõ íàïðàâëåíèé èññëåäîâàíèé.
Ñõåìà ðåøåíèÿ íàä êîëüöîì � ñèñòåì ïîëèíîìèàëüíûõ óðàâíåíèé ñ ïàðàìåò-
ðàìè, îñíîâàííàÿ íà èñïîëüçîâàíèè êëàññîâ àññîöèèðîâàííûõ ýëåìåíòîâ, äàåò âîç-
ìîæíîñòü ýôôåêòèâíî íàõîäèòü ðåøåíèÿ äëÿ ñïåöèàëüíûõ òèïîâ òàêèõ ñèñòåì íàä
êîëüöîì �
pk , ÷òî ïðîèëëþñòðèðîâàíî ïðèìåðîì 2. Èç íåãî âûòåêàåò, ÷òî ýôôåê-
òèâíîå ïðèìåíåíèå ïðåäëîæåííîé ñõåìû äëÿ êîëüöà � äîëæíî áûòü îñíîâàíî íà
ïîíÿòèè «òèï» äëÿ ýëåìåíòà êîëüöà � . Ïî-âèäèìîìó, òàêîé «òèï» äîëæåí ïðåä-
ñòàâëÿòü ñîáîé âåêòîð, êîìïîíåíòàìè êîòîðîãî ÿâëÿþòñÿ ïîêàçàòåëè ñòåïåíåé ýëå-
ìåíòîâ ìíîæåñòâà B0 â ðàçëîæåíèè ýëåìåíòà êîëüöà � â ïðîèçâåäåíèå íåïðèâîäè-
ìûõ ýëåìåíòîâ. Ïðè ýòîì, â îòëè÷èå îò êîëüöà �
pk , ìíîæåñòâî òèïîâ ýëåìåíòîâ
÷àñòè÷íî óïîðÿäî÷åíî, ÷òî óñëîæíÿåò àíàëèç âîçìîæíûõ ñëó÷àåâ ïðè ïîñòðîåíèè
ìíîæåñòâà ðåøåíèé. Äåòàëüíàÿ ïðîðàáîòêà ýòèõ àñïåêòîâ — äðóãîå íàïðàâëåíèå
äàëüíåéøèõ èññëåäîâàíèé.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4 29
Óñòàíîâëåííûå â ðàçä. 3 îáùèå õàðàêòåðèñòèêè àâòîìàòîâ íàä êîëüöîì � äî-
ïóñêàþò îáîáùåíèå â ñëåäóþùèõ äâóõ íàïðàâëåíèÿõ: èññëåäîâàíèå ñëó÷àåâ, êîãäà
îòîáðàæåíèå g �
�
ÿâëÿåòñÿ ëèáî ïðîèçâîëüíûì ëèíåéíûì îòîáðàæåíèåì, ëèáî íåëè-
íåéíûì îòîáðàæåíèåì ñïåöèàëüíîãî âèäà; ïåðåõîä îò àâòîìàòîâ, îñóùåñòâëÿþùèõ
îòîáðàæåíèå âèäà K K n� �% ( ) ê àâòîìàòàì, îñóùåñòâëÿþùèì îòîáðàæåíèå âèäà
( ) ( )K Km n� �% .
Àâòîðû âûðàæàþò èñêðåííþþ áëàãîäàðíîñòü àêàäåìèêó ÍÀÍ Óêðàèíû,
ïðîôåññîðó Àëåêñàíäðó Àäîëüôîâè÷ó Ëåòè÷åâñêîìó çà âíèìàíèå ê ðàáîòå, ïîëåç-
íûå ñîâåòû è èäåè, âîçìîæíî, íå â ïîëíîé ìåðå ðåàëèçîâàííûå â ïðîöåññå
âûïîëíåíèÿ íàñòîÿùåãî èññëåäîâàíèÿ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ê ó ç í å ö î â Ñ . Ï . Äèíàìè÷åñêèé õàîñ. — Ì.: Ôèçìàòëèò, 2001. — 296 ñ.
2. Ê î ñ ò å í ê î Ï . Þ . , À í ò î í î â À .  . , Ê î ñ ò å í ê î Ò . Ï . Îáðàòíûå çàäà÷è õàîòè÷åñêîé
äèíàìèêè è ñòàòèñòè÷åñêèé àíàëèç ïðè îáåñïå÷åíèè èíôîðìàöèîííîé ñêðûòíîñòè â êîììóíèêà-
öèîííûõ ñèñòåìàõ è ñåòÿõ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2006. — ¹ 5. — Ñ. 96–106.
3. Ê î ñ ò å í ê î Ï . Þ . , À í ò î í î â À . Â . , Ê î ñ ò å í ê î Ò . Ï . Ðàçâèòèå êîíöåïöèè îäíîñòîðîííèõ
ôóíêöèé äëÿ ñèñòåì êðèïòîãðàôè÷åñêîé çàùèòû èíôîðìàöèè ñ èñïîëüçîâàíèåì äîñòèæåíèé
õàîòè÷åñêîé äèíàìèêè // Òàì æå. — 2006. — ¹ 6. — Ñ. 136–146.
4. Ã è ë ë À . Ëèíåéíûå ïîñëåäîâàòåëüíîñòíûå ìàøèíû. — Ì.: Íàóêà, 1974. — 298 ñ.
5. Ô à ð à ä æ å â Ð . Ã . Ëèíåéíûå ïîñëåäîâàòåëüíîñòíûå ìàøèíû. — Ì.: Ñîâ. ðàäèî, 1975. — 248 ñ.
6. À ã è á à ë î â Ã . Ï . Ðàñïîçíàâàíèå îïåðàòîðîâ, ðåàëèçóåìûõ â ëèíåéíûõ àâòîíîìíûõ àâòîìàòàõ //
Èçâ. ÀÍ ÑÑÑÐ. Òåõí. êèáåðíåòèêà. — 1970. — ¹ 3. — Ñ. 99–108.
7. À ã è á à ë î â Ã . Ï . , Þ ô è ò ß . Ã . Î ïðîñòûõ ýêñïåðèìåíòàõ äëÿ ëèíåéíûõ èíèöèàëüíûõ
àâòîìàòîâ // Àâòîìàòèêà è âû÷èñë. òåõíèêà. — 1972. — ¹ 2. — Ñ. 17–19.
8. Ñ ï å ð à í ñ ê è é Ä .  . Ýêñïåðèìåíòû ñ ëèíåéíûìè è áèëèíåéíûìè êîíå÷íûìè àâòîìàòàìè. —
Ñàðàòîâ: Èçä-âî Ñàðàòîâ. óí-òà, 2004. — 144 ñ.
9. Ê ó ð î ø À . Ã . Ëåêöèè ïî îáùåé àëãåáðå. — Ì.: Íàóêà, 1973. — 400 ñ.
10. Ê ó ç ü ì è í À . Ñ . , Ê ó ð à ê è í  . Ë . , Í å ÷ à å â À . À . Ïñåâäîñëó÷àéíûå è ïîëèëèíåéíûå
ïîñëåäîâàòåëüíîñòè // Òð. ïî äèñêðåò. ìàòåìàòèêå. — Ì.: Íàó÷. èçä-âî «ÒÂÏ», 1997. — 1. —
Ñ. 139–202.
11. Ê ó ç ü ì è í À . Ñ . , Ê ó ð à ê è í Â . Ë . , Í å ÷ à å â À . À . Ñâîéñòâà ëèíåéíûõ è ïîëèëèíåéíûõ
ðåêóððåíò íàä êîëüöàìè Ãàëóà (I) // Òàì æå. — 1998. — 2. — Ñ. 191–222.
12. Ñ ê î á å ë å â Â . Â . Àíàëèç ñòðóêòóðû êëàññà ëèíåéíûõ àâòîìàòîâ íàä êîëüöîì �
pk // Êèáåðíåòèêà
è ñèñòåìíûé àíàëèç. — 2008. — ¹ 3. — Ñ. 60–74.
13. Ñ ê î á å ë å â  .  . Õàðàêòåðèñòèêè ëèíåéíûõ îäíîìåðíûõ àâòîìàòîâ ñ ëàãîì l íàä êîíå÷íûì
êîëüöîì // Òð. ÈÏÌÌ ÍÀÍ Óêðàèíû. — 2008. — 16. — Ñ. 190–196.
14. Ñ ê î á å ë å â  . à . Íåëèíåéíûå àâòîìàòû íàä êîíå÷íûì êîëüöîì // Êèáåðíåòèêà è ñèñòåìíûé
àíàëèç. — 2006. — ¹ 6. — Ñ. 29–42.
15. Ñ ê î á å ë å â  .  . Î äâóõ òèïàõ íåëèíåéíûõ àâòîìàòîâ íàä êîíå÷íûì êîëüöîì // Òàì æå. — 2009.
— ¹ 4. — Ñ. 57–68.
16. Ñ ê î á å ë å â  .  . Òî÷íàÿ ôîðìóëà äëÿ ÷èñëà îáðàòèìûõ ìàòðèö íàä êîíå÷íûì êîëüöîì //
Òð. ÈÏÌÌ ÍÀÍ Óêðàèíû. — 2009. — 18. — Ñ. 155–158.
17. Ñ ê î á å ë å â Â . Â . , Ñ ê î á å ë å â Â . Ã . Àíàëèç øèôðñèñòåì. — Äîíåöê: ÈÏÌÌ ÍÀÍ Óêðàèíû,
2009. — 479 ñ.
Ïîñòóïèëà 23.03.2010
30 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4
|