Р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##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2025 Доповіді Національної академії наук України

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