Применение p-адической модели в решении конечно-становой сопряженности кусочно-линейных сферически-транзитивных автоморфизмов корневого бинарного дерева
Использована p-адическая модель для решения конечно-становой сопряженности кусочно-линейных сферично-транзитивных автоморфизмов корневого бинарного дерева. Использование численных p-адических методов является технически удобным для работы с конечными автоматами....
Збережено в:
| Дата: | 2014 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2014
|
| Назва видання: | Электронное моделирование |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/100989 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Применение p-адической модели в решении конечно-становой сопряженности кусочно-линейных сферически-транзитивных автоморфизмов корневого бинарного дерева / Д.И. Морозов // Электронное моделирование. — 2014 — Т. 36, № 1. — С. 107-112. — Бібліогр.: 4 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-100989 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1009892016-05-29T03:03:13Z Применение p-адической модели в решении конечно-становой сопряженности кусочно-линейных сферически-транзитивных автоморфизмов корневого бинарного дерева Морозов, Д.И. Краткие сообщения Использована p-адическая модель для решения конечно-становой сопряженности кусочно-линейных сферично-транзитивных автоморфизмов корневого бинарного дерева. Использование численных p-адических методов является технически удобным для работы с конечными автоматами. Застосовано p-адичну модель для розв’язку скінченно-станової спряженості кусково-лінійних сферично-транзитивних автоморфізмів кореневого бінарного дерева. Використання чисельних p-адичних методів є технічно зручним для роботи зі скінченними автоматами. The p-adic model was used for solving the finite-state conjugacy of the piecewise-linear spherical-transitive automorphism of the binary rooted tree. The use of numerical p-adic methods provides a convenient technique for working with finite-state automata. 2014 Article Применение p-адической модели в решении конечно-становой сопряженности кусочно-линейных сферически-транзитивных автоморфизмов корневого бинарного дерева / Д.И. Морозов // Электронное моделирование. — 2014 — Т. 36, № 1. — С. 107-112. — Бібліогр.: 4 назв. — рос. 0204-3572 http://dspace.nbuv.gov.ua/handle/123456789/100989 517.5 ru Электронное моделирование Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Краткие сообщения Краткие сообщения |
| spellingShingle |
Краткие сообщения Краткие сообщения Морозов, Д.И. Применение p-адической модели в решении конечно-становой сопряженности кусочно-линейных сферически-транзитивных автоморфизмов корневого бинарного дерева Электронное моделирование |
| description |
Использована p-адическая модель для решения конечно-становой сопряженности кусочно-линейных сферично-транзитивных автоморфизмов корневого бинарного дерева. Использование численных p-адических методов является технически удобным для работы с конечными автоматами. |
| format |
Article |
| author |
Морозов, Д.И. |
| author_facet |
Морозов, Д.И. |
| author_sort |
Морозов, Д.И. |
| title |
Применение p-адической модели в решении конечно-становой сопряженности кусочно-линейных сферически-транзитивных автоморфизмов корневого бинарного дерева |
| title_short |
Применение p-адической модели в решении конечно-становой сопряженности кусочно-линейных сферически-транзитивных автоморфизмов корневого бинарного дерева |
| title_full |
Применение p-адической модели в решении конечно-становой сопряженности кусочно-линейных сферически-транзитивных автоморфизмов корневого бинарного дерева |
| title_fullStr |
Применение p-адической модели в решении конечно-становой сопряженности кусочно-линейных сферически-транзитивных автоморфизмов корневого бинарного дерева |
| title_full_unstemmed |
Применение p-адической модели в решении конечно-становой сопряженности кусочно-линейных сферически-транзитивных автоморфизмов корневого бинарного дерева |
| title_sort |
применение p-адической модели в решении конечно-становой сопряженности кусочно-линейных сферически-транзитивных автоморфизмов корневого бинарного дерева |
| publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| publishDate |
2014 |
| topic_facet |
Краткие сообщения |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/100989 |
| citation_txt |
Применение p-адической модели в решении конечно-становой сопряженности кусочно-линейных сферически-транзитивных автоморфизмов корневого бинарного дерева / Д.И. Морозов // Электронное моделирование. — 2014 — Т. 36, № 1. — С. 107-112. — Бібліогр.: 4 назв. — рос. |
| series |
Электронное моделирование |
| work_keys_str_mv |
AT morozovdi primeneniepadičeskojmodelivrešeniikonečnostanovojsoprâžennostikusočnolinejnyhsferičeskitranzitivnyhavtomorfizmovkornevogobinarnogodereva |
| first_indexed |
2025-07-07T10:17:20Z |
| last_indexed |
2025-07-07T10:17:20Z |
| _version_ |
1836982932783235072 |
| fulltext |
ÓÄÊ 517.5
Ä.È. Ìîðîçîâ, êàíä. ôèç.-ìàò. íàóê
Íàöèîíàëüíèé óíèâåðñèòåò «Êèåâî-Ìîãèëÿíñêàÿ àêàäåìèÿ»
(Óêðàèíà, 04655, Êèåâ, óë. Ã. Ñêîâîðîäè, 2,
òåë. (063) 6128335, e-mail: denis.morozov178@gmail.com)
Ïðèìåíåíèå p-àäè÷åñêîé ìîäåëè
â ðåøåíèè êîíå÷íî-ñòàíîâîé ñîïðÿæåííîñòè
êóñî÷íî-ëèíåéíûõ ñôåðè÷åñêè-òðàíçèòèâíûõ
àâòîìîðôèçìîâ êîðíåâîãî áèíàðíîãî äåðåâà
Èñïîëüçîâàíà p-àäè÷åñêàÿ ìîäåëü äëÿ ðåøåíèÿ êîíå÷íî-ñòàíîâîé ñîïðÿæåííîñòè êó-
ñî÷íî-ëèíåéíûõ ñôåðè÷íî-òðàíçèòèâíûõ àâòîìîðôèçìîâ êîðíåâîãî áèíàðíîãî äåðåâà.
Èñïîëüçîâàíèå ÷èñëåííûõ p-àäè÷åñêèõ ìåòîäîâ ÿâëÿåòñÿ òåõíè÷åñêè óäîáíûì äëÿ ðàáî-
òû ñ êîíå÷íûìè àâòîìàòàìè.
Çàñòîñîâàíî p-àäè÷íó ìîäåëü äëÿ ðîçâ’ÿçêó ñê³í÷åííî-ñòàíîâî¿ ñïðÿæåíîñò³ êóñêîâî-
ë³í³éíèõ ñôåðè÷íî-òðàíçèòèâíèõ àâòîìîðô³çì³â êîðåíåâîãî á³íàðíîãî äåðåâà. Âèêî-
ðèñòàííÿ ÷èñåëüíèõ p-àäè÷íèõ ìåòîä³â º òåõí³÷íî çðó÷íèì äëÿ ðîáîòè ç³ ñê³í÷åííèìè
àâòîìàòàìè.
Ê ë þ ÷ å â û å ñ ë î â à: àâòîìîðôèçì, êîðíåâîå äåðåâî, èçîìåòðèÿ, p-àäè÷åñêèé.
 1980 ã. áûëà ðåøåíà ïðîáëåìà Ìèëíîðà ñóùåñòâîâàíèÿ ãðóïï ïðîìåæó-
