Заголовок | Рiст графiв дiї скiнченних автоматiв |
Тип публікації | Journal Article |
Рік публікації | 2014 |
Автори | Бондаренко, ЄВ |
Abbreviated Key Title | Dopov. Nac. akad. nauk Ukr. |
DOI | 10.15407/dopovidi2014.06.037 |
Номер видання | 6 |
Розділ | Інформатика та кібернетика |
Нумерація сторінок | :37-41 |
Дата публікації | 06/2014 |
Мова | Українська |
Анотація | Розглядаються графи д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ст. |
Ключові слова | Рiст графiв дiї скiнченних автоматiв |