On classification of groups generated by 3-state automata over a 2-letter alphabet
We show that the class of groups generated by 3-state automata over a 2-letter alphabet has no more than 122 members. For each group in the class we provide some basic information, such as short relators, a few initial values of the growth function, a few initial values of the sizes of the quotients...
Saved in:
| Published in: | Algebra and Discrete Mathematics |
|---|---|
| Date: | 2008 |
| Main Authors: | , , , , , , |
| Format: | Article |
| Language: | English |
| Published: |
Інститут прикладної математики і механіки НАН України
2008
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/152389 |
| 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: | On classification of groups generated by 3-state automata over a 2-letter alphabet / I. Bondarenko, R. Grigorchuk, R. Kravchenko, Y. Muntyan, V. Nekrashevych, D. Savchuk, Z. Sunic // Algebra and Discrete Mathematics. — 2008. — Vol. 7, № 1. — С. 1–163. — Бібліогр.: 50 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-152389 |
|---|---|
| record_format |
dspace |
| spelling |
Bondarenko, I. Grigorchuk, R. Kravchenko, R. Muntyan, Y. Nekrashevych, V. Savchuk, D. Sunic, Z. 2019-06-10T18:55:07Z 2019-06-10T18:55:07Z 2008 On classification of groups generated by 3-state automata over a 2-letter alphabet / I. Bondarenko, R. Grigorchuk, R. Kravchenko, Y. Muntyan, V. Nekrashevych, D. Savchuk, Z. Sunic // Algebra and Discrete Mathematics. — 2008. — Vol. 7, № 1. — С. 1–163. — Бібліогр.: 50 назв. — англ. 1726-3255 2000 Mathematics Subject Classification:20E08. https://nasplib.isofts.kiev.ua/handle/123456789/152389 We show that the class of groups generated by 3-state automata over a 2-letter alphabet has no more than 122 members. For each group in the class we provide some basic information, such as short relators, a few initial values of the growth function, a few initial values of the sizes of the quotients by level stabilizers (congruence quotients), and hystogram of the spectrum of the adjacency operator of the Schreier graph of the action on level 9. In most cases we provide more information, such as whether the group is contracting, self-replicating, or (weakly) branch group, and exhibit elements of infinite order (we show that no group in the class is an infinite torsion group). A GAP package, written by Muntyan and Savchuk, was used to perform some necessary calculations. For some of the examples, we establish that they are (virtually) iterated monodromy groups of post-critically finite rational functions, in which cases we describe the functions and the limit spaces. There are exactly 6 finite groups in the class (of order no greater than 16), two free abelian groups (of rank 1 and 2), and only one free nonabelian group (of rank 3). The other examples in the class range from familiar (some virtually abelian groups, lamplighter group, Baumslag-Solitar groups BS(1±3), and a free product C2 ∗ C2 ∗ C2) to enticing (Basilica group and a few other iterated monodromy groups). All authors were partially supported by at least one of the NSF grants DMS-308985,DMS-456185, DMS-600975, and DMS-605019. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics On classification of groups generated by 3-state automata over a 2-letter alphabet Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
On classification of groups generated by 3-state automata over a 2-letter alphabet |
| spellingShingle |
On classification of groups generated by 3-state automata over a 2-letter alphabet Bondarenko, I. Grigorchuk, R. Kravchenko, R. Muntyan, Y. Nekrashevych, V. Savchuk, D. Sunic, Z. |
| title_short |
On classification of groups generated by 3-state automata over a 2-letter alphabet |
| title_full |
On classification of groups generated by 3-state automata over a 2-letter alphabet |
| title_fullStr |
On classification of groups generated by 3-state automata over a 2-letter alphabet |
| title_full_unstemmed |
On classification of groups generated by 3-state automata over a 2-letter alphabet |
| title_sort |
on classification of groups generated by 3-state automata over a 2-letter alphabet |
| author |
Bondarenko, I. Grigorchuk, R. Kravchenko, R. Muntyan, Y. Nekrashevych, V. Savchuk, D. Sunic, Z. |
| author_facet |
Bondarenko, I. Grigorchuk, R. Kravchenko, R. Muntyan, Y. Nekrashevych, V. Savchuk, D. Sunic, Z. |
| publishDate |
2008 |
| language |
English |
| container_title |
Algebra and Discrete Mathematics |
| publisher |
Інститут прикладної математики і механіки НАН України |
| format |
Article |
| description |
We show that the class of groups generated by 3-state automata over a 2-letter alphabet has no more than 122 members. For each group in the class we provide some basic information, such as short relators, a few initial values of the growth function, a few initial values of the sizes of the quotients by level stabilizers (congruence quotients), and hystogram of the spectrum of the adjacency operator of the Schreier graph of the action on level 9. In most cases we provide more information, such as whether the group is contracting, self-replicating, or (weakly) branch group, and exhibit elements of infinite order (we show that no group in the class is an infinite torsion group). A GAP package, written by Muntyan and Savchuk, was used to perform some necessary calculations. For some of the examples, we establish that they are (virtually) iterated monodromy groups of post-critically finite rational functions, in which cases we describe the functions and the limit spaces. There are exactly 6 finite groups in the class (of order no greater than 16), two free abelian groups (of rank 1 and 2), and only one free nonabelian group (of rank 3). The other examples in the class range from familiar (some virtually abelian groups, lamplighter group, Baumslag-Solitar groups BS(1±3), and a free product C2 ∗ C2 ∗ C2) to enticing (Basilica group and a few other iterated monodromy groups).
|
| issn |
1726-3255 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/152389 |
| citation_txt |
On classification of groups generated by 3-state automata over a 2-letter alphabet / I. Bondarenko, R. Grigorchuk, R. Kravchenko, Y. Muntyan, V. Nekrashevych, D. Savchuk, Z. Sunic // Algebra and Discrete Mathematics. — 2008. — Vol. 7, № 1. — С. 1–163. — Бібліогр.: 50 назв. — англ. |
| work_keys_str_mv |
AT bondarenkoi onclassificationofgroupsgeneratedby3stateautomataovera2letteralphabet AT grigorchukr onclassificationofgroupsgeneratedby3stateautomataovera2letteralphabet AT kravchenkor onclassificationofgroupsgeneratedby3stateautomataovera2letteralphabet AT muntyany onclassificationofgroupsgeneratedby3stateautomataovera2letteralphabet AT nekrashevychv onclassificationofgroupsgeneratedby3stateautomataovera2letteralphabet AT savchukd onclassificationofgroupsgeneratedby3stateautomataovera2letteralphabet AT sunicz onclassificationofgroupsgeneratedby3stateautomataovera2letteralphabet |
| first_indexed |
2025-12-07T15:39:54Z |
| last_indexed |
2025-12-07T15:39:54Z |
| _version_ |
1850864560583475200 |