Transition systems linearly realizable with respect to the input variable
Received: 29 Oct 2026 Revised: 30 Oct 2026 Accepted: 02 Nov 2026
Published: 2026, vol. 30, issue 4, pp. 127–130
Abstract
This paper continues the investigation into the complexity of semiautomata realization via states encoding, namely the property of linear realizability of semiautomaton. Encoding of the semiautomaton alphabets induces a Boolean operator. Arguments of the Boolean operator might be separated into two sets. The first one corresponds to the code of the input alphabet, the second one corresponds to the code of the alphabet of states. The property of the linear realizability with respect to each subset of variables can be studied separately.
This paper studies the property of linear realizability with respect to input variables. It is proven that “additive shift” property for generators of the inner semigroup \(p_0\) and \(p_1\) is a necessary and a sufficient condition for semiautomaton to be linearly realizable by input variable regardless of the code length. This means that code length increasing will not induce linear realizability if “additive shift” property is not fulfilled for generators of the inner semigroup.
Keywords: Automata theory, semiautomata, transition systems, permutation, state encoding, complexity, boolean operator.
BibTeX
@article{IS-Rodin2026,
author = {Rodin, Sergei Borisovich},
title = {{Transition systems linearly realizable with respect to the input variable}},
journal = {Intelligent Systems. Theory and Applications},
year = {2026},
volume = {30},
number = {4},
pages = {127--130},
}
AMSBIB
\Bibitem{IS-Rodin2026}
\by S.\,B.~Rodin
\paper Transition systems linearly realizable with respect to the input variable
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 4
\pages 127--130
\lang In Russian
RU