Раціональність функцій росту ініціальних автоматів Мілі

• Опубліковано в: : Доповіді НАН України
• Дата: 2019
• Автори: Бондаренко, Є.В., Скочко, В.М.
• Формат: Стаття
• Мова: Українська
• Опубліковано: Видавничий дім "Академперіодика" НАН України 2019
• Теми: Математика
• Онлайн доступ: https://nasplib.isofts.kiev.ua/handle/123456789/158072
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Цитувати: Раціональність функцій росту ініціальних автоматів Мілі / Є.В. Бондаренко, В.М. Скочко // Доповіді Національної академії наук України. — 2019. — № 3. — С. 3-8. — Бібліогр.: 13 назв. — укр.

Функція росту 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.