Групи автоматів без циклу з виходом
Доведено, що клас груп, породжених автоматами над скiнченним алфавiтом, є замкненим вiдносно прямих степенiв та деяких вiнцевих добуткiв. Отримано точну оцiнку порядкiв груп автоматiв без циклу з виходом над бiнарним алфавiтом....
Gespeichert in:
| Datum: | 2010 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Видавничий дім "Академперіодика" НАН України
2010
|
| Schriftenreihe: | Доповіді НАН України |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/19584 |
| 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: | Групи автоматів без циклу з виходом / А.В. Руссєв // Доп. НАН України. — 2010. — № 2. — С. 28-32. — Бібліогр.: 7 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-19584 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-195842011-05-12T12:04:24Z Групи автоматів без циклу з виходом Руссєв, А.В. Математика Доведено, що клас груп, породжених автоматами над скiнченним алфавiтом, є замкненим вiдносно прямих степенiв та деяких вiнцевих добуткiв. Отримано точну оцiнку порядкiв груп автоматiв без циклу з виходом над бiнарним алфавiтом. It is proved that the class of groups generated by automata over a finite alphabet is closed with respect to direct powers and some wreath products. Orders of groups of automata without cycles with exit over a binary alphabet are precisely estimated. 2010 Article Групи автоматів без циклу з виходом / А.В. Руссєв // Доп. НАН України. — 2010. — № 2. — С. 28-32. — Бібліогр.: 7 назв. — укр. 1025-6415 http://dspace.nbuv.gov.ua/handle/123456789/19584 512.54 uk Доповіді НАН України Видавничий дім "Академперіодика" НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Математика Математика |
| spellingShingle |
Математика Математика Руссєв, А.В. Групи автоматів без циклу з виходом Доповіді НАН України |
| description |
Доведено, що клас груп, породжених автоматами над ск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 |
2010 |
| topic_facet |
Математика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/19584 |
| citation_txt |
Групи автоматів без циклу з виходом / А.В. Руссєв // Доп. НАН України. — 2010. — № 2. — С. 28-32. — Бібліогр.: 7 назв. — укр. |
| series |
Доповіді НАН України |
| work_keys_str_mv |
AT russêvav grupiavtomatívbezcikluzvihodom |
| first_indexed |
2025-07-02T20:24:55Z |
| last_indexed |
2025-07-02T20:24:55Z |
| _version_ |
1836568171631345664 |
| fulltext |
УДК 512.54
© 2010
А.В. Руссєв
Групи автоматiв без циклу з виходом
(Представлено членом-кореспондентом НАН України Ю.С. Самойленком)
Доведено, що клас груп, породжених автоматами над скiнченним алфавiтом, є замкне-
ним вiдносно прямих степенiв та деяких вiнцевих добуткiв. Отримано точну оцiнку
порядкiв груп автоматiв без циклу з виходом над бiнарним алфавiтом.
1. Клас груп, породжених автоматами-трансляторами над скiнченними алфавiтами, мi-
стить багато груп з цiкавими та несподiваними властивостями. Серед них у першу чергу
видiляються групи бернсайдового типу (скiнченно породженi нескiнченнi перiодичнi групи)
та групи промiжного росту (див. [1, 2] та наведену в них бiблiогр.). Ряд робiт присвячено,
зокрема, вивченню реалiзацiй тих чи iнших груп як груп, породжених автоматами. Так,
в [3] дослiджувались абелевi групи, породженi скiнченними автоматами над бiнарним ал-
фавiтом, а в [4] побудовано скiнченнi автомати, що породжують деякi скiнченно заданi
розв’язнi групи. Вiдзначимо також приклади скiнченних автоматiв, що породжують вiль-
ну групу рангу 2 [2] та вiльнi добутки скiнченної кiлькостi циклiчних груп порядку 2 [5].
Природно виникають такi питання. Якi групи реалiзуються як групи, породженi автоматом
над заданим алфавiтом? Яка найменша можлива кiлькiсть станiв у такому автоматi? За-
значимо, що задача повної класифiкацiї груп, породжених автоматами навiть над бiнарним
алфавiтом, є надзвичайно складною. Так, повну класифiкацiю груп, породжених двостано-
вими автоматами над бiнарним алфавiтом, наведено в [1], а результатам, отриманим при
спробi класифiкувати групи, породженi тристановими автоматами над цим же алфавiтом,
присвячено роботу [6].
У данiй роботi встановлюється замкненiсть класу груп, породжених автоматами, вiднос-
но операцiї вiнцевого добутку, активний множних якого є групою пiдстановок на алфавiтi,
та операцiї пiднесення до прямого степеня. У класi груп, породжених автоматами, природно
видiлити пiдклас груп, породжених автоматами без циклу з виходом. Цей пiдклас мiстить
лише скiнченнi групи [7]. Для класу груп, породжених автоматами без циклу з виходом
над бiнарним алфавiтом, знайдена точна оцiнка потужностi групи, як функцiя кiлькостi
станiв автомату.
2. Нехай X — деяка скiнченна непорожня множина, яку будемо називати алфавiтом,
а її елементи — лiтерами.
Означення 1. Автоматом над алфавiтом X називається набiр A = 〈X,Q,ϕ, λ〉, де Q —
множина внутрiшнiх станiв автомата, ϕ : Q×X → Q — функцiя переходiв, λ : Q×X → X —
функцiя виходiв.
Автомат A = 〈X,Q,ϕ, λ〉 можна зображати у виглядi помiченого орiєнтованого гра-
фа, вершинами якого є стани автомата. Помiтка в кожнiй вершинi q ∈ Q визначає фун-
кцiю виходiв λ(q, ·). Функцiя переходiв зображується за допомогою ребер. Для кожної пари
(q, x) ∈ Q × X граф мiстить ребро з помiткою x, що виходить з вершини q i закiнчується
у вершинi ϕ(q, x).
Розглянемо автомат A = 〈X,Q,ϕ, λ〉.
28 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2010, №2
Означення 2. Циклом в автоматi A називається послiдовнiсть попарно рiзних станiв
q1, q2, . . . , qn ∈ Q, n > 1, для яких iснує послiдовнiсть лiтер x1, x2, . . . , xn ∈ X така, що
ϕ(qi, xi) = qi+1 для 1 6 i < n та ϕ(qn, xn) = q1. При цьому число n називається довжиною
циклу.
Означення 3. Цикл q1, q2, . . . , qn ∈ Q в автоматi A називається циклом з виходом, якщо
iснує i, 1 6 i 6 n, та x ∈ X такi, що ϕ(qi, x) 6= {q1, q2, . . . , qn}. В iншому випадку кажуть,
що цей цикл є циклом без виходу.
Означення 4. Стан q ∈ Q називається циклiчним, якщо вiн належить деякому циклу
в автоматi A.
Розглянемо множину X∗ =
⋃
n>1
Xn
⋃
{Λ} усiх слiв над алфавiтом X; символом Λ буде-
мо позначати порожнє слово. Функцiї переходiв та виходiв автомата A продовжуються на
множину Q × X∗ за правилом: для q ∈ Q, w ∈ X∗ та x ∈ X
ϕ(q, wx) = ϕ(ϕ(q, w), x), ϕ(q,Λ) = q,
λ(q, wx) = λ(q, w)λ(ϕ(q, w), x), λ(q,Λ) = Λ.
Кожному стану q ∈ Q вiдповiдає вiдображення fq = λ(q, ·) : X∗ → X∗.
Далi будемо розглядати лише такi автомати, що для кожного стану q ∈ Q вiдобра-
ження fq є бiєкцiєю.
Означення 5 [2, роздiл 1.5.4]. Групою, породженою автоматом A, називається група,
породжена перетвореннями fq, де q пробiгає всi стани автомата A.
Згiдно з означенням, група, породжена автоматом, є групою пiдстановок на множинi X∗.
Теорема 1 [7, теорема 2]. Група, породжена скiнченним автоматом, який не мiстить
циклу з виходом, скiнченна.
Символом S(X) будемо позначати симетричну групу пiдстановок на множинi X.
3. Клас груп, породжених автоматами над алфавiтом X, є замкненим вiдносно певних
теоретико-групових операцiй. А саме, має мiсце такий результат про замкненiсть вiдносно
вiнцевого множення:
Теорема 2. Нехай G є групою, породженою (скiнченним, без циклу з виходом) автома-
том A = 〈X,Q,ϕ, λ〉 над алфавiтом X, P < S(X) та для кожного q ∈ Q пiдстановка λ(q, ·)
належить групi P . Тодi група P ≀G також є групою, породженою (скiнченним, без циклу
з виходом) автоматом над алфавiтом X.
Також клас груп, породжених автоматами над алфавiтом X, є замкненим вiдносно пiд-
несення до прямого степеня:
Теорема 3. Нехай G є групою, породженою (скiнченним, без циклу з виходом) автома-
том над алфавiтом X. Тодi група
n⊕
i=1
G для кожного натурального n також є групою,
породженою (скiнченним, без циклу з виходом) автоматом над алфавiтом X.
У загальному випадку з того, що G1 i G2 породжуються автоматами над алфавiтом X,
не випливає, що G1 × G2 породжується автоматом над тим же алфавiтом. Наприклад,
група Z⊕Z2 не породжується автоматом над бiнарним алфавiтом [3, твердження 3.4], хоча
групи Z та Z2 породжуються.
Якщо не накладати обмежень на алфавiт, то легко побудувати автомат, що буде поро-
джувати групу G1 × G2. Досить розглянути алфавiт вдвiчi бiльшої потужностi i автомат
утворити з двох диз’юнктних частин, одна з яких буде дiяти як автомат для G1 на пер-
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2010, №2 29
шiй половинi алфавiту i тотожно на другiй половинi, а iнша, навпаки, тотожно на першiй
половинi i як автомат для G2 на другiй.
З теорем 2 i 3 отримуємо такий результат про реалiзацiю груп як груп, породжених
автоматами:
Наслiдок 1. Нехай група G породжується (скiнченним, без циклу з виходом) автома-
том над бiнарним алфавiтом. Тодi групи Z2 ≀G та
n⊕
i=1
G породжуються (скiнченним, без
циклу з виходом) автоматом над бiнарним алфавiтом.
Зауважимо, що доведення теорем 2 i 3 є конструктивними, а тому, як тiльки вiдома
конструкцiя автомата, що породжує групу G, вiдразу можна вказати автомати, якi б по-
роджували групи Z2 ≀ G та
n⊕
i=1
G.
4. Надалi вважатимемо, що X = {0, 1}. Знайдемо точну оцiнку порядку групи, пород-
женої n-становим (n ∈ N) автоматом без циклiв з виходом.
Нехай автомат A = 〈X,Q,ϕ, λ〉 без циклу з виходом породжує групу G. Множину твiр-
них групи G ототожнюємо з множиною станiв автомата A. Легко бачити, що квадрати
циклiчних станiв автомата A дiють тотожно. Тому кожний циклiчний стан A буде обер-
неним до себе. Крiм того, усi цi стани попарно комутують. Будемо говорити, що множина
циклiчних станiв автомата A є залежною, якщо серед них є стан, що дiє тотожно або є до-
бутком деяких iнших циклiчних станiв.
Лема 1. Нехай множина циклiчних станiв автомата A є залежною. Якщо |Q| = n,
то має мiсце нерiвнiсть |G| 6 22
n−1−1.
Доведення. Доводимо iндукцiєю за кiлькiстю станiв n. База iндукцiї n = 1. Єдиний
стан такого автомата буде циклiчним. Оскiльки множина циклiчних станiв є залежною, то
цей стан є тотожним i група G є одиничною.
Крок iндукцiї. Розiб’ємо множину станiв автомата A на двi частини Q = Q1
⊔
Q2, де
Q1 = imϕ — множина станiв, в якi можна прийти по ребру з деякого iншого, а Q2 = Q\Q1 —
множина станiв, в якi не входять ребра. Якщо Q2 порожня, то автомат A мiстить лише
циклiчнi стани. Вони мають порядок не вище за 2 та комутують. Враховуючи залежнiсть
множини циклiчних станiв, маємо
|G| 6 2n−1
6 22
n−1−1.
Нехай тепер Q2 не порожня. Позначимо через G̃ групу, породжену автоматом з множи-
ною станiв Q1. Усi циклiчнi стани A належать множинi Q1. Тому за припущенням iндукцiї
маємо |G̃| 6 22
n−2−1, оскiльки |Q1| 6 n − 1. Група G є пiдгрупою Z2 ≀ G̃, а тому
|G| 6 |Z2 ≀ G̃| = 2 · |G̃|2 6 2 ·
(
22
n−2−1
)2
= 22
n−1−1.
Твердження леми випливає з принципу математичної iндукцiї.
Лема 2. Нехай слово w, що складене з твiрних G, має непарну довжину та дорiвнює 1
у групi G. Тодi множина циклiчних станiв A є залежною.
Доведення. Слово w можна вважати станом автомата (A
⋃
A−1)|w|. Цей стан є одини-
чним. Тому довiльний стан w також одиничний. Розглянемо стан w̃ = w|u, де u — деяке
слово довжини |Q|, в який перейде автомат зi стану w, одержавши слово u. Кожний стан
автомата A
⋃
A−1 з добутку w, одержавши |Q| лiтер, перейде в циклiчний стан автомата
30 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2010, №2
Рис. 1
A
⋃
A−1. Але множини циклiчних станiв автоматiв A−1 та A збiгаються. Отже, стан w̃ є до-
бутком |w| циклiчних станiв автомата A i його можна скоротити до вигляду, де кожний ци-
клiчний стан зустрiчається не бiльше одного разу. Одержаний добуток буде мiстити непарну
кiлькiсть циклiчних станiв автомата A. Звiдси випливає залежнiсть циклiчних станiв A.
Лема 3. Нехай слова w1, w2 складенi з твiрних G та w1 = w2 у групi G. Якщо множина
циклiчних станiв A є незалежною, то довжини слiв w1 та w2 мають однакову парнiсть.
Доведення. Розглянемо слово w = w1w
−1
2
. Якщо воно має непарну довжину, то за
лемою 2 множина циклiчних станiв A є залежною.
Нехай множина циклiчних станiв автомата A є незалежною. Елемент групи G будемо
називати парним, якщо вiн є добутком парної кiлькостi твiрних групи. Лема 3 обгрунтовує
коректнiсть введення поняття парностi на елементах G. Нехай g ∈ G — деякий твiрний гру-
пи G. Вiдображення групи G в себе, задане правилом x 7→ gx, є iн’єктивним та переводить
непарнi елементи в парнi i навпаки. Тому кiлькiсть парних i непарних елементiв однакова.
Лема 4. Нехай множина циклiчних станiв автомата A є незалежною. Якщо |Q| = n,
то має мiсце нерiвнiсть |G| 6 22
n−1
.
Доведення. Доводимо iндукцiєю за кiлькiстю станiв n. База iндукцiї n = 1. Єдиний
стан такого автомата буде циклiчним. Оскiльки множина циклiчних станiв є незалежною,
то цей стан має порядок 2 та |G| = 2.
Крок iндукцiї. Розiб’ємо множину станiв автомата A на двi частини Q = Q1
⊔
Q2, де
Q1 = imϕ — множина станiв, в якi можна прийти по ребру з деякого iншого, а Q2 = Q\Q1 —
множина станiв, в якi не входять ребра. Якщо Q2 порожня, то автомат A мiстить лише
циклiчнi стани, що мають порядок 2 та комутують. Звiдси
|G| 6 2n 6 22
n−1
.
Нехай тепер Q2 не порожня. Позначимо через G̃ групу, породжену автоматом з множи-
ною станiв Q1. За припущенням iндукцiї маємо |G̃| 6 22
n−2
, оскiльки |Q1| 6 n− 1. Група G
є пiдгрупою Z2 ≀ G̃. Елементи групи G мають вигляд [π; g1, g2], де π ∈ Z2, g1, g2 ∈ G̃ одна-
кової парностi. Тому
|G| 6
1
2
· |Z2 ≀ G̃| =
1
2
· 2 · |G̃|2 6
(
22
n−2)2
= 22
n−1
.
Твердження леми випливає з принципу математичної iндукцiї.
Теорема 4. Нехай автомат A = 〈X,Q,ϕ, λ〉 без циклу з виходом породжує групу G.
Якщо |Q| = n, то |G| 6 22
n−1
.
Доведення. Твердження теореми є наслiдком лем 1 та 4.
Зауважимо, що оцiнка в теоремi 4 є точною. Як приклад можна розглянути автомат,
зображений на рис. 1. Вiн має n+ 1 стан i породжує групу G ≃ Z2 ⊕ ≀ni=1Z2 порядку 22
n
.
1. Григорчук Р.И., Некрашевич В. В., Сущанский В.И. Автоматы, динамические системы и группы //
Тр. Мат. ин-та им. В. А. Стеклова. – 2000. – 231. – С. 134–214.
2. Nekrashevych V.V. Self-similar groups. – Providence, RI: Amer. Math. Soc., 2005. – 231 p.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2010, №2 31
3. Nekrashevych V., Sidki S. Automorphisms of the binary tree: state closed subgroups and dynamics of
1/2-endomorphisms // Groups: Topological, Combinatorial and Arithmetic Aspects / Ed. T.W. Müller. –
Cambridge: Cambridge Univ. Press, 2004. – 311. – P. 375–404.
4. Bartholdi L., Šunić Z. Some solvable automaton groups // Contemp. Math. – 2006. – 394. – P. 11–29.
5. Savchuk D., Vorobets Ya. Automata generating free products of groups of order 2, 2008. – (available at
http://arxiv.org/abs/0806.4801).
6. Bondarenko I., Grigorchuk R., Kravchenko R. et al. Classification of groups generated by 3-state automata
over a 2-letter alphabet // Algebra and Discrete Mathematics. – 2008. – 1. – P. 1–163.
7. Руссєв А. В. Про скiнченнi та абелевi групи, породженi скiнченними автоматами // Мат. студiї. –
2005. – 24, № 2. – С. 139–146.
Надiйшло до редакцiї 15.05.2009Київський нацiональний унiверситет
iм. Тараса Шевченка
A.V. Russyev
Groups of automata without cycles with exit
It is proved that the class of groups generated by automata over a finite alphabet is closed with
respect to direct powers and some wreath products. Orders of groups of automata without cycles
with exit over a binary alphabet are precisely estimated.
32 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2010, №2
|