This article is cited in 8 papers

The problem of completeness in the class of linear automata

A. A. Chasovskikh

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: Classes of linear automata over finite fields with composition operations (superposition and feedback) are considered. Previously an algorithm for checking the completeness of finite subsets was obtained for these classes. In the case of a simple field, all precomplete classes whose set is a countable reduced criterial system are found. Previously in the general case the set of closed classes was constructed, which is a criterial system, including the family of classes generated by maximal fields in the transcendental extension of the finite field under consideration. For simple fields, all classes of this family were absorbed by other classes from the reduced criterial system. Therefore, in the present paper the family is being investigated in the case of finite fields that are not simple. It turned out that part of the elements of the family is also absorbed in this case, but also among its elements there are precomplete classes that are finitely generated and not contained among the precomplete classes of other families.

Keywords: linear automaton, adder, delay, feedback, composition operations, completeness check algorithm, precomplete class.