Part 3. Mathematical models

Approximation completeness of linear definite automata

I. V. Moldovanov

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: In linear definite automata, the output signals at each moment depend only on a bounded number of the most recent input values. This paper studies functional completeness with respect to the operator of approximation closure for the class of linear definite automata over the two-element field. For this class of automata, a completeness criterion is obtained, formulated in terms of a system of precomplete classes.

Keywords: approximation closure, linear automata, definite automata.