Growth of action graphs of finite automata

TitleGrowth of action graphs of finite automata
Publication TypeJournal Article
Year of Publication2014
AuthorsBondarenko, IV
Abbreviated Key TitleDopov. Nac. akad. nauk Ukr.
SectionInformation Science and Cybernetics
Date Published6/2014

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.

Keywordsfinite 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.
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.
6. Bondarenko I. Math. Ann., 2012, 354, No. 2: 765–785.