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

ЗаголовокРiст графiв дiї скiнченних автоматiв
Тип публікаціїJournal Article
Рік публікації2014
АвториБондаренко, ЄВ
Abbreviated Key TitleDopov. Nac. akad. nauk Ukr.
DOI10.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в