òî÷íîãî ðîñòà [1] è ïðåäëîæåíà ãðóïïà, ïîðîæäåííàÿ êîíå÷íûì ìíî-
æåñòâîì îáðàòèìûõ àâòîìàòîâ íàä êîíå÷íûì àëôàâèòîì, èìåþùàÿ ïðî-
ìåæóòî÷íûé ðîñò. Ñ ïîäîáíûìè ãðóïïàìè ñâÿçàíà ñåðèÿ ñëîæíûõ ïðîá-
ëåì. Èññëåäóåì îäíó èç íèõ.
Ãðóïïû îáðàòèìûõ àâòîìàòîâ íàä êîíå÷íûì àëôàâèòîì åñòåñòâåííûì
îáðàçîì ïðåäñòàâëÿþòñÿ ïîäãðóïïàìè àâòîìîðôèçìîâ êîðíåâîãî îäíî-
ðîäíîãî äåðåâà. Äëÿ òàêèõ ãðóïï ïðîáëåìà êîíå÷íî-ñòàíîâîé ñîïðÿæåí-
íîñòè íå ðåøåíà [2], â îòëè÷èå îò ïðîáëåìû îáùåé ñîïðÿæåííîñòè â
ãðóïïå àâòîìîðôèçìîâ îäíîðîäíîãî êîðíåâîãî äåðåâà, ãäå ðåøåíèå ïîëó-
÷åíî íà îñíîâàíèè èññëåäîâàíèÿ èçîìîðôíîñòè äåðåâüåâ òèïà àâòîìîð-
ôèçìîâ, äëÿ êîòîðûõ ïðîâåðÿåòñÿ ñîïðÿæåííîñòü.
Ïðè ðåøåíèè äàííîé ïðîáëåìû åñòåñòâåííûì ÿâëÿåòñÿ ïîñòåïåííîå
ðàñøèðåíèå êëàññà àâòîìîðôèçìîâ êîðíåâîãî îäíîðîäíîãî äåðåâà, äëÿ
êîòîðûõ äàííàÿ ïðîáëåìà ðåøåíà.  êà÷åñòâå òàêîãî êëàññà ðàññìîòðèì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 1 107
� Ä.È. Ìîðîçîâ, 2014
�������
�
����
êëàññ êóñî÷íî-ëèíåéíûõ ñôåðè÷åñêè-òðàíçèòèâíûõ àâòîìîðôèçìîâ êîð-
íåâîãî áèíàðíîãî äåðåâà.
Äëÿ ðàáîòû ñ àâòîìîðôèçìàìè êîðíåâîãî áèíàðíîãî äåðåâà ñóùåñò-
âóåò óäîáíàÿ òåõíèêà ïðåäñòàâëåíèÿ èõ â âèäå èçîìåòðèé êîëüöà Z2 öåëûõ
2-àäè÷åñêèõ ÷èñåë. Îïðåäåëåíèå êîðíåâîãî áèíàðíîãî äåðåâà ñîñòîèò â ñëå-
äóþùåì. Ìíîæåñòâî âåðøèí äåðåâà ðàçáèâàåòñÿ íà ïîäìíîæåñòâà âåðøèí
îäíîãî óðîâíÿ:
a) v0 — êîðåíü èëè âåðøèíà íóëåâîãî óðîâíÿ;
á) äëÿ êàæäîãî i �0 1 2, , ... äåðåâî ñîäåðæèò2i âåðøèí è ðåáåð i-ãî óðîâíÿ.
Ââåäåì îòíîøåíèå ñìåæíîñòè: êàæäàÿ âåðøèíà i-ãî óðîâíÿ ñìåæíà ñ
äâóìÿ âåðøèíàìè (ëåâîé è ïðàâîé) (i + 1)-ãî óðîâíÿ. Êîîðäèíàòèçàöèÿ
ðåáåð ýòîãî äåðåâà ïðîèñõîäèò ñëåäóþùèì îáðàçîì: äâà ñìåæíûõ ðåáðà,
ñîåäèíÿþùèõ âåðøèíó i-ãî óðîâíÿ ñ äâóìÿ âåðøèíàìè (i + 1)-ãî óðîâíÿ,
ïîëó÷àþò îòìåòêè 0 (ëåâîå) è 1 (ïðàâîå). Íîìåðà óðîâíåé âåðøèí ÿâëÿþò-
ñÿ èíâàðèàíòíûìè îòíîñèòåëüíî äåéñòâèÿ ãðóïïû àâòîìîðôèçìîâ äåðåâà
T2. Àâòîìîðôèçì, äåéñòâóÿ íà T2, èíäóöèðóåò äåéñòâèå íà âñåõ ïîääå-
ðåâüÿõ äåðåâà T2, êîòîðîå ÿâëÿåòñÿ ñàìîïîäîáíûì. Èíäóöèðîâàííûå äåéñò-
âèÿ àâòîìîðôèçìà íà ïîääåðåâüÿõ, èçîìîðôíûõ T2, íàçîâåì ñîñòîÿíèÿìè
äàííîãî àâòîìîðôèçìà.
Îïðåäåëåíèå 1. Àâòîìîðôèçì äåðåâà T2 íàçûâàåòñÿ êîíå÷íî-ñòàíî-
âûì, åñëè ìíîæåñòâî åãî ñîñòîÿíèé — êîíå÷íî. Òàêèå àâòîìîðôèçìû
îáðàçóþò ãðóïïó F TAut 2.
Ëþáîé áåñêîíå÷íûé ïóòü áåç öèêëîâ, íà÷èíàþùèéñÿ â êîðíå v0, áó-
äåì íàçûâàòü êîíöîì äåðåâà. Òàêîé ïóòü êîîðäèíàòèçèðóåòñÿ áåñêîíå÷-
íîé âëåâî ïîñëåäîâàòåëüíîñòüþ 0 è 1 îïèñàííûì âûøå ñïîñîáîì. Ðàñ-
ñìîòðèì ýòó áåñêîíå÷íóþ äâîè÷íóþ ïîñëåäîâàòåëüíîñòü, êàê 2-àäè÷åñêîå
÷èñëî èç ñîîòâåòñòâóþùåãî êîëüöà Z2.
Îòîæäåñòâëÿÿ êîîðäèíàòèçàöèþ ïóòåé ñ äâîè÷íûì ðàçëîæåíèåì öå-
ëûõ 2-àäè÷åñêèõ ÷èñåë, ïîëó÷èì ïðåäñòàâëåíèå àâòîìîðôèçìîâ äåðåâà T2
ôóíêöèÿìè íà Z2. Êàæäîìó àâòîìîðôèçìó äåðåâà ñîîòâåòñòâóåò ôóíêöèÿ
f � : åñëè àâòîìîðôèçì � ïåðåâîäèò êîíåö x â êîíåö y, òî f x y� ( ) � . Íàïðè-
ìåð, êîíå÷íûé àâòîìàò, çàäàâàåìûé ñîîòíîøåíèÿìè a id a s� ( , ) , id id id� ( , )
ñîîòâåòñòâóåò 2-àäè÷åñêîé èçîìåòðèè f x x( ) � �1, êîòîðàÿ èìååò âàæíîå
çíà÷åíèå â òåîðèè âû÷èñëèìîñòè, ïîñêîëüêó ÿâëÿåòñÿ áàçîâîé ïðèìèòèâ-
íî-ðåêóðñèâíîé ôóíêöèåé.
Àâòîìîðôèçìû, êîòîðûì ñîîòâåòñòâóþò ëèíåéíûå ôóíêöèè êîëüöà Z2,
áóäåì íàçûâàòü ëèíåéíûìè. Èññëåäîâàíèå ãðóïïû àâòîìîðôèçìîâ êîðíå-
âîãî îäíîðîäíîãî äåðåâà ñ ïîìîùüþ èçîìåòðèé êîëüöà öåëûõ p-àäè÷åñêèõ
÷èñåë ïîçâîëÿåò ðåøàòü ðÿä ïðîáëåì, ñâÿçàííûõ ñ ýòîé ãðóïïîé.
Ñëåäóåò çàìåòèòü, ÷òî ïðîáëåìà êîíå÷íî-ñòàíîâîé ñîïðÿæåííîñòè â äàí-
íîé ãðóïïå äîñòàòî÷íî ñëîæíà, è ñóùåñòâóþò ãðóïïû, ïîðîæäåííûå êîíå÷-
Ä.È. Ìîðîçîâ
108 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 1
íûìè ãðóïïîâûìè àâòîìàòàìè, äëÿ êîòîðûõ äàííàÿ ïðîáëåìà íåðàçðåøèìà
[2], â îòëè÷èå, íàïðèìåð, îò ïðîáëåìû ñîïðÿæåííîñòè â ãðóïïå íåâûðîæ-
äåííûõ ëèíåéíûõ îïåðàòîðîâ íàä ïîëåì. Ýòà ïðîáëåìà, êàê èçâåñòíî, ýêâè-
âàëåíòíà íàõîæäåíèþ æîðäàíîâîé íîðìàëüíîé ôîðìû äàííûõ îïåðàòîðîâ.
Ðàññìîòðèì ðåøåíèå ïðîáëåìû êîíå÷íî-ñòàíîâîé ñïðÿæåííîñòè äëÿ
ñôåðè÷åñêè-òðàíçèòèâíûõ êóñî÷íî-ëèíåéíûõ àâòîìîðôèçìîâ êîðíåâîãî
áèíàðíîãî äåðåâà. Ïðè òàêîì îãðàíè÷åíèè ìíîæåñòâà àâòîìîðôèçìîâ ñó-
ùåñòâóåò ýôôåêòèâíûé àëãîðèòì ðåøåíèÿ ýòîé ïðîáëåìû.
 [3] äîêàçàíî ñëåäóþùåå óòâåðæäåíèå ïðè óñëîâèè, ÷òî F TAut 2 —
