Образец для цитирования:
Карандашов М. В. Алгоритм проверки транзитивности отображений, ассоциированных с конечными автоматами из групп ASp // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2017. Т. 17, вып. 1. С. 85-95. DOI: https://doi.org/10.18500/1816-9791-2017-17-1-85-95
Алгоритм проверки транзитивности отображений, ассоциированных с конечными автоматами из групп ASp
В статье затрагивается вопрос определения свойства транзитивности автоматных отображений, определяемых конечными детерминированными автоматами. Приведен критерий транзитивности автоматных отображений на словах конечной длины в терминах конечных детерминированных автоматов и деревьев детерминированных функций. Показано, что для конечных автоматов из групп ASp можно построить алгоритм проверки транзитивности. Для доказательства данного факта использованы свойства абелевых групп перестановок. На основе представленных результатов построен матричный алгоритм проверки транзитивности автоматных отображений на словах конечной длины для инициальных автоматов из групп ASp. Особенностью данного алгоритма является его независимость от длин рассматриваемых слов. Даны результаты численных экспериментов и точная верхняя граница сложности представленного алгоритма.
1. Григорчук Р. И., Некрашевич В. В., Сущанский В. И. Автоматы, динамические системы и группы // Динамические системы, автоматы и бесконечные группы : сб. ст. Тр. МИАН. Т. 231. М. : Наука, 2000. С. 134–214.
2. Тяпаев Л. Б. Транзитивные семейства автоматных отображений // Дискретные модели в теории управляющих систем : тр. IX Междунар. конф. (Москва и Подмосковье, 20–22 мая 2015 г.); отв. ред. В. Б. Алексеев, Д. С. Романов, Б. Р. Данилов. М. : МАКС Пресс, 2015. С. 244–247.
3. Tyapaev L. B. Transitive families and measure-preservind an N-unit delay mappings // Компьютерные науки и информационные технологии : материалы Междунар. науч. конф. Саратов : Издат. центр «Наука», 2016. С. 425–429.
4. Гилл А. Введение в теорию конечных автоматов. М. : Наука, 1966. 272 с.
5. Карандашов М. В. Исследование биективных автоматных отображений на кольце вычетов по модулю 2 k // Компьютерные науки и информационные технологии : материалы Междунар. науч. конф. Саратов : Издат. центр «Наука», 2014. С. 148–152.
6. Яблонский С. В. Введение в дискретную математику : учеб. пособие для вузов. М. : Наука ; Гл. ред. физ.-мат. лит., 1986. 384 с.
7. Калужин Л. А., Сущанский В. И. Преобразования и перестановки : пер. с укр. М. : Наука ; Гл. ред. физ.-мат. лит., 1985. 160 с.
8. Алешин С. В. Конечные автоматы и проблема Бернсайда о периодических группах // Матем. заметки. 1972. Т. 11, № 3. С. 319–328.
