A Decomposition Of Weakly Invertible Finite Automata

Automata theory is mathematical theory which studies the function, the structure and their relation between them about discrete system. Its original purpose is studying the analysis and synthesis of automata. Finite automata is a branch of automata theory, and has got good applications in fields of computer, automatic control etc. Decomposition of finite automata is a concept corresponding to composition of finite automata in Finite Automata Public Key Crypto- system(FAPKC). Research of decomposition of finite automata may simplify automata, so it is not only helping make clear the structure, the property, the function of finite automata, but also helps to analyse the safety of FAPKC.Through the output weight, this paper discusses a decomposing form about weakly invertib- le finite automata; also, gets its form for the linear finite automata and related decision method; the other side, studies that in what situation weakly invertible finite automata (not necessarily finite automata with n elements) can get finite order delay unite by decomposition.This paper is composed of five parts.In Part one, i.e. Chapter one, it simply introduces finite automata and Finite Automata Public Key Cryptosystem, gives the present main results about decomposition of weakly invertible finite automata and the work in this paper, and makes simple introduction for the basic concepts and symbols.In Part two, i.e. Chapter two, it is about the sufficient and necessary condition for that weakly invertible finite automata (have not necessarily n elements) can get finite order delay unit by decomposition. The main results are following:Theorm 2.1. Let finite automata M = < X , Y , S ,δ,λ> be weakly invertible and |X|≥2. k₀∈N₊. For each state s∈S, let delay M ( s )= ms. If holds for any state s , then there exits weakly invertible finite automata M₁ = < X , Y , S ,δ₁ ,λ₁> satisfying: Theorem 2.4. Let finite automata M = < X , Y , S ,δ,λ> be weakly invertible with delayÏ„, and X≥2, k 0∈N₊. Then M can be decomposed into WIFA M₁ with delayÏ„? k0 and k 0 order delay unit M_k0,d, if and only if wk M₀ , s= 1 holds for any state s in M .In Part three, i.e. Chapter three, it deals with a decomposing form of weakly invertible finite automata. The main results are following:Theorem 3.1. Let finite automata M = l , U^m , Uⁿ,δ,λ< be weakly invertible with delayÏ„, and U is a finite set with U = q. Here, r∈N₊:0< r < m. If w_Ï„M ,s = q_Ï„( m-r) and , hold for each state s∈Uⁿ, thenâ‘´When l = m - r, (M|—) is weakly invertible with delay 0 .⑵When l > m - r, (M|—) is strictly weakly invertible with delayÏ„, and the delay step isÏ„for any state.Theorem 3.3. Let finite automata (M|—) = m , U^m , Uⁿ, (δ|—) ,(λ|—)> be weakly invertible with delayÏ„(Ï„> 0), and U is a finite set with |U| = q. Here, r∈N₊:0< r < m. Then M can be decomposed into weakly invertible finite automata with delay 0 and D_Ï„,r, if and only if and for each state s∈Uⁿ.Theorem 3.4. Let finite automata (M|—) = l , U^m , Uⁿ, (δ|—) ,(λ|—)> be weakly invertible with delayÏ„, and U is a finite set with |U| = q. Here, r∈+:0< r < m. Then M can be decomposed into weakly invertible finite automata M with delayÏ„and Dk 0 ,r, if and only if for each state s∈Uⁿ.In Part four, i.e. Chapter four, it discusses the concrete form of this decomposition for the linear finite automata, and get a decision method. The main results are following:Theorem 4.1.1. Let finite automata M = < X , Y , S ,δ,λ> is weakly isomorphic to (M|—) = < (X|—) , (Y|—) , (S|—) , (δ|—) ,(λ|—)> . Let finite automata M₁ = < X₁ , Y₁ , S₁ ,δ₁ ,λ₁> and M₂ = < X₂ , Y₂ , S₂ ,δ₂ ,λ₂> satisfy: M (?) C ( M₁ , M2). Then there exit finite automata (M₁|—) and (M₂|—) satisfying: (M₁|—) weakly isomorphic to M₁, (M₂|—) weakly isomorphic to M₂, and (M|—)(?)C ( (M₁|—) , (M₂|—)).Theorem 4.2.2. For linear finite automata M = < X , Y , S ,δ,λ> over finite field F = GF ( q), let dim( X )= l,dim(Y )= m,dim( S )= n, r∈N₊:0< r < m. Then the following two propositions are equivalent:â‘´There exits subspace V (?) Y spanned by m - r elements in the basesatisfying:⑵There exit three bases: in S , satisfying that their decided finite automata M = < F^l , F^m , Fⁿ, (δ|—) ,(λ|—)> has the output property: and for any state z∈Fⁿ. Here, let the structure matrixes of M are A,B,C,D , corresponding to the three bases.(M|—) is defined are following: (δ|—) ( z , x )= Az + Bx, (λ|—) ( z , x )= Cz + Dx for any state z∈Fn, any input alpha x∈F^l.Theorem 4.2.4. Let LFA M = < X , Y , S ,δ,λ> over finite field F = GF ( q) be weakly invertible with delayÏ„(Ï„> 0). Let dim( X )= l, dim(Y )= m, dim( S )= n, l = m and r∈+:0< r < m. Then M can be decomposed into WILFA M 0 with delay 0 and LFA M D, if and only if there exits a subspace V of Y satisfying:â‘ for any state s∈S;â‘¡y_i - y_i'∈V, i = 1,2,…,Ï„, (?)y₁ y₂…y_Ï„, y₁' y₂'…y_Ï„'∈w_M,s^Ï„, for any state s∈S.Theorem 4.2.5. Let LFA M = < X , Y , S ,δ,λ> , dim( X )= l,dim(Y )= m,dim( S )= n, and r∈N₊:0< r < m. Then there exit a subspace V (?) Y with dimension m - r, which satisfies: y_i - y_i'∈V, i = 1,2,…,Ï„, (?)y₁ y₂…y_Ï„, y₁' y₂'…y_Ï„'∈w_M,s^Ï„, for any state s∈S; if and only if there exit structure matrixes A,B,C,D in M , satisfying rank ([CA^{Ï„- 2} B , CA^{Ï„- 3}B ,…, CAB , CB , D ])≤m - r.Part five is conclusion. It introduces the main results for this paper, illustrates its meaning and that what need continue discussion.