Growth of action graphs of finite automata

Authors

  • I.V. Bondarenko

DOI:

https://doi.org/10.15407/dopovidi2014.06.037

Keywords:

finite automata, graphs

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.

Downloads

References

Glushkov V. M. Uspekhi mat. nauk, 1961, 16, No. 5: 3–62 (in Russian).

Grigorchuk R. I., Nekrashevich V. V., Sushchansky V. I. Tr. Mat. in-ta im. V.A. Steklova, 2000. 231: 134–214 (in Russian).

Nekrashevych V. Self-similar groups. Providence, RI: AMS, 2005. https://doi.org/10.1090/surv/117

Sidki S. J. Math. Sci. (New York), 2000, 100, No. 1: 1925. – 1943.

Bondarenko I. Linear Algebra Appl., 2009, 431, No. 5–7: 495–510. https://doi.org/10.1016/j.laa.2009.02.038

Bondarenko I. Math. Ann., 2012, 354, No. 2: 765–785. https://doi.org/10.1007/s00208-011-0757-x

Downloads

Published

26.02.2025

How to Cite

Bondarenko, I. (2025). Growth of action graphs of finite automata . Reports of the National Academy of Sciences of Ukraine, (6), 37–41. https://doi.org/10.15407/dopovidi2014.06.037

Issue

No. 6 (2014): Reports of the National Academy of Sciences of Ukraine

Section

Information Science and Cybernetics

License

Copyright (c) 2025 Reports of the National Academy of Sciences of Ukraine

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.