Tao R. Finite Automata and Application to Cryptography
Подождите немного. Документ загружается.
4.1 Relations Between R
a
R
b
Transformations 113
or
Q
1
j
Q
3
j
Q
2
j
Q
4
j
for short, where Q
1
j,c−1
and Q
4
j,c−1
are ¯r
c
× r
c
and (m− ¯r
c
) ×
(m − r
c
) matrices, respectively. Then we have
R
3
R
4
R
5
=
Q
0,c−1
Q
1,c−1
... Q
c−1,c−1
00
0 Q
0,c−1
... Q
c−2,c−1
Q
c−1,c−1
0
.
It follows that
R
2
R
3
R
4
R
5
R
6
=
Q
4
0
Q
3
1
Q
4
1
Q
3
2
... Q
4
c−1
0000Q
3
0
0 Q
1
0
Q
2
0
Q
1
1
... Q
2
c−2
Q
1
c−1
Q
2
c−1
000
.
Let R
2
R
3
R
4
R
5
R
6
=[
¯
Q
0c
, ...,
¯
Q
c+1,c
], where
¯
Q
jc
has m columns, j =
0, 1,...,c+1. To prove Q
3
0,c−1
= 0, from (4.4), we have
¯
B
0,c−1
= Q
0,c−1
B
0,c−1
.
Thus
¯
P
c−1
¯
B
0,c−1
=
¯
P
c−1
Q
0,c−1
P
−1
c−1
(P
c−1
B
0,c−1
)=Q
0,c−1
(P
c−1
B
0,c−1
). (4.6)
Since (4.2) is linear over GF (q), the first r
c
rows of P
c−1
B
0,c−1
are linearly
independent over GF (q)andthelastm − r
c
rows of P
c−1
B
0,c−1
are 0. From
(4.3), the last m − ¯r
c
rows of
¯
P
c−1
¯
B
0,c−1
are 0. Using (4.6), it follows that
Q
3
0,c−1
, the submatrix of the first r
c
columns and the last m − ¯r
c
rows of
Q
0,c−1
,is0.SinceQ
3
0,c−1
= 0 yields
¯
Q
c+1,c
=0,weobtain
¯
Q
c+1,c
=0;
therefore, Q
c+1,c
= R
1
¯
Q
c+1,c
E
m,−r
c
=0.
Let
¯
B
j,c−1
=
¯
B
j,c−1
=0
m,m
, j = h +1,..., h + c − 1, and
Ω
r
k
=
⎡
⎢
⎢
⎢
⎣
B
0r
B
1r
... ... B
hr
B
0r
B
1r
... ... B
hr
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
B
0r
B
1r
... ...B
hr
⎤
⎥
⎥
⎥
⎦
with mk rows, for any r and any k. From (4.4), we have
h+c−1
j=0
¯
B
j,c−1
z
j
=
c−1
j=0
Q
j,c−1
z
j
h
j=0
B
j,c−1
z
j
.
It follows immediately that
¯
B
0,c−1
¯
B
1,c−1
...
¯
B
h+c−1,c−1
00
0
¯
B
0,c−1
...
¯
B
h+c−2,c−1
¯
B
h+c−1,c−1
0
= R
4
Ω
c−1
c+2
. (4.7)
Let
¯
B
jc
=0
m,m
, j = h +1,..., h + c. From (4.3), we have
114 4. Relations Between Transformations
R
1
R
2
R
3
¯
B
0,c−1
¯
B
1,c−1
...
¯
B
h+c−1,c−1
00
0
¯
B
0,c−1
...
¯
B
h+c−2,c−1
¯
B
h+c−1,c−1
0
= R
1
R
2
¯
B
0,c−1
¯
B
1,c−1
...
¯
B
h+c−1,c−1
00
0
¯
B
0,c−1
...
¯
B
h+c−2,c−1
¯
B
h+c−1,c−1
0
=
0
¯
B
0c
...
¯
B
h+c−2,c
¯
B
h+c−1,c
¯
B
h+c,c
.
Using (4.7), we have
0
¯
B
0c
...
¯
B
h+c−2,c
¯
B
h+c−1,c
¯
B
h+c,c
= R
1
R
2
R
3
R
4
Ω
c−1
c+2
= R
1
R
2
R
3
R
4
R
5
R
6
R
7
R
−1
7
R
−1
6
R
−1
5
Ω
c−1
c+2
= Q(R
−1
7
R
−1
6
R
−1
5
Ω
c−1
c+2
).
From (4.2), it follows that
0
¯
B
0c
...
¯
B
h+c−2,c
¯
B
h+c−1,c
¯
B
h+c,c
= Q
0 Ω
c
c+1
G
G
(4.8)
for some matrices G
and G
with m rows. Since Q =[Q
0c
, ..., Q
c+1,c
]and
Q
c+1,c
= 0, (4.8) yields
[
¯
B
0c
,...,
¯
B
h+c,c
]=[Q
0c
,...,Q
cc
]Ω
c
c+1
,
which is equivalent to (4.5) because
¯
B
jc
=0forh +1 j h + c.Thatis,
(4.5) holds.
Now we suppose that Q
0,c−1
is nonsingular and (4.3) is linear over GF (q).
Since (4.3) and (4.2) are linear over GF(q), ¯r
c
and r
c
are the ranks of
¯
B
0,c−1
and B
0,c−1
, respectively. Since
¯
B
0,c−1
= Q
0,c−1
B
0,c−1
and Q
0,c−1
is nonsin-
gular, we have ¯r
c
= r
c
.
Since
¯
P
c−1
, P
c−1
and Q
0,c−1
are nonsingular, Q
0,c−1
=
¯
P
c−1
Q
0,c−1
P
−1
c−1
is nonsingular. Noticing ¯r
c
= r
c
and Q
3
0,c−1
= 0, it follows that Q
4
0,c−1
and
Q
1
0,c−1
are nonsingular. Thus
¯
Q
0c
=
Q
4
0,c−1
0
Q
3
1,c−1
Q
1
0,c−1
is nonsingular. Therefore,
Q
0c
= R
1
¯
Q
0c
E
m,−r
c
is nonsingular.
Theorem 4.1.1. Assume that eq
0
(i) and ¯eq
0
(i) are the same. Assume that
eq
c
(i)
R
a
[P
c
]
−→ eq
c
(i),eq
c
(i)
R
b
[r
c+1
]
−→ eq
c+1
(i),c=0, 1,...,τ − 1 (4.9)
is a linear R
a
R
b
transformation sequence and
¯eq
c
(i)
R
a
[
¯
P
c
]
−→ ¯eq
c
(i), ¯eq
c
(i)
R
b
[¯r
c+1
]
−→ ¯eq
c+1
(i),c=0, 1,...,τ − 1 (4.10)
is an R
a
R
b
transformation sequence. Then there exist m × m matrices Q
jτ
,
j =0, 1,...,τ over GF (q) such that
4.2 Composition of R
a
R
b
Transformations 115
h
j=0
¯
B
jτ
z
j
=
τ
j=0
Q
jτ
z
j
h
j=0
B
jτ
z
j
.
Moreover, if (4.10) is linear over GF (q),then¯r
j
= r
j
holds for any j, 1
j τ and Q
0τ
is nonsingular.
Proof.Since ¯eq
0
(i)andeq
0
(i) are the same, (4.4) holds in the case of
c =1,whereQ
00
is the identity matrix. Applying Lemma 4.1.1 τ times, c
from 1 to τ, we obtain the theorem.
Theorem 4.1.2. Let eq
0
(i) and ¯eq
0
(i) be the same and equivalent to the
equation
ϕ
0
(y(i, t +1))+[B
00
,...,B
h0
]ψ
lh
μν
(u, x, i)=0.
(a) If (4.10) is an R
a
R
b
transformation sequence and
¯
B
0τ
ψ
l
μν
(u(i, μ +1),
x(i, ν +1)) as a function of the variable x
i
is an injection, then for any linear
R
a
R
b
transformation sequence (4.9),B
0τ
ψ
l
μν
(u(i, μ +1),x(i, ν +1)) as a
function of the variable x
i
is an injection.
(b) If (4.10) is an R
a
R
b
transformation sequence and
¯
B
0τ
ψ
l
μν
(u(i, μ +1),
x(i, ν +1)) as a function of the variable x
i
is a surjection, then for any linear
R
a
R
b
transformation sequence (4.9),B
0τ
ψ
l
μν
(u(i, μ +1),x(i, ν +1)) as a
function of the variable x
i
is a surjection.
Proof. (a) Suppose that (4.10) is an R
a
R
b
transformation sequence and
¯
B
0τ
ψ
l
μν
(u(i, μ +1),x(i, ν + 1)) as a function of the variable x
i
is an injection.
For any linear (4.9), from Theorem 4.1.1, there exists an m × m matrix Q
0τ
such that
¯
B
0τ
= Q
0τ
B
0τ
. It follows immediately that for any parameters
x
i−1
, ..., x
i−ν
, u
i
, ..., u
i−μ
, B
0τ
ψ
l
μν
(u(i, μ +1),x(i, ν + 1)) as a function of
the variable x
i
is an injection.
(b) The proof of part (b) is similar to part (a), just by replacing“injection”
by “surjection”.
Notice that if for any linear R
a
R
b
transformation sequence (4.9), B
0τ
ψ
l
μν
(u(i, μ+1),x(i, ν +1)) as a function of the variable x
i
is a surjection, then for
any parameters x
i−1
, ..., x
i−h−ν
, u
i
, ..., u
i−h−μ
, y
i+τ
, ..., y
i−t
, the equation
eq
τ
(i) has a solution x
i
. If for any linear R
a
R
b
transformation sequence (4.9),
B
0τ
ψ
l
μν
(u(i, μ +1),x(i, ν + 1)) as a function of the variable x
i
is an injection,
then for any parameters x
i−1
, ..., x
i−h−ν
, u
i
, ..., u
i−h−μ
, y
i+τ
, ..., y
i−t
,the
equation eq
τ
(i) has at most one solution x
i
.
4.2 Composition of R
a
R
b
Transformations
Let X and U be two finite nonempty sets. Let Y
and Y be two column vector
spaces over a finite field GF (q) of dimensions m
and m, respectively, where
m
and m are two positive integers.
116 4. Relations Between Transformations
For any nonnegative integer c,let1eq
c
(i) be an equation
ξ
c
(y(i + c, c +1))+[F
0c
,...,F
h
1
c
]ψ
lh
1
μν
(u, x, i)=0
and let 1eq
c
(i) be an equation
ξ
c
(y(i + c, c +1))+[F
0c
,...,F
h
1
c
]ψ
lh
1
μν
(u, x, i)=0,
where ξ
c
and ξ
c
are two single-valued mappings from Y
c+1
to Y
, F
jc
and
F
jc
are m
× l matrices over GF (q), j =0, 1,...,h
1
.
For any nonnegative integer c,let0eq
c
(i) be an equation
η
c
(y(i + c, c + k +1))+[B
0c
,...,B
h
0
c
]
⎡
⎢
⎣
x
i
.
.
.
x
i−h
0
⎤
⎥
⎦
=0
and let 0eq
c
(i) be an equation
η
c
(y(i + c, c + k +1))+[B
0c
,...,B
h
0
c
]
⎡
⎢
⎣
x
i
.
.
.
x
i−h
0
⎤
⎥
⎦
=0,
where η
c
and η
c
are two single-valued mappings from Y
c+k+1
to Y , B
jc
and
B
jc
are m × m
matrices over GF (q), j =0, 1,...,h
0
.
Let h = h
0
+ h
1
. In this section, for any nonnegative integer c,leteq
c
(i)
be an equation
ϕ
c
(y(i + c, c + k +1))+[C
0c
,...,C
hc
]ψ
lh
μν
(u, x, i)=0
and let eq
c
(i) be an equation
ϕ
c
(y(i + c, c + k +1))+[C
0c
,...,C
hc
]ψ
lh
μν
(u, x, i)=0,
where ϕ
c
and ϕ
c
are two single-valued mappings from Y
c+k+1
to Y , C
jc
and
C
jc
are m × l matrices over GF (q), j =0, 1,...,h.
For any nonnegative integer r,let
Γ
h+r
=
⎡
⎢
⎢
⎢
⎣
F
0
F
1
... ... F
h
1
F
0
F
1
... ... F
h
1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
F
0
F
1
... ... F
h
1
⎤
⎥
⎥
⎥
⎦
(4.11)
be an (h
0
+ r)m
× (h + r)l matrix, where F
j
, j =0, 1,...,h
1
are m
× l
matrices over GF (q).
4.2 Composition of R
a
R
b
Transformations 117
Lemma 4.2.1. Let c>0 and
[C
0,c−1
,...,C
h,c−1
]=[B
0,c−1
,...,B
h
0
,c−1
]Γ
h+1
. (4.12)
If
0eq
c−1
(i)
R
a
[P
c−1
]
−→ 0eq
c−1
(i), 0eq
c−1
(i)
R
b
[r
c
]
−→ 0eq
c
(i), (4.13)
then
eq
c−1
(i)
R
a
[P
c−1
]
−→ eq
c−1
(i),eq
c−1
(i)
R
b
[r
c
]
−→ eq
c
(i) (4.14)
and
[C
0c
,...,C
hc
]=[B
0c
,...,B
h
0
c
]Γ
h+1
. (4.15)
Proof.LetR
1
= E
m,r
c
, R
2
=[0
m,r
c
E
m
0
m,m−r
c
], R
3
= DIA
P
c−1
,2
.By
(4.13), we have
R
1
R
2
R
3
B
0,c−1
B
1,c−1
... B
h
0
,c−1
0
0 B
0,c−1
... B
h
0
−1,c−1
B
h
0
,c−1
= R
1
R
2
B
0,c−1
B
1,c−1
... B
h
0
,c−1
0
0 B
0,c−1
... B
h
0
−1,c−1
B
h
0
,c−1
(4.16)
=
0 B
0c
... B
h
0
−1,c
B
h
0
c
.
We prove that (4.14) is an R
a
R
b
transformation sequence. It is suffi-
cient to prove that the last m − r
c
rows of P
c−1
C
0,c−1
are 0. Let C
0,c−1
=
P
c−1
C
0,c−1
. Since (4.12) yields C
0,c−1
= B
0,c−1
F
0
,wehaveC
0,c−1
=
B
0,c−1
F
0
. From (4.13), it is easy to see that the last m − r
c
rows of B
0,c−1
are 0. It follows immediately that the last m − r
c
rows of C
0,c−1
are 0.
Since (4.14) holds, we have
R
1
R
2
R
3
C
0,c−1
C
1,c−1
... C
h,c−1
0
0 C
0,c−1
... C
h−1,c−1
C
h,c−1
= R
1
R
2
C
0,c−1
C
1,c−1
... C
h,c−1
0
0 C
0,c−1
... C
h−1,c−1
C
h,c−1
=
0 C
0c
... C
h−1,c
C
hc
.
From (4.12) and (4.16), it follows that
0 C
0c
... C
h−1,c
C
hc
= R
1
R
2
R
3
B
0,c−1
B
1,c−1
... B
h
0
,c−1
0
0 B
0,c−1
... B
h
0
−1,c−1
B
h
0
,c−1
Γ
h+2
=
0 B
0c
... B
h
0
−1,c
B
h
0
c
Γ
h+2
.
118 4. Relations Between Transformations
Therefore, (4.15) holds.
For any nonnegative integers c and r,letΓ
c
h+r
be an (h
0
+ r)m
× (h + r)l
matrix
Γ
c
h+r
=
⎡
⎢
⎢
⎢
⎣
F
0c
F
1c
... ... F
h
1
c
F
0c
F
1c
... ... F
h
1
c
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
F
0c
F
1c
... ... F
h
1
c
⎤
⎥
⎥
⎥
⎦
. (4.17)
Lemma 4.2.2. Assume that τ
0
0, c>0,
[C
0,τ
0
+c−1
,...,C
h+c−1,τ
0
+c−1
]=[Q
0,c−1
,...,Q
h
0
+c−1,c−1
]Γ
c−1
h+c
, (4.18)
C
h+j,τ
0
+c−1
=0for j>0,whereQ
j,c−1
is an m × m
matrix over GF (q),
j =0, 1,...,h
0
+ c − 1.If
1eq
c−1
(i)
R
a
[P
c−1
]
−→ 1eq
c−1
(i), 1eq
c−1
(i)
R
b
[r
c
]
−→ 1eq
c
(i), (4.19)
then there exist an m × m invertible matrix
¯
P
τ
0
+c−1
over GF (q) and a non-
negative integer ¯r
τ
0
+c
such that
eq
τ
0
+c−1
(i)
R
a
[
¯
P
τ
0
+c−1
]
−→ eq
τ
0
+c−1
(i),eq
τ
0
+c−1
(i)
R
b
[¯r
τ
0
+c
]
−→ eq
τ
0
+c
(i) (4.20)
and there exist m × m
matrices Q
0c
, ..., Q
h
0
+c,c
over GF (q) such that
[C
0,τ
0
+c
,...,C
h+c,τ
0
+c
]=[Q
0c
,...,Q
h
0
+c,c
]Γ
c
h+c+1
and the rank of Q
0c
is not less than the rank of Q
0,c−1
,whereC
h+j,τ
0
+c
=0
for j>0.
Proof.LetQ
0,c−1
be the reduced echelon matrix of Q
0,c−1
P
−1
c−1
,and
¯
P
τ
0
+c−1
an m × m invertible matrix with Q
0,c−1
=
¯
P
τ
0
+c−1
Q
0,c−1
P
−1
c−1
.Let
¯r
τ
0
+c
be the rank of the submatrix of the first r
c
columns of Q
0,c−1
.
Let R
1
= E
m,¯r
τ
0
+c
, R
2
=[0
m,¯r
τ
0
+c
E
m
0
m,m−¯r
τ
0
+c
], R
3
= DIA
¯
P
τ
0
+c−1
,2
,
R
4
=
Q
0,c−1
Q
1,c−1
... Q
h
0
+c−1,c−1
00
0 Q
0,c−1
... Q
h
0
+c−2,c−1
Q
h
0
+c−1,c−1
0
,
R
5
= DIA
P
−1
c−1
,h
0
+c+2
, R
6
= E
m
(h
0
+c+2),r
c
, R
7
= DIA
E
m
,−r
c
,h
0
+c+2
.It
follows that R
−1
5
= DIA
P
c−1
,h
0
+c+2
, R
−1
6
= E
m
(h
0
+c+2),−r
c
,andR
−1
7
=
DIA
E
m
,r
c
,h
0
+c+2
.LetQ = R
1
R
2
R
3
R
4
R
5
R
6
R
7
. Partition Q =[Q
0c
, ...,
Q
h
0
+c+1,c
], where Q
jc
has m
columns, j =0, 1,...,h
0
+ c +1.
For any j,1 j h
0
+ c − 1, let Q
j,c−1
=
¯
P
τ
0
+c−1
Q
j,c−1
P
−1
c−1
. For any j,
0 j h
0
+ c − 1, let Q
j,c−1
=
Q
1
j,c−1
Q
3
j,c−1
Q
2
j,c−1
Q
4
j,c−1
,or
Q
1
j
Q
3
j
Q
2
j
Q
4
j
for short, where
4.2 Composition of R
a
R
b
Transformations 119
Q
1
j,c−1
and Q
4
j,c−1
are ¯r
τ
0
+c
× r
c
and (m− ¯r
τ
0
+c
) × (m
− r
c
) matrices,
respectively. We prove Q
3
0,c−1
=0andQ
h
0
+c+1,c
=0.SinceQ
0,c−1
is the
reduced echelon matrix of Q
0,c−1
P
−1
c−1
, from the definition of ¯r
τ
0
+c
,wehave
Q
3
0,c−1
= 0. Clearly,
R
3
R
4
R
5
=
Q
0,c−1
Q
1,c−1
... Q
h
0
+c−1,c−1
00
0 Q
0,c−1
... Q
h
0
+c−2,c−1
Q
h
0
+c−1,c−1
0
.
Therefore, we have
R
2
R
3
R
4
R
5
R
6
=
Q
4
0
Q
3
1
Q
4
1
Q
3
2
... Q
4
h
0
+c−1
0000Q
3
0
0 Q
1
0
Q
2
0
Q
1
1
... Q
2
h
0
+c−2
Q
1
h
0
+c−1
Q
2
h
0
+c−1
000
.
Let R
2
R
3
R
4
R
5
R
6
=[
¯
Q
0c
, ...,
¯
Q
h
0
+c+1,c
], where
¯
Q
jc
has m
columns, j =0,
1, ..., h
0
+c+1. Since Q
3
0,c−1
= 0 yields
¯
Q
h
0
+c+1,c
=0,weobtain
¯
Q
h
0
+c+1,c
=
0andQ
h
0
+c+1,c
= R
1
¯
Q
h
0
+c+1,c
E
m
,−r
c
=0.
We prove that (4.20) is an R
a
R
b
transformation sequence. It is suffi-
cient to prove that the last m − ¯r
τ
0
+c
rows of
¯
P
τ
0
+c−1
C
0,τ
0
+c−1
are 0. Let
C
0,τ
0
+c−1
=
¯
P
τ
0
+c−1
C
0,τ
0
+c−1
. Since (4.18) yields C
0,τ
0
+c−1
= Q
0,c−1
F
0,c−1
,
we have
C
0,τ
0
+c−1
=
¯
P
τ
0
+c−1
Q
0,c−1
F
0,c−1
=(
¯
P
τ
0
+c−1
Q
0,c−1
P
−1
c−1
)(P
c−1
F
0,c−1
)
= Q
0,c−1
F
0,c−1
.
Since Q
3
0,c−1
=0andthelastm
− r
c
rows of F
0,c−1
are 0, the last m− ¯r
τ
0
+c
rows of C
0,τ
0
+c−1
are 0.
To prove [C
0,τ
0
+c
,...,C
h+c,τ
0
+c
]=[Q
0c
,...,Q
h
0
+c,c
]Γ
c
h+c+1
, using (4.19),
it is easy to verify that R
−1
5
Γ
c−1
h+c+2
equals
⎡
⎢
⎢
⎢
⎣
F
0,c−1
F
1,c−1
··· ··· F
h
1
,c−1
F
0,c−1
F
1,c−1
··· ··· F
h
1
,c−1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
F
0,c−1
F
1,c−1
··· ··· F
h
1
,c−1
⎤
⎥
⎥
⎥
⎦
and R
−1
7
R
−1
6
R
−1
5
Γ
c−1
h+c+2
=
0
G
Γ
c
h+c+1
G
for some matrices G
and G
with m
rows. Since Q =[Q
0c
, ..., Q
h
0
+c+1,c
]andQ
h
0
+c+1,c
=0,wehave
QR
−1
7
R
−1
6
R
−1
5
Γ
c−1
h+c+2
=[Q
0c
,...,Q
h
0
+c,c
][0,Γ
c
h+c+1
]. (4.21)
From (4.20) and C
h+j,τ
0
+c−1
=0forj>0, we have
120 4. Relations Between Transformations
R
1
R
2
R
3
C
0,τ
0
+c−1
C
1,τ
0
+c−1
... C
h+c−1,τ
0
+c−1
00
0 C
0,τ
0
+c−1
... C
h+c−2,τ
0
+c−1
C
h+c−1,τ
0
+c−1
0
= R
1
R
2
C
0,τ
0
+c−1
C
1,τ
0
+c−1
... C
h+c−1,τ
0
+c−1
00
0 C
0,τ
0
+c−1
... C
h+c−2,τ
0
+c−1
C
h+c−1,τ
0
+c−1
0
=
0 C
0,τ
0
+c
... C
h+c−2,τ
0
+c
C
h+c−1,τ
0
+c
0
(4.22)
and C
h+j,τ
0
+c
=0forj>0. On the other hand, from (4.18), we obtain
R
1
R
2
R
3
C
0,τ
0
+c−1
C
1,τ
0
+c−1
... C
h+c−1,τ
0
+c−1
00
0 C
0,τ
0
+c−1
... C
h+c−2,τ
0
+c−1
C
h+c−1,τ
0
+c−1
0
= R
1
R
2
R
3
R
4
Γ
c−1
h+c+2
= R
1
R
2
R
3
R
4
R
5
R
6
R
7
R
−1
7
R
−1
6
R
−1
5
Γ
c−1
h+c+2
= QR
−1
7
R
−1
6
R
−1
5
Γ
c−1
h+c+2
.
Using (4.22) and (4.21), it follows immediately that
[0,C
0,τ
0
+c
,...,C
h+c,τ
0
+c
]=QR
−1
7
R
−1
6
R
−1
5
Γ
c−1
h+c+2
=[Q
0c
,...,Q
h
0
+c,c
][0,Γ
c
h+c+1
],
where C
h+c,τ
0
+c
= 0. Therefore,
[C
0,τ
0
+c
,...,C
h+c,τ
0
+c
]=[Q
0c
,...,Q
h
0
+c,c
]Γ
c
h+c+1
.
Finally, we prove that the rank of Q
0c
is not less than the rank of Q
0,c−1
.
It is easy to see that the rank of Q
0,c−1
is equal to the rank of Q
0,c−1
.
From Q
0c
= R
1
¯
Q
0c
E
m
,−r
c
, the rank of Q
0c
is equal to the rank of
¯
Q
0c
.Since
Q
0,c−1
=
Q
1
0,c−1
0
Q
2
0,c−1
Q
4
0,c−1
and ¯r
τ
0
+c
is the rank of
Q
1
0,c−1
0
,therowsofQ
1
0,c−1
are linearly independent. It follows that the rank of Q
0,c−1
is equal to the
sum of the rank of Q
1
0,c−1
and the rank of Q
4
0,c−1
. On the other hand,
¯
Q
0c
=
Q
4
0,c−1
0
Q
3
1,c−1
Q
1
0,c−1
deduces that the rank of
¯
Q
0c
is equal to or greater than the
sum of the rank of Q
1
0,c−1
and the rank of Q
4
0,c−1
. Therefore, the rank of
¯
Q
0c
is equal to or greater than the rank of Q
0,c−1
. It follows that the rank of Q
0c
is equal to or greater than the rank of Q
0,c−1
.
Theorem 4.2.1.
Let
[C
00
,...,C
h0
]=[B
00
,...,B
h
0
0
]Γ
0
h+1
. (4.23)
Assume that
0eq
c
(i)
R
a
[P
c
]
−→ 0eq
c
(i), 0eq
c
(i)
R
b
[r
c+1
]
−→ 0eq
c+1
(i),c=0, 1,...,τ
0
− 1 (4.24)
4.2 Composition of R
a
R
b
Transformations 121
and
1eq
c
(i)
R
a
[P
c
]
−→ 1eq
c
(i), 1eq
c
(i)
R
b
[r
c+1
]
−→ 1eq
c+1
(i),c=0, 1,...,τ
1
− 1 (4.25)
are two R
a
R
b
transformation sequences. Then there exist an R
a
R
b
trans-
formation sequence
eq
c
(i)
R
a
[
¯
P
c
]
−→ eq
c
(i),eq
c
(i)
R
b
[¯r
c+1
]
−→ eq
c+1
(i),c=0, 1,...,τ − 1
and m × m
matrices Q
0τ
1
, ..., Q
h
0
+τ
1
,τ
1
over GF (q) such that
[C
0τ
,...,C
h+τ
1
,τ
]=[Q
0τ
1
,...,Q
h
0
+τ
1
,τ
1
]Γ
τ
1
h+τ
1
+1
(4.26)
and the rank of Q
0τ
1
is not less than the rank of B
0τ
0
in 0eq
τ
0
(i), where
τ = τ
0
+τ
1
,C
h+j,τ
=0for j>0.Therefore, iftherankofB
0τ
0
is min(m, m
),
then the rank of Q
0τ
1
is min(m, m
).
Proof. From (4.23), (4.12) for c = 1 in Lemma 4.2.1 holds, where F
j
= F
j0
,
j =0, 1,...,h
1
. From (4.24), using Lemma 4.2.1 τ
0
times, c from 1 to τ
0
,we
obtain
eq
c
(i)
R
a
[P
c
]
−→ eq
c
(i),eq
c
(i)
R
b
[r
c+1
]
−→ eq
c+1
(i),c=0, 1,...,τ
0
− 1 (4.27)
and
[C
0τ
0
,...,C
hτ
0
]=[B
0τ
0
,...,B
h
0
τ
0
]Γ
0
h+1
. (4.28)
Let Q
j0
= B
jτ
0
for any j,0 j h
0
. Then the rank of B
0τ
0
is the rank
of Q
00
. Clearly, (4.28) yields (4.18) for c = 1 in Lemma 4.2.2. From (4.25),
using Lemma 4.2.2 τ
1
times, c from 1 to τ
1
, we obtain that there exist
eq
c
(i)
R
a
[
¯
P
c
]
−→ eq
c
(i),eq
c
(i)
R
b
[¯r
c+1
]
−→ eq
c+1
(i),c= τ
0
,τ
0
+1,...,τ − 1 (4.29)
and Q
0τ
1
, ..., Q
h
0
+τ
1
,τ
1
such that (4.26) holds and the rank of Q
0τ
1
is not
less than the rank of Q
00
,whereτ = τ
0
+ τ
1
, C
h+j,τ
=0forj>0. Thus the
rank of Q
0τ
1
is not less than the rank of B
0τ
0
. Letting
¯
P
j
= P
j
and ¯r
j
= r
j
for any j,0 j τ
0
− 1, from (4.27) and (4.29),
eq
c
(i)
R
a
[
¯
P
c
]
−→ eq
c
(i),eq
c
(i)
R
b
[¯r
c+1
]
−→ eq
c+1
(i),c=0, 1,...,τ − 1
is an R
a
R
b
transformation sequence. This completes the proof of the theo-
rem.
Let M
0
= Y
, Y , Y
k
× Y
h
0
, δ
0
, λ
0
be a special h
0
-quasi-linear finite
automaton defined by
122 4. Relations Between Transformations
y
i
= ϕ
out
(y(i − 1,k)) + [B
0
,...,B
h
0
]
⎡
⎢
⎣
y
i
.
.
.
y
i−h
0
⎤
⎥
⎦
,i=0, 1,... (4.30)
Let M
1
= X, Y
,U
p+1
× X
h
1
,δ
1
,λ
1
be a pseudo-memory finite automa-
tondefinedby
y
i
= f(u(i, p +1),x(i, h
1
+1)),
u
i+1
= g(u(i, p +1),x(i, h
1
+1)), (4.31)
i =0, 1,...,
and suppose that f can be expressed in the form
f(u(i, p +1),x(i, h
1
+1))=[F
0
,...,F
h
1
]ψ
lh
1
μν
(u, x, i).
Let h = h
0
+ h
1
and
[C
0
,C
1
,...,C
h
]=[B
0
,B
1
,...,B
h
0
]Γ
h+1
, (4.32)
where Γ
h+1
is defined by (4.11).
From M
0
and M
1
, a finite automaton X, Y, Y
k
× U
p+1
× X
h
,δ,λ is
defined by
y
i
= ϕ
out
(y(i − 1,k)) + [C
0
,...,C
h
]ψ
lh
μν
(u, x, i),
u
i+1
= g(u(i, p +1),x(i, h
1
+1)),
i =0, 1,...
Theorem 4.2.2. Let M
0
and M
1
be finite automata defined by (4.30) and
(4.31), respectively. Let 1eq
0
(i) be equivalent to the equation
−y
i
+[F
0
,...,F
h
1
]ψ
lh
1
μν
(u, x, i)=0,
and eq
0
(i) be equivalent to the equation
−y
i
+ ϕ
out
(y(i − 1,k)) + [C
0
,...,C
h
]ψ
lh
μν
(u, x, i)=0. (4.33)
Assume that (4.25) is an R
a
R
b
transformation sequence.
(a) If F
0τ
1
ψ
l
μν
(u(i, μ +1),x(i, ν +1)) in 1eq
τ
1
(i) as a function of the
variable x
i
is an injection and M
0
is weakly invertible with delay τ
0
,thenfor
any linear R
a
R
b
transformation sequence
eq
c
(i)
R
a
[P
c
]
−→ eq
c
(i),eq
c
(i)
R
b
[r
c+1
]
−→ eq
c+1
(i),c=0, 1,...,τ − 1 (4.34)
with τ = τ
0
+ τ
1
,C
0τ
ψ
l
μν
(u(i, μ +1),x(i, ν +1)) in eq
τ
(i) as a function of
the variable x
i
is an injection.