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

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