Р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

Номер

Розділ

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