ãðóïïà êîíå÷íî-ñòàíîâûõ àâòîìîðôèçìîâ êîðíåâîãî áèíàðíîãî äåðåâà.
Ëåììà 1. f x p x p F T p p Z Q( ) ,� � � � �1 2 2 1 2 2Aut � .
Òåîðåìà 1. Àâòîìîðôèçìû f x k x t k t Z( ) ( ) ( ) ( , )� � � � �4 1 2 1 2 ÿâëÿþòñÿ
ñôåðè÷åñêè-òðàíçèòèâíûìè.
Òåîðåìà 2. Èçîìåòðèè f x k x1 14 1 1( ) ( )� � � è f x k x2 24 1( ) ( )� � �
� �1 1 2 2
( , )k k ZQ ñîïðÿæåíû â F T k kAut 2 1 24 1 4 1� � � � .
Îïðåäåëåíèå 2. Íàçîâåì êîíå÷íî-ñòàíîâîé ñôåðè÷åñêè-òðàíçèòèâíûé
àâòîìîðôèçì äåðåâà T2 0-ïîëíûì, åñëè îáðàç äåéñòâèÿ åãî öåíòðàëèçà-
òîðà â F TAut 2 íà 0 ñîâïàäàåò ñ ìíîæåñòâîì êâàçèïåðèîäè÷åñêèõ êîíöîâ
äåðåâà T2.
Íåîáõîäèìî îáðàòèòü âíèìàíèå íà òî, ÷òî äëÿ ïðîâåðêè êîíå÷íî-ñòà-
íîâîé ñîïðÿæåííîñòè äâóõ êîíå÷íî-ñòàíîâûõ ñôåðè÷åñêè-òðàíçèòèâíûõ
àâòîìîðôèçìîâ, èç êîòîðûõ îäèí ÿâëÿåòñÿ 0-ïîëíûì, äîñòàòî÷íî ïðîâå-
ðèòü êîíå÷íî-ñòàíîâîñòü ðåøåíèÿ óðàâíåíèÿ ñïðÿæåííîñòè, êîòîðîå 0
ïåðåâîäèò â 0.
Îïðåäåëåíèå 3. Îïðåäåëèì � ( )a äëÿ ñôåðè÷åñêè-òðàíçèòèâíîãî àâòî-
ìîðôèçìà a b c� ( , )� â âèäå � ( )a = bc è îïðåäåëèì �
n a( ), êàê n-þ
èòåðàöèþ � ( )a .
 [4] äîêàçàíà ñëåäóþùàÿ òåîðåìà.
