Rationality of the growth functions of initial Mealy automata

TitleRationality of the growth functions of initial Mealy automata
Publication TypeJournal Article
Year of Publication2019
AuthorsBondarenko, IV, Skochko, VM
Abbreviated Key TitleDopov. Nac. akad. nauk Ukr.
DOI10.15407/dopovidi2019.03.003
Issue3
SectionMathematics
Pagination3-8
Date Published03/2019
LanguageUkrainian
Abstract

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.

Keywordsautomaton group, growth function, Mealy automaton, polynomial automaton
References: 

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