Reversible Finite Automata Structure And Decomposition

The structure of feedforward inverse finite automata is a fundamental problem in the invertibility theory of finite automata. The characterization of the structure of feedforward inverses with delay steps ≥ 3 is a long-term unsolved problem, especially when we wish give the explicit expressions of the functions, the work get more difficult. The decomposition of weakly invertible finite automata is another problem in the invertibility theory of finite automata. It was first raised by Bao Feng in 1993. However, this issue hasnot been studied in depth since then . This thesis mainly deals with these two topics.In Chapter 1, we introduce the background, core notions, main contents of the invertibility theory of finite automata, and its applications in public key cryptography-the Finite Automaton Public Key Crypotsystem(FAPKC).In Chapter 2, we investigate the structure of binary feedforward inverse finite automata with delay 3. For a semi - input - memory finite automaton C(Ma, f) , where both the input alphabet and the output alphabet have two elements, the state graph of the autonomous finite automaton Ma is cyclic, when it is weakly invertible with delay3, we give the expressions of functions f and some other relationships when the minimal 3 - output weight w3,m = 1, 2, 8, respectively. Furthermore, we also show that if C(Ma,f) satisfies these conditions, then it is weakly invertible with delay 3. Due to the fact that C(Ma, f) is weakly invertible with delay 3 iff it is weak inverse with delay 3, we actually give a partial characterization of the structure of binary feedforward inverse finite automata with delay 3. Our results are of scientific meaning in characterizing the structure of feedforward inverses with delay steps ≥ 3.In Chapter 3, we consider the decomposition of weakly invertible finite automata by using the output weight of finite automaton, and obtain the following results. (1)Main Theorem: LetM be an n-ary weakly invertible finite automaton with delay r, then M can be decomposed into a weakly finite automaton with delay 0 and a so-called τ-order delay unit iff |WMT,S|= 1 holds for each state s of M. Applying the main theorem we show that (2) There exist a class of weakly invertible finite automata that cannot be decomposed into weakly finite automata with delay 0 and delay units. (3) By (2) we construct an example which negatively answer an unsolved question proposed in 1993. (4) We also give a sufficient condition that a binary strongly connected weakly invertible M with delay τ can be decomposed into a weakly invertible finite automaton with strict delay τ - 1 and a weakly invertible finite automaton with strict delay 1 . (5) Using the composition method we obtain a class of n-ary weakly invertible finite automata with strict delay τ, where the delay step of each state of M is τ.In Chapter 4, we propose a concurrent signature based on finite automata signature scheme. Our scheme satisfies the security properties of concurrent signature, such as correctness, unforge-ability, Ambiguity and fairness.In Chapter 5, we list some unsolved questions, problems , and further directions for research in these areas .