Part 3. Mathematical models

Comlexity of implementation of elementary basis in one-place lineary automata class that preserves zero sequence

I. Ilin

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: For now some facts about completeness of linear automata are proven. We now know about every precomlete class on superposition operetion and composition operation, the completeness criterions are also had been formulated. In this work we have proven some facts about the complexity of this process: to receive neutral element and delay.

Keywords: linear automata, comlexity estimation.