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...
Збережено в:
Дата: | 2018 |
---|---|
Автори: | , , , , , , |
Формат: | Стаття |
Мова: | English |
Опубліковано: |
Lugansk National Taras Shevchenko University
2018
|
Теми: | |
Онлайн доступ: | https://admjournal.luguniv.edu.ua/index.php/adm/article/view/805 |
Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
Назва журналу: | Algebra and Discrete Mathematics |
Репозитарії
Algebra and Discrete Mathematicsid |
oai:ojs.admjournal.luguniv.edu.ua:article-805 |
---|---|
record_format |
ojs |
spelling |
oai:ojs.admjournal.luguniv.edu.ua:article-8052018-03-22T09:32:59Z On classification of groups generated by \(3\)-state automata over a \(2\)-letter alphabet Bondarenko, Ievgen Grigorchuk, Rostislav Kravchenko, Rostyslav Muntyan, Yevgen Nekrashevych, Volodymyr Savchuk, Dmytro Sunic, Zoran automata groups, self-similar groups, branch groups 20E08 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\pm3)\), and a free product C2 ∗ C2 ∗ C2) to enticing (Basilica group and a few other iterated monodromy groups). Lugansk National Taras Shevchenko University 2018-03-22 Article Article Peer-reviewed Article application/pdf https://admjournal.luguniv.edu.ua/index.php/adm/article/view/805 Algebra and Discrete Mathematics; Vol 7, No 1 (2008) 2415-721X 1726-3255 en https://admjournal.luguniv.edu.ua/index.php/adm/article/view/805/335 Copyright (c) 2018 Algebra and Discrete Mathematics |
institution |
Algebra and Discrete Mathematics |
collection |
OJS |
language |
English |
topic |
automata groups self-similar groups branch groups 20E08 |
spellingShingle |
automata groups self-similar groups branch groups 20E08 Bondarenko, Ievgen Grigorchuk, Rostislav Kravchenko, Rostyslav Muntyan, Yevgen Nekrashevych, Volodymyr Savchuk, Dmytro Sunic, Zoran On classification of groups generated by \(3\)-state automata over a \(2\)-letter alphabet |
topic_facet |
automata groups self-similar groups branch groups 20E08 |
format |
Article |
author |
Bondarenko, Ievgen Grigorchuk, Rostislav Kravchenko, Rostyslav Muntyan, Yevgen Nekrashevych, Volodymyr Savchuk, Dmytro Sunic, Zoran |
author_facet |
Bondarenko, Ievgen Grigorchuk, Rostislav Kravchenko, Rostyslav Muntyan, Yevgen Nekrashevych, Volodymyr Savchuk, Dmytro Sunic, Zoran |
author_sort |
Bondarenko, Ievgen |
title |
On classification of groups generated by \(3\)-state automata over a \(2\)-letter alphabet |
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 |
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\pm3)\), and a free product C2 ∗ C2 ∗ C2) to enticing (Basilica group and a few other iterated monodromy groups). |
publisher |
Lugansk National Taras Shevchenko University |
publishDate |
2018 |
url |
https://admjournal.luguniv.edu.ua/index.php/adm/article/view/805 |
work_keys_str_mv |
AT bondarenkoievgen onclassificationofgroupsgeneratedby3stateautomataovera2letteralphabet AT grigorchukrostislav onclassificationofgroupsgeneratedby3stateautomataovera2letteralphabet AT kravchenkorostyslav onclassificationofgroupsgeneratedby3stateautomataovera2letteralphabet AT muntyanyevgen onclassificationofgroupsgeneratedby3stateautomataovera2letteralphabet AT nekrashevychvolodymyr onclassificationofgroupsgeneratedby3stateautomataovera2letteralphabet AT savchukdmytro onclassificationofgroupsgeneratedby3stateautomataovera2letteralphabet AT suniczoran onclassificationofgroupsgeneratedby3stateautomataovera2letteralphabet |
first_indexed |
2024-04-12T06:27:30Z |
last_indexed |
2024-04-12T06:27:30Z |
_version_ |
1796109254084526080 |