Рiст графiв дiї скiнченних автоматiв

Автор(и)

  • Є.В. Бондаренко

DOI:

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

Ключові слова:

Рiст графiв дiї скiнченних автоматiв

Анотація

Розглядаються графи дiї Γn(A) і Γ∞(A) для обмежених i полiномiальних автоматiв A, якi моделюють дiю автоматiв на словах довжиною n i нескiнченних словах вiдповiдно. Встановлено метод знаходження орбiтального коефiцiєнта стиску обмежених автоматiв, росту дiаметрiв графiвΓn(A) для обмежених автоматiв, наведено оцiнки на степiнь полiномiального росту графiв Γ∞(A). Доведено, що графи Γ∞(A) для недетермiнованих полiномiальних автоматiв мають субекспоненцiйний рiст.

Завантаження

Посилання

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

##submission.downloads##

Опубліковано

26.02.2025

Як цитувати

Бондаренко, Є. (2025). Рiст графiв дiї скiнченних автоматiв . Доповіді Національної академії наук України, (6), 37–41. https://doi.org/10.15407/dopovidi2014.06.037

Номер

№ 6 (2014): Доповіді Національної академії наук України

Розділ

Інформатика та кібернетика

Ліцензія

Авторське право (c) 2025 Доповіді Національної академії наук України

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial 4.0 International License.