О порядке автоматов с операцией суперпозиции.

Аннотация

Если входной и выходной алфавиты инициального автомата совпадают, то число различных автоматов, получаемых суперпозицией исходного автомата с самим собой, может быть как конечным, так и бесконечным. Задача определения порядка конечного инициального автомата относительно суперпозиции алгоритмически неразрешима в общем случае, но для некоторых классов автоматов удается найти алгоритмы определения порядка.

Ключевые слова: автоматы Мили, классы Поста, алгоритмическая разрешимость.

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)

← К номеру журнала

× Issue cover