Free groups defined by finite $$$p$$$-automata

A.P. Krenevych; A.S. Oliynyk

doi:10.15421/242314

Free groups defined by finite $$$p$$$-automata

A.P. Krenevych (Taras Shevchenko National University of Kyiv), https://orcid.org/0000-0002-0720-786X
A.S. Oliynyk (Taras Shevchenko National University of Kyiv), https://orcid.org/0000-0003-0940-7731

Abstract

For every odd prime $$$p$$$ we construct two $$$p$$$-automata with 14 inner states and prove that the group generated by 2 automaton permutations defined at their states is a free group of rank 2.

Keywords

finite automaton; p-automaton; free group

MSC 2020

20E08; 20E22; 20E26

Full Text:

PDF

References

Aleshin S.V. "A free group of finite automata", Vestnik Moskov. Univ. Ser. I Mat. Mekh., 1983; 4: pp. 12-14.

Bondarenko I., Kivva B. "Automaton groups and complete square complexes", Groups Geom. Dyn., 2022; 16: pp. 305-332. doi:10.4171/ggd/649

Brunner A.M., Sidki S. "The generation of $$${\rm GL}(n,\mathbf Z)$$$ by finite state automata", Internat. J. Algebra Comput., 1998; 8: pp. 127-139. doi:10.1142/S0218196798000077

Grigorchuk R.I., Nekrashevich V.V., Sushchanskii V.I. "Automata, dynamical systems, and groups", Dynamical systems, automata, and infinite groups, Transl. from the Russian. MAIK Nauka/Interperiodica Publishing, 2000; pp. 128-203.

Lyndon R.C., Schupp P.E. Combinatorial group theory, Springer-Verlag, 1977.

Oliynyk A. "Free products of finite groups and groups of finitely automatic permutations", Proc. Steklov Institute of Mathematics, 2000; 231: pp. 323-331.

Oliynyk A. "Finite state wreath powers of transformation semigroups", Semigroup Forum, 2011; 82: pp. 423-436. doi:10.1007/s00233-011-9292-z

Oliynyk A., Prokhorchuk V. "On exponentiation, $$$p$$$-automata and HNN extensions of free abelian groups", Algebra Discrete Math., 2023; 35: pp. 180-190. doi:10.12958/adm2132

Oliynyk A., Prokhorchuk V. "On a finite state representation of $$$GL(n,\mathbb{Z})$$$", Algebra Discrete Math., 2023; 36: pp. 74-84. doi:10.12958/adm2158

Steinberg B., Vorobets M., Vorobets Y. "Automata over a binary alphabet generating free groups of even rank", Internat. J. Algebra Comput., 2011; 21: pp. 329-354. doi:10.1142/S0218196711006194

Vorobets M., Vorobets Y. "On a free group of transformations defined by an automaton", Geom. Dedicata., 2007; 124: pp. 237-249. doi:10.1007/s10711-006-9060-5

Vorobets M., Vorobets Y. "On a series of finite automata defining free transformation groups", Groups Geom. Dyn., 2010; 4: pp. 377-405. doi:10.4171/GGD/87