О линейной реализуемости переходных систем по входной переменной
Получена: 29.10.2026 Доработана: 30.10.2026 Принята: 02.11.2026
Опубликована: 2026 год, том 30, выпуск 4, С. 127–130
Аннотация
Данная работа посвящена изучению вопроса простойреализации переходной системы посредством кодирования. В общем случае переход от абстрактного автомата к булеву оператору осуществляется с помощью кодирования входного алфавита, алфавита состояний и выходного алфавита. Входные переменные полученного оператора можно разбить на два множества: одно соответствует коду входного символа, второе — коду состояния. Это позволяет рассмотреть свойство линейной реализуемости по каждому множеству отдельно.
В статье исследуется вопрос линейной реализуемости относительно входной переменной. Доказан критерий, согласно которому свойство аддитивного сдвига для порождающих внутренней полугруппы переходной системы является необходимым и достаточным условием линейной реализуемости по входной переменной независимо от длины кода.
Ключевые слова: теория автоматов, переходные системы, подстановка, кодирование, сложность, булев оператор.
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
EN