| The automata theory is a mathematical theory to study the function and structure of dis-crete digital system, and even the relationship between them. The finite automata is a branch of automata theory. With the emergence and development of science and technology such as digi-tal computer, digital communications and automation, automata theory plays a more and more important role in theory and practice. Linear finite automata is an important part of automata theory. With the high speed vigorous development and the widespread application of commu-nications technology and network, more and more information are transmitted on the network. Thus information security and protection problems become particularly important. Linear finite automata theory plays a very important role in information security and protection. Reversibility problems in finite automata have been widely applied and studied recent years.The public key cryptography based on weak reversible finite automata, and the realization of finite automata public key cryptography based on password system and digital signatures further shows the advantage and potentiality of finite automata reversibility in cryptography, which makes the:research on finite automata reversibility especially important.This paper discusses the reversibility, weak reversibility and delay reversibility of linear finite automata, and discusses how to estimate the problem of finite automata reversibility using transfer function matrix and free response matrix Also, this paper discusses the equivalence of linear finite automata, and the relationship between reversibility of two linear finite automata.Theorem 2.1 Let H'(z)andH" (z) be Transfer function matrix of linear finite automata M,M", G'(z) andG"(z) be free response matrix, thenM" is M' DelayτInverse step iff H"(z)H'(z)= zτE,the elements of H" (z)G'(z) And G" (z) are the number of<τof the polynomial.Theorem 2.2 Let H(z) be Transfer function matrix of the linear finite automaton M in the finite field F, G(z) be free response matrix, M reversible iff H(z) are the set of linear independent column vectors, and columns Delivery of G(z) in the field F on the column vector space and H(z) in the field F on the vector space is zero space.Theorem 2.3 Let H(z) be Transfer function matrix of the linear finite automaton M in the finite field F, G(z) be free response matrix, then M is reversible iff there is matrix H'(z) satisfy: τhas H'(z)H(z)= zτE for a non-negative integers, H'(z)G(z). The elements are the number of<τof polynomials, and H'(z) The elements are the number of≤τof the polynomial.Theorem 2.5 Let G(z) be transfer function matrix of linear finite automata M=(X, Y,S,δ,λ) in finite field F, H(z) be free response matrix, then M is weak reversible iff H(z) exists left inverse.Theorem 2.6 Let M=(X,Y,S,δ,λ) and M=(X, Y, S,δ,λ) be linear finite automata, G(z), G'(z) be free response matrix of M and M', H(z), H'(z) be transfer function matrix, n is the state space dimension of M,then the M'is M of the delay inτ-step weak inverse iff: H'(z)H(z)=zτE,And for each cj exists s'∈S' Makes cj+G'(z)s'number of elements are<τof the polynomialWhere cj is H'(z)G(z) of the column, j=1...n.Theorem 2.7 Let G(z) be the free response matrix of linear finite automata M=(X, Y. S,δ,λ), H(z) be Transfer function matrix, M0=(X, Y, S0,δ0,λ0) be the minimum of linear finite automata of M, then M delaysτWeak reversible step iff M0 delayτweakly reversible.Theorem 2.8 Let M=(X,Y,S,δ,λ) be the smallest linear subspace of finite automata M0=(X, Y, So,δ0,λ0), G(z) be free response matrix of it, H(z) be transfer function matrix of it, then M0 delayτweak reversible step iff exists matrix H'(z) satisfy:H'(z)H(z)=zτE, andH'(z) does not contain the elements of the denominator polynomial factor z.Theorem 2.9 Let H'(z), G'(z) respectively are free transfer function matrix and response matrix of linear finite automataM', Then M'the delayτstep iff the weak against the existence of matrix H(z) satisfy: H'(z)H(z)=zτE, H(z) does not contain the elements of the denominator polynomial factor z.Chapter III:equivalence, like, stronger than the relationship and reversibility of linear finite automata. Through this chapter, the structure of linear finite automata discussed the equivalent matrix, similar and stronger than the relationship of reversible finite automata, the weak reversible and delayedτReversible step, the main results are:Theorem 3.5 Let M and M' are the linear finite automata on GF(q), A,B,C,D and A',B',C',D' be the structure matrix.(1) if M and M' similar and P is nonsingular matrix, such that A'=PAP-1,B'=PB,C'=CP-1, D'=D There are G'(z)= G(z)P-1, H'(z)=H(z)(2) The zero-state of M and zero-state of M'are equivalent, iff H'(z)=H(z) (3) M and M' equivalent, iff G'(z) and G(z) in the column GF(q) on the composition of a linear combination of GF(q) vector space over the same And H'(z)=H(z),which G(z) and G'(z) are M And M' Generated free response matrix, H(z) and H'(z) Were M and M' the transfer function matrix.Theorem 3.6 Let M be the linear finite automata in GF(q), G(z) be the free response generator matrix, M minimal iff G(z) In GF(q) on the linearly independent.Theorem 3.7 Let Mo is the linear finite automata in GF(q), the structure parameter is l,m,no, the transfer function matrix of H(z), And Mo state variable chosen by the state to zero, set M1 be the linear finite automata in GF(q), the structure parameter is 0, m,n, G(z) be free response generator matrix. Then G(z) and H(z) is generated free response matrix and transfer function matrix the linear finite automaton M in GF(q) iff M0 of the free response space is M1 of the free response space, subspace Theorem 3.11 If M'～M,then M'is weakly reversible iff M is weakly invertiblTheorem 3.12 If M'(?) M, and M delayτweakly invertible, then M'delayτweakly invertible.Theorem 3.16 If M and M'similar, M delayτ-step invertible if f M'delay inτ-step reversible... |
PDF Full Text Request