О порядке автоматов с операцией суперпозиции.
Получена: 01.10.2026 Доработана: 19.10.2026 Принята: 22.10.2026
Опубликована: 2026 год, том 30, выпуск 4, С. 62–65
Аннотация
Если входной и выходной алфавиты инициального автомата совпадают, то число различных автоматов, получаемых суперпозицией исходного автомата с самим собой, может быть как конечным, так и бесконечным. Задача определения порядка конечного инициального автомата относительно суперпозиции алгоритмически неразрешима в общем случае, но для некоторых классов автоматов удается найти алгоритмы определения порядка.
Ключевые слова: автоматы Мили, классы Поста, алгоритмическая разрешимость.
BibTeX
@article{IS-Babin-Muravev2026,
author = {Бабин, Дмитрий Николаевич and Муравьев, Никита Валерьевич},
title = {{О порядке автоматов с операцией суперпозиции.}},
journal = {Интеллектуальные системы. Теория и приложения},
year = {2026},
volume = {30},
number = {4},
pages = {62--65},
}
AMSBIB
\RBibitem{IS-Babin-Muravev2026}
\by Д.\,Н.~Бабин, Н.\,В.~Муравьев
\paper О порядке автоматов с операцией суперпозиции.
\jour Интеллектуальные системы. Теория и приложения
\yr 2026
\vol 30
\issue 4
\pages 62--65
Опубликовано на условиях лицензии
Creative Commons Attribution 4.0 International (CC BY 4.0)
EN