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

A.P. Krenevych (Taras Shevchenko National University of Kyiv),
A.S. Oliynyk (Taras Shevchenko National University of Kyiv),


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.


finite automaton; p-automaton; free group

MSC 2020

20E08; 20E22; 20E26

Full Text:



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




  • There are currently no refbacks.

Copyright (c) 2023 A.P. Krenevych, A.S. Oliynyk

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Registered in


ISSN (Online): 2664-5009
ISSN (Print): 2664-4991