RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика, 2017, том 17, выпуск 1, страницы 85–95 (Mi isu706)  

Научный отдел
Информатика

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

М. В. Карандашов

Саратовский национальный исследовательский государственный университет им. Н. Г. Чернышевского, Россия, 410012, Саратов, Астраханская, 83

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

Ключевые слова: конечные автоматы, транзитивность, автоматные отображения, группы $AS_p$.

DOI: https://doi.org/10.18500/1816-9791-2017-17-1-85-95

Полный текст: PDF файл (361 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.7

Образец цитирования: М. В. Карандашов, “Алгоритм проверки транзитивности отображений, ассоциированных с конечными автоматами из групп $AS_p$”, Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика, 17:1 (2017), 85–95

Цитирование в формате AMSBIB
\RBibitem{Kar17}
\by М.~В.~Карандашов
\paper Алгоритм проверки транзитивности отображений, ассоциированных с конечными автоматами из групп~$AS_p$
\jour Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика
\yr 2017
\vol 17
\issue 1
\pages 85--95
\mathnet{http://mi.mathnet.ru/isu706}
\crossref{https://doi.org/10.18500/1816-9791-2017-17-1-85-95}
\elib{http://elibrary.ru/item.asp?id=29112759}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/isu706
  • http://mi.mathnet.ru/rus/isu/v17/i1/p85

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Известия Саратовского университета. Новая серия. Серия Математика. Механика. Информатика
    Просмотров:
    Эта страница:79
    Полный текст:16
    Литература:15

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019