Intelligent Systems.
Theory and Applications

(Intellektual'nye Sistemy. Teoriya i Prilozheniya)

On generating sets in the class of finite automata with a linear output function

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
Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue

× Issue cover