Title | Growth of action graphs of finite automata |
Publication Type | Journal Article |
Year of Publication | 2014 |
Authors | Bondarenko, IV |
Abbreviated Key Title | Dopov. Nac. akad. nauk Ukr. |
DOI | 10.15407/dopovidi2014.06.037 |
Issue | 6 |
Section | Information Science and Cybernetics |
Pagination | 37-41 |
Date Published | 6/2014 |
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 |
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