Раціональність функцій росту ініціальних автоматів Мілі - Бондаренко, Є.В.; Скочко, В.М. (Доповіді НАН України, 2019)
Функція росту gA(n) ініціального автомата Мілі A обчислює кількість станів у композиції автоматів
A^n = Ao…o A (n разів) після мінімізації, які досягаються з ініціального стану. Досліджено, коли
генератриса функції росту є раціональною для таких класів ініціальних автоматів: стискуючих з нільпотентною автоматною групою, біреверсивних, поліноміальних. Функция роста gA(n) инициального автомата Мили A подcчитывает количество состояний в композиции
автоматов A^n = Ao…o A (n раз) после минимизации, достижимых с инициального состояния. Исследовано, когда генератриса функции роста является рациональной для следующих классов автоматов: стягивающих с нильпотентной автоматной группой, биреверсивных, полиномиальных. The growth function γA(n) of an initial Mealy automaton A counts the number of states in a composition of automata A^n = Ao…o A (n times) after the minimization that are reachable from the initial state. We study the question when the generating function of the growth function is rational for the following automata classes: contracting with a nilpotent automaton group, bireversible, and polynomial ones.