Òåîðåìà 3. Ïóñòü a, b — 0-ïîëíûå ñôåðè÷åñêè-òðàíçèòèâíûå êîíå÷íî-
ñòàíîâûå èçîìåòðèè êîëüöà Z2. Èçîìåòðèè a è b ñîïðÿæåíû â F TAut 2
òîãäà è òîëüêî òîãäà, êîãäà �
n a( ) è �
n b( ) ñîïðÿæåíû â F TAut 2 äëÿ íå-
êîòîðîãî n N� .
Âîñïîëüçóåìñÿ äàëåå ýòèìè óòâåðæäåíèÿìè. Ñîãëàñíî òåîðåìå 2 àâ-
òîìîðôèçìû 5 1x � è 5 3x � ñîïðÿæåíû â F TAut 2, à àâòîìîðôèçìû 5 1x � è
9 1x � íå ñîïðÿæåíû â F TAut 2. Íî òåîðåìà 2 íå ïîçâîëÿåò îòâåòèòü íà
âîïðîñ, ñîïðÿæåíû ëè, íàïðèìåð, êîíå÷íî-ñòàíîâûå ñôåðè÷åñêè-òðàíçè-
òèâíûå àâòîìîðôèçìû âèäà( , )3 15 1x x � � è( , )5 29 3x x� � � , èëè ( , )x x15 1� �
è ( , )3 15 1x x � � (çàïèñü ( , )3 15 1x x � � îçíà÷àåò, ÷òî íà ëåâîå ïîääåðåâî äå-
ðåâà T2 äåéñòâóåò àâòîìîðôèçì f x x( ) �3 , íà ïðàâîå ïîääåðåâî — àâòî-
ìîðôèçì g x x( ) � �15 1è ÷òî ïðàâîå è ëåâîå ïîääåðåâüÿT2 ìåíÿþòñÿ ìåñòàìè).
Ïðèìåíåíèå p-àäè÷åñêîé ìîäåëè â ðåøåíèè êîíå÷íî-ñòàíîâîé ñîïðÿæåííîñòè
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 1 109
Îáîáùèì òåîðåìó 2 íà êëàññ êîíå÷íî-ñòàíîâûõ êóñî÷íî-ëèíåéíûõ
ñôåðè÷åñêè-òðàíçèòèâíûõ àâòîìîðôèçìîâ.
Îïðåäåëåíèå 4. Íàçîâåì àâòîìîðôèçì äåðåâà T2 êóñî÷íî-ëèíåéíûì,
åñëè ñóùåñòâóåò óðîâåíü äåðåâà T2, äëÿ êîòîðîãî âñå ñîñòîÿíèÿ ýòîãî
óðîâíÿ äàííîãî àâòîìîðôèçìà ÿâëÿþòñÿ ëèíåéíûìè.
Äëÿ èñïîëüçîâàíèÿ òåîðåìû 3 íåîáõîäèìû äîêàçàòåëüñòâà 0-ïîëíîòû
èññëåäóåìûõ êëàññîâ àâòîìîðôèçìîâ.
Ëåììà 2. Êîíå÷íî-ñòàíîâàÿ ëèíåéíàÿ ñôåðè÷åñêè-òðàíçèòèâíàÿ èçî-
ìåòðèÿ ÿâëÿåòñÿ 0-ïîëíîé.
Ä î ê à ç à ò å ë ü ñ ò â î. Ñïðàâåäëèâû ñëåäóþùèå ðàâåíñòâà:
((( ) ) ) ( ) ((( ) ) )a t x bt ax b a a t x bt b
� � � �
� � � �1 1 1 1�
�
� � �a a t x abt b(( ) )1 1 ,
( ) ((( ) ) (( ) )( )ax b a t x bt a t ax b bt�
� � �
� � � �� 1 1 1 1
�
� �
� � �
� � �a a t x b a t b bt a a t x abt b(( ) ) ( ) (( ) )1 1 1 1 1 .
Ñëåäîâàòåëüíî, àâòîìîðôèçì (( ) )a t x bt
� �1 1 êîììóòèðóåò ñ àâòîìîðôèç-
ìîì ax b a b t Z� �( , , )2 . Äåéñòâèòåëüíî, ñîãëàñíî ëåììå 1 ïðè a b t Z Q, , � 2 �
àâòîìîðôèçì (( ) )a t x bt
� �1 1 ÿâëÿåòñÿ êîíå÷íî-ñòàíîâûì, ò.å. ïðèíàäëå-
æèò öåíòðàëèçàòîðó C ax bF TAut 2
( )� .
Ñîãëàñíî òåîðåìå 1, åñëè àâòîìîðôèçì ax b� ÿâëÿåòñÿ ñôåðè÷åñêè-
òðàíçèòèâíûì, òî a a� � �4 1, b b� � �2 1, � ��a b Z, 2. Ïîñêîëüêó b — îáðàòèìûé
ýëåìåíò êîëüöà Z2 è 0 4 1� � �(( )a t x� � � � � �( ) ) ( )2 1 2 1b t b t, à 4 1� �a t — îáðà-
òèìî äëÿ ïðîèçâîëüíîãî t Z� 2 (ïðè óñëîâèè àâòîìîðôíîñòè ( )4 1� � �a t x
� � �( ) ))2 1b t , òî 0
2
� �C ax bF TAut ( ) Z Q2 � . Ëåììà 2 äîêàçàíà.
Îáîçíà÷èì ÷åðåç x a* äåéñòâèå àâòîìîðôèçìà à íà êîíåö äåðåâà x.
Ëåììà 3. Êîíå÷íî-ñòàíîâàÿ èçîìåòðèÿ a ÿâëÿåòñÿ 0-ïîëíîé òîãäà è
òîëüêî òîãäà, êîãäà �
n a( ) ÿâëÿåòñÿ 0-ïîëíîé äëÿ íåêîòîðîãî n N� .
Ä î ê à ç à ò å ë ü ñ ò â î. Äëÿ èçîìåòðèè a b c� ( , )� ñïðàâåäëèâû ñëåäóþ-
ùèå ñîîòíîøåíèÿ:
0 2 02
�
a at t( ( ) )� , 0 2 0 12 1
�
�
�a a bt t( ( ) )� .
Èòàê, èçîìåòðèÿ ÿâëÿåòñÿ 0-ïîëíîé òîãäà è òîëüêî òîãäà, êîãäà � ( )a
ÿâëÿåòñÿ 0-ïîëíîé. Ïðèìåíèâ ïîëó÷åííîå óòâåðæäåíèå n ðàç, ïîëó÷èì
àíàëîãè÷íîå óòâåðæäåíèå äëÿ �
n a( ).
Òåîðåìà 4. Êîíå÷íî-ñòàíîâàÿ êóñî÷íî-ëèíåéíàÿ ñôåðè÷åñêè-òðàíçè-
òèâíàÿ èçîìåòðèÿ ÿâëÿåòñÿ 0-ïîëíîé.
Ä î ê à ç à ò å ë ü ñ ò â î. Äëÿ êóñî÷íî-ëèíåéíîé ñôåðè÷åñêè-òðàí-
çèòèâíîé èçîìåòðèè a íàéäåòñÿ n N� òàêîå, ÷òî èçîìåòðèÿ �
n a( ) áóäåò
ëèíåéíîé. Ñîãëàñíî ëåììàì 2 è 3 òåîðåìà 4 äîêàçàíà.
Ä.È. Ìîðîçîâ
110 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 1
Òåîðåìà 5. Äâà êîíå÷íî-ñòàíîâûõ êóñî÷íî-ëèíåéíûõ ñôåðè÷åñêè-
òðàíçèòèâíûõ àâòîìîðôèçìà ñîïðÿæåííû â F TAut 2 òîãäà è òîëüêî òîãäà,
êîãäà â T2 íàéäåòñÿ óðîâåíü, äëÿ êîòîðîãî âñå àâòîìîðôèçìû ÿâëÿþòñÿ
ëèíåéíûìè, è ïðîèçâåäåíèÿ âñåõ êîýôôèöèåíòîâ õ ðàâíû äëÿ îáîèõ àâòî-
ìîðôèçìîâ.
Ä î ê à ç à ò å ë ü ñ ò â î. Ñóùåñòâîâàíèå â êóñî÷íî-ëèíåéíîì àâòîìîð-
ôèçìå óðîâíÿ, äëÿ êîòîðîãî âñå àâòîìîðôèçìû ÿâëÿþòñÿ ëèíåéíûìè, ñëå-
äóåò èç îïðåäåëåíèÿ êóñî÷íî-ëèíåéíîãî àâòîìîðôèçìà. Ñîãëàñíî òåîðåìå 2
êîíå÷íî-ñòàíîâûå ñôåðè÷åñêè-òðàíçèòèâíûå àâòîìîðôèçìû ax b� è cx d�
ñîïðÿæåííû â F TAut 2 òîãäà è òîëüêî òîãäà, êîãäà a c� . Èòàê, ñîãëàñíî
òåîðåìàì 3 è 4 ïîëó÷àåì óòâåðæäåíèå òåîðåìû 5.
Ðàññìîòðèì ïðèìåð ïðèìåíåíèÿ òåîðåìû 5. Êóñî÷íî-ëèíåéíûå ñôåðè-
÷åñêè-òðàíçèòèâíûå àâòîìîðôèçìû f x x x( ) ( , )� �3 13 � è g x x x( ) ( ,� � �9 2
� 7)� ñîãëàñíî òåîðåìå 5 ñîïðÿæåíû â F TAut 2, ïîñêîëüêó 3 3 9 1� � � .
Âûâîäû
Òàêèì îáðàçîì, ïðåäëîæåííàÿ 2-àäè÷åñêàÿ ìîäåëü êîíå÷íî-ñòàíîâîé ñî-
ïðÿæåííîñòè ïðåäñòàâëÿåò ñîáîé óäîáíóþ òåõíèêó äëÿ ðàáîòû ñ ãðóï-
ïîâûìè àâòîìàòàìè. Çàïèñü àâòîìàòà â âèäå ñîîòâåòñòâóþùåé 2-àäè÷åñêîé
ôóíêöèè èìååò áîëåå êîìïàêòíûé âèä, ÷åì çàïèñü àâòîìàòà â òðàäè-
öèîííîì àëãåáðàè÷åñêîì âèäå. Íàïðèìåð, àâòîìàò, ñîîòâåòñòâóþùèé
ôóíêöèè f x x( ) � �5 1, çàäàåòñÿ ñîîòíîøåíèÿìè
a b c� ( , ) � , b b d� ( , ), c a e� ( , ) � , d a c� ( , ), e d a� ( , ) .
Ñôîðìóëèðîâàííûé è äîêàçàííûé êðèòåðèé ñîïðÿæåííîñòè êîíå÷íî-
ñòàíîâûõ ñôåðè÷åñêè-òðàíçèòèâíûõ êóñî÷íî-ëèíåéíûõ èçîìåòðèé, à òàê-
æå îïèñàíèå êëàññîâ ñîïðÿæåííîñòè êîíå÷íî-ñòàíîâûõ ñôåðè÷åñêè-òðàí-
çèòèâíûõ êóñî÷íî-ëèíåéíûõ èçîìåòðèé ìîãóò áûòü èñïîëüçîâàíû ïðè
äàëüíåéøåì èññëåäîâàíèè âîïðîñà êîíå÷íî-ñòàíîâîé ñîïðÿæåííîñòè â
F TAut 2.
The p-adic model was used for solving the finite-state conjugacy of the piecewise-linear spheri-
cal-transitive automorphism of the binary rooted tree. The use of numerical p-adic methods pro-
vides a convenient technique for working with finite-state automata.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ãðèãîð÷óê Ð.È., Íåêðàøåâè÷ Â.Â., Ñóùàíñêèé Â.È. Àâòîìàòû, äèíàìè÷åñêèå ñèñòåìû è
ãðóïïû// Òð. ÌÈÀÍ. «Äèíàìè÷åñêèå ñèñòåìû, àâòîìàòû è áåñêîíå÷íûå ãðóïïû».Ò.231. —
Ì. : Íàóêà, 2000. — Ñ. 134—214.
Ïðèìåíåíèå p-àäè÷åñêîé ìîäåëè â ðåøåíèè êîíå÷íî-ñòàíîâîé ñîïðÿæåííîñòè
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 1 111
2. Sunic Z., Ventura E. The conjugacy problem in automaton groups is not solvable. [Ýëåêòðîí.
ðåñóðñ]. — Ðåæèì äîñòóïà: arXiv:1010.1993[math.GR], 11 May 2012 .
3. Ìîðîçîâ Ä.I. Ñïðÿæåíiñòü àâòîìîðôiçìiâ, ùî çàäàþòüñÿ ëiíiéíèìè ôóíêöiÿìè â ãðóïi
ñêií÷åííî-ñòàíîâèõ àâòîìîðôiçìiâ êîðåíåâîãî ñôåðè÷íî-îäíîðiäíîãî äåðåâà// Âiñí.
Êè¿âñüêîãî óí-òó. Ñåðiÿ : ôiçèêî-ìàòåìàòè÷íi íàóêè. — 2008. — Âèï. ¹ 1. — C. 40— 43.
4. Ìîðîçîâ Ä.I. Ñê³í÷åííî-ñòàíîâà ñïðÿæåí³ñòü ñôåðè÷íî-òðàíçèòèâíèõ àâòîìîðô³çì³â
êîðåíåâîãî á³íàðíîãî äåðåâà.// Íàóêîâèé ÷àñîïèñ ÍÏÓ Äðàãîìàíîâà. Âiñí. Êè¿âñüêîãî
óí-òó. Ñåðiÿ 1. Ôiçèêî-ìàòåìàòè÷íi íàóêè. — Êè¿â: ÍÏÓ ³ì. Ì.Ï. Äðàãîìàíîâà, 2013. —
¹ 12. — Ñ. 5—12.
Ïîñòóïèëà 06.12.13;
ïîñëå äîðàáîòêè 24.12.13
ÌÎÐÎÇÎÂ Äåíèñ Èâàíîâè÷, êàíä. ôèç.-ìàò. íàóê, äîêòîðàíò, ïðåïîäàâàòåëü êàôåäðû ìà-
òåìàòèêè Íàöèîíàëüíîãî óíèâåðñèòåòà «Êèåâî-Ìîãèëÿíñêàÿ àêàäåìèÿ».  2001 ã. îêîí÷èë
Êèåâñêèé íàöèîíàëüíûé óíèâåðñèòåò èì. Ò.Ã. Øåâ÷åíêî. Îáëàñòü íàó÷íûõ èññëåäîâàíèé —
òåîðèÿ ãðóïï, òåîðèÿ àâòîìàòîâ, p-àäè÷åñêèé àíàëèç.
Ä.È. Ìîðîçîâ
112 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 1
|