Rationality of the growth functions of initial Mealy automata
DOI:
https://doi.org/10.15407/dopovidi2019.03.003Keywords:
automaton group, growth function, Mealy automaton, polynomial automatonAbstract
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.
Downloads
References
Grigorchuk, R. I. (1983). On the Milnor problem of group growth. Dokl. AN SSSR, 271, No.1, pp. 30-33.
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
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
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
Erschler, A. & Zheng, T. (2018). Growth of periodic Grigorchuk groups. arXiv:1802.09077v1 [math. GR] 25 Feb 2018.
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).
Nekrashevych, V. (2005). Selfsimilar groups. Mathematical Surveys and Monographs, Vol. 117. Providence, RI: AMS. doi: https://doi.org/10.1090/surv/117
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
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
Macedonska, O., Nekrashevych, V. & Sushchansky, V. (2000). Commensurators of groups and reversible automata. Dopov. Nac. acad. nauk Ukr., No. 12, pp. 36-39.
Glasner, Y. & Mozes, S. (2005). Automata and square complexes. Geometriae Dedicata, 111, Iss. 1, pp. 43-64. doi: https://doi.org/10.1007/s1071100418152
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
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
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Reports of the National Academy of Sciences of Ukraine
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
