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

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

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



ПДМ. Приложение:
Год:
Том:
Выпуск:
Страница:
Найти






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


ПДМ. Приложение, 2016, выпуск 9, страницы 115–118 (Mi pdma273)  

Прикладная теория автоматов и графов

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

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

Кафедра дискретной математики и информационных технологий Саратовского национального исследовательского университета им. Н. Г. Чернышевского, г. Саратов

Аннотация: Рассматривается вопрос определения свойства транзитивности автоматных отображений. Приводится общий критерий транзитивности автоматного отображения на словах длины $k\in\mathbb N$. Для автоматов из групп $AS_p$ предложен алгоритм проверки транзитивности. Сложность представленного алгоритма зависит от числа состояний автомата и не зависит от длины входного слова; приведена верхняя граница сложности алгоритма.

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

DOI: https://doi.org/10.17223/2226308X/9/46

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

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

Образец цитирования: М. В. Карандашов, “О транзитивности отображений, ассоциированных с конечными автоматами из групп $AS_p$”, ПДМ. Приложение, 2016, № 9, 115–118

Цитирование в формате AMSBIB
\RBibitem{Kar16}
\by М.~В.~Карандашов
\paper О транзитивности отображений, ассоциированных с~конечными автоматами из групп~$AS_p$
\jour ПДМ. Приложение
\yr 2016
\issue 9
\pages 115--118
\mathnet{http://mi.mathnet.ru/pdma273}
\crossref{https://doi.org/10.17223/2226308X/9/46}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdma273
  • http://mi.mathnet.ru/rus/pdma/y2016/i9/p115

    ОТПРАВИТЬ: 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
  • Прикладная дискретная математика. Приложение
    Просмотров:
    Эта страница:61
    Полный текст:14
    Литература:14

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