О линейной реализуемости переходных систем по входной переменной

Аннотация

Данная работа посвящена изучению вопроса простойреализации переходной системы посредством кодирования. В общем случае переход от абстрактного автомата к булеву оператору осуществляется с помощью кодирования входного алфавита, алфавита состояний и выходного алфавита. Входные переменные полученного оператора можно разбить на два множества: одно соответствует коду входного символа, второе — коду состояния. Это позволяет рассмотреть свойство линейной реализуемости по каждому множеству отдельно.

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

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

BibTeX
@article{IS-Rodin2026,
  author  = {Родин, Сергей Борисович},
  title   = {{О линейной реализуемости переходных систем по входной переменной}},
  journal = {Интеллектуальные системы. Теория и приложения},
  year    = {2026},
  volume  = {30},
  number  = {4},
  pages   = {127--130},
}
AMSBIB
\RBibitem{IS-Rodin2026}
\by С.\,Б.~Родин
\paper О линейной реализуемости переходных систем по входной переменной
\jour Интеллектуальные системы. Теория и приложения
\yr 2026
\vol 30
\issue 4
\pages 127--130
Опубликовано на условиях лицензии Creative Commons Attribution 4.0 International (CC BY 4.0)

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

× Issue cover