Two Results of Decomposing Weakly Invertible Finite Automata

It is very important to investigate the decompositon of weakly invertible finite automata, since it could provide an approach to cryptanalyzing finite automaton public-key cryptosystem (FAPKC), which was proposed by Tao Renji and Chen Shihu a in 1985. This paper deals with this topic. For an n-ary weakly invertible fini te automaton (WIFA, for short) M with delay τ, a necessary and sufficient cond ition is obtained, that M can be decomposed into a WIFA with delay 0 and a so-ca lled τ-order delay unit, i.e., the τ-output weight of s is 1 for any state s i n M. Meanwhile, based on a class of weakly invertible finite automata that canno t be decomposed into a delay unit, an example is hereby constructed. Thus, a neg ative answer to an open question presented by Bao Feng in 1993 is given.