Part 3. Mathematical models

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

F. R. Yusupov

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

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.