Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


For citation:

Карандашов М. В. Алгоритм проверки транзитивности отображений, ассоциированных с конечными автоматами из групп ASp // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2017. Т. 17, вып. 1. С. 85-95. DOI: 10.18500/1816-9791-2017-17-1-85-95

Опубликована онлайн: 
22.02.2017
Язык публикации: 
русский
Рубрика: 
DOI: 
10.18500/1816-9791-2017-17-1-85-95
УДК: 
519.7

Алгоритм проверки транзитивности отображений, ассоциированных с конечными автоматами из групп 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. 
Полный текст в формате PDF:
(downloads: 21)