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

Yusupov Feliks Renatovich

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

Yusupov F. R.

Yusupov Feliks Renatovich

graduate student, Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Chair of Mathematical Theory of Intellectual Systems

Received: 25 Mar 2026

Published: 2025, vol. 29, issue 4, pp. 150–162

Download full text (In Russian)

Abstract

The class of finite automata is finitely generated by composition operations [1]. An important subclass of this class are classes of automata with linear output functions. A set of operations on automata consisting of variable substitution, automata substitution, and feedback is called bounded composition. The class of unary automata is closed under bounded composition operations. In this paper, we show that the class of unary finite automata with linear output functions and bounded composition operations lacks finite complete sets. However, automata from this class, implemented by circuits with at most one delay, generate this class.

Keywords: finite automata, composition operations for automata, finite automata with linear outputs.

BibTeX

@article{IS-Yusupov2025,
  author  = {Yusupov, Feliks Renatovich},
  title   = {{On the cardinality of generating sets in the class of finite automata
with a linear output function}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2025},
  volume  = {29},
  number  = {4},
  pages   = {150--162},
}

AMSBIB

\Bibitem{IS-Yusupov2025}
\by F.\,R.~Yusupov
\paper On the cardinality of generating sets in the class of finite automata
with a linear output function
\jour Intelligent Systems. Theory and Applications
\yr 2025
\vol 29
\issue 4
\pages 150--162
\lang In Russian

Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue