Growth of action graphs of finite automata

1Bondarenko, IV
1Taras Shevchenko National University of Kyiv
Dopov. Nac. akad. nauk Ukr. 2014, 6:37-41
https://doi.org/10.15407/dopovidi2014.06.037
Section: Information Science and Cybernetics
Language: Ukrainian
Abstract: 

We consider the action graphs Γn(A) and Γ(A) for bounded and polynomial automata A, which model the action of automata on words of length n and infinite words, respectively. A method for finding the orbital contracting coefficient and the growth of the diameters of graphs Γn(A) for a bounded automaton is established. We give estimates on the growth degrees of the graphs Γ(A) for bounded automata. It is proved that the graphs Γ(A) for non-deterministic polynomial automata have subexponential growth.

Keywords: finite automata, graphs
References: 

1. Glushkov V. M. Uspekhi mat. nauk, 1961, 16, No. 5: 3–62 (in Russian).
2. Grigorchuk R. I., Nekrashevich V. V., Sushchansky V. I. Tr. Mat. in-ta im. V.A. Steklova, 2000. 231: 134–214 (in Russian).
3. Nekrashevych V. Self-similar groups. Providence, RI: AMS, 2005. https://doi.org/10.1090/surv/117
4. Sidki S. J. Math. Sci. (New York), 2000, 100, No. 1: 1925. – 1943.
5. Bondarenko I. Linear Algebra Appl., 2009, 431, No. 5–7: 495–510. https://doi.org/10.1016/j.laa.2009.02.038
6. Bondarenko I. Math. Ann., 2012, 354, No. 2: 765–785. https://doi.org/10.1007/s00208-011-0757-x