EN
О свойстве аддитивного сдвига для линейной реализуемости автоматов
Опубликована: 2024 год, том 28, выпуск 2, С. 52–66
Аннотация
Одним из необходимых условий для линейной реализуемости автомата является выполнения условия «аддитивного сдвига» на порождающих внутренней полугруппы автомата. «Аддитивный сдвиг» задается отображением на множестве состояний автомата. В данной работе изучаются такие отображения. Приведены свойства, которыми должно обладать отображение, чтобы задавать «аддитивный сдвиг». Так же показано, что такие отображения линейно реализуемы посредством неизбыточных кодирований и приведен явный вид получаемого оператора.
Ключевые слова: теория автоматов, переходные системы, подстановка, кодирование, сложность, булев оператор.
BibTeX
@article{IS-Rodin2024,
author = {Родин, Сергей Борисович},
title = {{О свойстве аддитивного сдвига для линейной реализуемости автоматов}},
journal = {Интеллектуальные системы. Теория и приложения},
year = {2024},
volume = {28},
number = {2},
pages = {52--66},
}
AMSBIB
\RBibitem{IS-Rodin2024}
\by С.\,Б.~Родин
\paper О свойстве аддитивного сдвига для линейной реализуемости автоматов
\jour Интеллектуальные системы. Теория и приложения
\yr 2024
\vol 28
\issue 2
\pages 52--66