ON COMPLEXITY OF FORMAL CODING METHOD FOR ANALYSIS OF GENERATOR WITH MONOCYCLE SUBSTITUTIONAL TRANSITION FUNCTION | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2009. № 3(5).

Here we investigate autonomous automata with automaton states being binary n-dimensional vectors and transition function being a monocycle substitution. The complexity T_n of solving gamma generating equations system by formal coding method is estimated asuming the number of equations is not constrained. Bounds of T_n are obtained by estimating line complexity and the order monomial sets for the output functions sequence. It is stated that TL(2^n-1) _n < TL(2ⁿ) where TL(m) is a complexity of solving linear equations system of size m × m over field GF(2).