Rationality of the growth functions of initial Mealy automata

1Bondarenko, IV, Skochko, VM
1Taras Shevchenko National University of Kyiv
Dopov. Nac. akad. nauk Ukr. 2019, 3:3-8
Section: Mathematics
Language: Ukrainian

The growth function γA(n) of an initial Mealy automaton A counts the number of states in a composition of automata An = Ao…o A (n times) after the minimization that are reachable from the initial state. We study the question when the generating function of the growth function is rational for the following automata classes: contracting with a nilpotent automaton group, bireversible, and polynomial ones.

Keywords: automaton group, growth function, Mealy automaton, polynomial automaton

1. Grigorchuk, R. I. (1983). On the Milnor problem of group growth. Dokl. AN SSSR, 271, No.1, pp. 30-33.
2. Bartholdi, L. & Reznykov, I. I. (2008). A Mealy machine with polynomial growth of irrational degree. Int. J. Algebra Comput., 18, No.1, pp. 59-82. doi: https://doi.org/10.1142/S0218196708004287
3. Bartholdi, L., Reznykov, I. I. & Sushchansky, V. I. (2006). The smallest Mealy automaton of intermediate growth. J. Algebra, 295, No. 2, pp. 387-414. doi: https://doi.org/10.1016/j.jalgebra.2004.08.040
4. Reznykov, I. I. & Sushchansky, V. I. (2006). On the 3state Mealy automata over an msymbol alphabet of growth order [nlog n/2log m]. J. Algebra, 304, No. 2, pp. 712-754. doi: https://doi.org/10.1016/j.jalgebra. 2006.03.039
5. Erschler, A. & Zheng, T. (2018). Growth of periodic Grigorchuk groups. arXiv:1802.09077v1 [math. GR] 25 Feb 2018.
6. Grigorchuk, R. I., Nekrashevych, V. V. & Sushchansky, V. I. (2000). Automata, dynamic systems and groups. Tr. mat. inst. im. V. A. Steklova, 231, pp. 134-214 (in Russian).
7. Nekrashevych, V. (2005). Selfsimilar groups. Mathematical Surveys and Monographs, Vol. 117. Providence, RI: AMS. doi: https://doi.org/10.1090/surv/117
8. Bondarenko, I. V., Bondarenko, N. V., Sidki, S. N. & Zapata, F. R. (2013). On the conjugacy problem for finitestate automorphisms of regular rooted trees. With an appendix by Raphaël M. Jungers. Groups Geom. Dyn., 7, Iss. 2, pp. 323-355. doi: https://doi.org/10.4171/GGD/184
9. Bondarenko, I., D’Angeli, D. & Rodaro, E. (2016). The lamplighter group ¢3 ¢ generated by a bireversible automaton. Commun. Algebra, 44, No. 12, pp. 5257-5268. doi: https://doi.org/10.1080/00927872.2016.1172602
10. Macedonska, O., Nekrashevych, V. & Sushchansky, V. (2000). Commensurators of groups and reversible automata. Dopov. Nac. acad. nauk Ukr., No. 12, pp. 36-39.
11. Glasner, Y. & Mozes, S. (2005). Automata and square complexes. Geometriae Dedicata, 111, Iss. 1, pp. 43-64. doi: https://doi.org/10.1007/s1071100418152
12. Sidki, S. (2000). Automorphisms of onerooted trees: growth, circuit structure, and acyclicity. J. Math. Sci., 100, No. 1, pp. 1925-1943. doi: https://doi.org/10.1007/BF02677504
13. Gillibert, P. (2018). An automaton group with undecidable order and Engel problems. J. Algebra, 497, pp. 363-392. doi: https://doi.org/10.1016/j.jalgebra.2017.11.049