Decomposition of Weakly Invertible Finite Automata
Feng Cao · Chinese Journal of Computers · 2005
In 1985, the finite automaton public key cryptosystem was proposed. It stimulates the investigation of invertibility of finite automata. The concept of composition of finite automata is first proposed in finite automaton public key cryptosystem. It is easy to get the conclusion that the composition of two weakly invertible finite automata is still a weakly invertible finite automaton, and its delay steps is no more than the sum of the delay steps of two finite automata. On the other hand, because lack the effective mathematics tool, the problem of how to decompose a weakly invertible finite automaton into two weakly invertible finite automata with smaller delay steps is still a difficult problem at present. In this paper, authors consider the problem of how to decompose a kind of n-ary weakly invertible finite automata with strict τ delays and get some results. Firstly, authors prove that M can be decomposed to τ weakly invertible finite automatons with strict 1 delay if the tree T(s,τ ) is equal-branch of all states, then prove M can be decomposed to a weakly invertible finite automaton with strict (τ-m) delays and a m-order delay units if the tree T(s,m) is equal-branch of all states.