Известия Саратовского университета. Новая серия.
ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


группы ASp

Алгоритм проверки транзитивности отображений, ассоциированных с конечными автоматами из групп ASp

В статье затрагивается вопрос определения свойства транзитивности автоматных отображений, определяемых конечными детерминированными автоматами. Приведен критерий транзитивности автоматных отображений на словах конечной длины в терминах конечных детерминированных автоматов и деревьев детерминированных функций. Показано, что для конечных автоматов из групп ASp можно построить алгоритм проверки транзитивности. Для доказательства данного факта использованы свойства абелевых групп перестановок.