On generating sets in the class of finite automata with a linear output function
Received: 06 Nov 2026 Accepted: 07 Nov 2026
Published: 2026, vol. 30, issue 4, pp. 139–142
Abstract
It was shown earlier that the class of finite automata with one linear output is not finitely generated under bounded composition. A much narrower generating set is built from the adder, the constant and conjunctions with a delay. For automata with at most \(s\) inputs a reduced generating set of three automata is found, including a conjunction of \(s+1\) variables with a delay, and it is proved that a smaller arity of the conjunction is insufficient. An upper bound for the complexity of realization of automata by circuits over this set is obtained.
Keywords: finite automata, automata with a linear output function, composition operations, generating set, complexity of realization.
BibTeX
@article{IS-Yusupov2026,
author = {Yusupov, Feliks Renatovich},
title = {{On generating sets in the class of finite automata with a linear output function}},
journal = {Intelligent Systems. Theory and Applications},
year = {2026},
volume = {30},
number = {4},
pages = {139--142},
}
AMSBIB
\Bibitem{IS-Yusupov2026}
\by F.\,R.~Yusupov
\paper On generating sets in the class of finite automata with a linear output function
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 4
\pages 139--142
\lang In Russian
RU