A Decomposition of the Weakly Invertible Linear Finite Automata

Composition of finite automata is a method of constructing new finite automata and is also a way of constructing public key in the finite automata public key crypt-systems. On the other hand, the study of the decomposition of weakly invertible finite automata is necessary, because it can help to analyze the structure of weakly invertible finite automata and solve its weak inverse. In this paper, firstly, it is proved that the weak isomorphism weakly invertible finite automata have similar decomposition. Secondly, a decomposition about a special weakly invertible linear finite automata (WILFA) M is considered, and a sufficient condition for the existence of this decomposition is found from the output weight of states. Thirdly, the decomposition is extended to the general WILFA, i.e. a WILFA with delay τ can be decomposed into a WILFA with delay 0 and a finite automata M\-D. That is because any WILFA is weakly isomorphic to the special WILFA M. Meanwhile, a sufficient and necessary condition for the existence about this decomposition is obtained. Finally, this sufficient condition for the existence of the decomposition is reflected on the algebra property of the output sequence, and it is partly converted into counting the rank of a matrix. For this decomposing form, the decomposed finite automata neednt be n-ary weakly invertible finite automata, and the corresponding condition is only related with the output sequence.