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...

Повний опис

Збережено в:

Бібліографічні деталі
Видавець:	Інститут прикладної математики і механіки НАН України
Дата:	2008
Автори:	Bondarenko, I., Grigorchuk, R., Kravchenko, R., Muntyan, Y., Nekrashevych, V., Savchuk, D., Sunic, Z.
Формат:	Стаття
Мова:	English
Опубліковано:	Інститут прикладної математики і механіки НАН України 2008
Назва видання:	Algebra and Discrete Mathematics
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/152389
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Цитувати:	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 назв. — англ.

Репозиторії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-152389
record_format	dspace
spelling	irk-123456789-1523892019-06-11T01:25:42Z 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. 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). 2008 Article 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. http://dspace.nbuv.gov.ua/handle/123456789/152389 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	English
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).
format	Article
author	Bondarenko, I. Grigorchuk, R. Kravchenko, R. Muntyan, Y. Nekrashevych, V. Savchuk, D. Sunic, Z.
spellingShingle	Bondarenko, I. Grigorchuk, R. Kravchenko, R. Muntyan, Y. Nekrashevych, V. Savchuk, D. Sunic, Z. On classification of groups generated by 3-state automata over a 2-letter alphabet Algebra and Discrete Mathematics
author_facet	Bondarenko, I. Grigorchuk, R. Kravchenko, R. Muntyan, Y. Nekrashevych, V. Savchuk, D. Sunic, Z.
author_sort	Bondarenko, I.
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
publisher	Інститут прикладної математики і механіки НАН України
publishDate	2008
url	http://dspace.nbuv.gov.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 назв. — англ.
series	Algebra and Discrete Mathematics
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	2023-05-20T17:38:16Z
last_indexed	2023-05-20T17:38:16Z
_version_	1796153744703881216

On classification of groups generated by 3-state automata over a 2-letter alphabet

Репозиторії

Схожі ресурси