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
Автори: Bondarenko, Ievgen, Grigorchuk, Rostislav, Kravchenko, Rostyslav, Muntyan, Yevgen, Nekrashevych, Volodymyr, Savchuk, Dmytro, Sunic, Zoran
Формат: Стаття
Мова: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 Mathematics
id 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