Tao R. Finite Automata and Application to Cryptography
Подождите немного. Документ загружается.
5.3 One Step Delay 163
|X| = |Y |.ThenM is weakly invertible with delay 1 if and only if there exist
single-valued mappings ϕ
x
−c
,...,x
−2
,s
a
from X to Y
w
,x
−c
,...,x
−2
∈ X, s
a
∈
S
a
such that (a) for any x
−c
,...,x
−2
∈ X and any s
a
∈ S
a
, P
ϕ
x
−c
,...,x
−2
,s
a
is
non-empty, and (b) for any x
−c
,...,x
−1
∈ X and any s
a
∈ S
a
, there exists
ψ
x
−c
,...,x
−1
,s
a
∈ P
ϕ
x
−c+1
,...,x
−1
,δ
a
(s
a
)
such that
f(x
0
,x
−1
,...,x
−c
,s
a
)=m(ψ
x
−c
,...,x
−1
,s
a
(x
0
),ϕ
x
−c
,...,x
−2
,s
a
(x
−1
)) (5.1)
holds for any x
0
∈ X. Moreover, whenever the above condition holds, w in
the condition is equal to w
1,M
.
Proof. only if : from Lemma 5.3.3.
if and w = w
1,M
: from Lemma 5.3.4.
Remark Inthecaseofw
1,M
= 1, in the condition (b), we have
ψ
x
−c
,...,x
−1
,s
a
(x
0
) = 1. Therefore, the equation (5.1) can be simplified into
f(x
0
,x
−1
,...,x
−c
,s
a
)=ϕ
x
−c
,...,x
−2
,s
a
(x
−1
).
Meanwhile, the condition (a) is equivalent to the condition: for any x
−c
,...,
x
−2
∈ X and any s
a
∈ S
a
, ϕ
x
−c
,...,x
−2
,s
a
is a surjection (or an injection, or a
bijection).
In the case of w
1,M
= |X|, ϕ
x
−c
,...,x
−2
,s
a
(x
−1
)=Y and ψ
x
−c
,...,x
−1
,s
a
is
bijective. It follows that the right-side of the equation (5.1) as a function
of x
0
defines a bijection from X to Y . In this case, the condition in Theo-
rem 5.3.1 is equivalent to the condition: for any x
−c
,...,x
−1
∈ X and any
s
a
∈ S
a
, f(x
0
,x
−1
,...,x
−c
,s
a
) as a function of x
0
is a bijection from X to Y .
Therefore, this case degenerates to the case of weakly invertible with delay
0.
To sum up, for the cases of w
1,M
=1, |X|, the expressions of semi-input-
memory finite automata with strongly cyclic autonomous finite automata are
very succinct, and their synthesization is clear. Below we present synthesizing
method for the case where w
1,M
is a proper divisor of |X| other than 1.
Synthesizing method Given |X| = |Y | = q, c 1 and a strongly cyclic
autonomous finite automaton M
a
= Y
a
,S
a
,δ
a
,λ
a
. Suppose that w|q and
w =1,q. Find f, a single-valued mapping from X
c+1
× S
a
to Y , such that
SIM(M
a
,f) is weakly invertible with delay 1.
Step 1. For any x
−c
,...,x
−2
∈ X and any s
a
∈ S
a
, choose arbitrarily a
single-valued mapping ϕ
x
−c
,...,x
−2
,s
a
from X to Y
w
, of which a valid par-
tition is existent, that is, there exists a single-valued mapping ψ from X to
{1,...,w} such that for any j,1 j w, |ψ
−1
(j)| = |X|/w and
x∈ψ
−1
(j)
ϕ
x
−c
,...,x
−2
,s
a
(x)=Y . Denote the set of all valid partitions of ϕ
x
−c
,...,x
−2
,s
a
by P
ϕ
x
−c
,...,x
−2
,s
a
.
164 5. Structure of Feedforward Inverses
Step 2. For any x
−c
,...,x
−1
∈ X and any s
a
∈ S
a
, choose arbitrarily a
valid partition, say ψ
x
−c
,...,x
−1
,s
a
,inP
ϕ
x
−c+1
,...,x
−1
,δ
a
(s
a
)
.
Step 3. Define
f(x
0
,x
−1
,...,x
−c
,s
a
)=m(ψ
x
−c
,...,x
−1
,s
a
(x
0
),ϕ
x
−c
,...,x
−2
,s
a
(x
−1
))
for x
−c
,...,x
1
,x
0
∈ X, s
a
∈ S
a
,wherem(j, T ) denotes the j-th element in
T . (The order of elements of T ⊆ Y is naturally induced by a given order of
elements in Y .)
According to Theorem 5.3.1, each SIM(M
a
,f) obtained by the above
synthesizing method is weakly invertible with delay 1, and all c-order semi-
input-memory finite automata with strongly cyclic autonomous finite au-
tomata which are weakly invertible with delay 1 can be found by the above
synthesizing method.
Example 5.3.1. Let X = Y = {0, 1, 2, 3}. Take c 1, w = 2. Suppose that
M
a
= Y
a
,S
a
,δ
a
,λ
a
is a strongly cyclic autonomous finite automaton. Find
a single-valued mapping from X
c+1
× S
a
to Y ,sayf , such that SIM(M
a
,f)
is weakly invertible with delay 1.
According to the synthesizing method mentioned above, for any x
−c
,...,
x
−2
∈ X and any s
a
∈ S
a
, we define ϕ
x
−c
,...,x
−2
,s
a
(x)=ϕ(x), where ϕ(x)=
{0, 1} if x =0, 2, ϕ(x)={2, 3} if x =1, 3. Define ψ
i
as in Table 5.3.1.
Table 5.3.1 Definition of ψ
i
xψ
1
(x) ψ
2
(x) ψ
3
(x) ψ
4
(x)
01122
11221
22211
32112
It is easy to verify that ψ
1
, ψ
2
, ψ
3
and ψ
4
are all valid partitions of ϕ.For
any x
−c
,...,x
−1
∈ X and any s
a
∈ S
a
, take ψ
x
−c
,...,x
−1
,s
a
= ψ
1
if x
−c
=0,
or ψ
2
if x
−c
=0.TakeanorderforelementsinY : the first to the fourth
elements are 0, 1, 2, 3. We then have
f(x
0
,x
−1
,...,x
−c
,s
a
)=
m(ψ
1
(x
0
),ϕ(x
−1
)), if x
−c
=0,
m(ψ
2
(x
0
),ϕ(x
−1
)), if x
−c
=0.
It follows that
5.4 Two Step Delay 165
f(x
0
,x
−1
,...,x
−c
,s
a
)=
⎧
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎩
0, if x
−c
=0,x
−1
=0, 2,x
0
=0, 1,
1, if x
−c
=0,x
−1
=0, 2,x
0
=2, 3,
2, if x
−c
=0,x
−1
=1, 3,x
0
=0, 1,
3, if x
−c
=0,x
−1
=1, 3,x
0
=2, 3,
0, if x
−c
=0,x
−1
=0, 2,x
0
=0, 3,
1, if x
−c
=0,x
−1
=0, 2,x
0
=1, 2,
2, if x
−c
=0,x
−1
=1, 3,x
0
=0, 3,
3, if x
−c
=0,x
−1
=1, 3,x
0
=1, 2.
Theorem 5.3.2. Let M = X, Y, S, δ, λ be a c-order semi-input-memory
finite automaton SIM(M
a
,f),M
a
= Y
a
,S
a
,δ
a
,λ
a
be strongly cyclic, and
|X| = |Y |.ThenM is a feedforward inverse with delay 1 if and only if
there exist single-valued mappings ϕ
x
−c
,...,x
−2
,s
a
,x
−c
,..., x
−2
∈ X, s
a
∈ S
a
from X to Y
w
such that (a) for any x
−c
,...,x
−2
∈ X and any s
a
∈ S
a
,
P
ϕ
x
−c
,...,x
−2
,s
a
is non-empty, and (b) for any x
−c
,...,x
−1
∈ X and any s
a
∈
S
a
, there exists ψ
x
−c
,...,x
−1
,s
a
∈ P
ϕ
x
−c+1
,...,x
−1
,δ
a
(s
a
)
such that (5.1) holds for
any x
0
∈ X. Moreover, whenever the above condition holds,win the condition
is equal to w
1,M
.
Proof.SinceM, i.e. SIM(M
a
,f), is a semi-input-memory finite automa-
ton and M
a
is strongly cyclic, M is strongly connected. Using Theorem 2.2.2,
M is a feedforward inverse with delay 1 if and only if M is weakly invertible
with delay 1. From Theorem 5.3.1, the theorem holds.
It should be pointed out that any SIM(M
a
,f) can be expressed as
SIM(
¯
M
a
,
¯
f) such that the output function of
¯
M
a
is the identity function. In
fact, let M
a
= Y
a
,S
a
,δ
a
,λ
a
. Take
¯
M
a
= S
a
,S
a
,δ
a
,
¯
λ
a
,where
¯
λ
a
(s
a
)=s
a
for any s
a
∈ S
a
. Take
¯
f(x
0
, x
−1
, ..., x
−c
, s
a
)=f (x
0
,x
−1
,...,x
−c
,λ
a
(s
a
)).
Then SIM(
¯
M
a
,
¯
f)=SIM(
¯
M
a
,
¯
f).
5.4 Two Step Delay
For any finite automaton M = X, Y, S, δ,λ and any state s of M, if for any
α = x
0
...x
l
of length l +1inX
∗
, x
0
can be uniquely determined by s and
λ(s, α), s is called a l-step state;forl>0, if s is a l-step state and not
a (l − 1)-step state, s is called an l-step state;ifs is a 0-step state, s is
called a 0-step state. Clearly, if M is weakly invertible with delay τ and s is
a state of M,thens is an l-step state for some l,0 l τ .
Lemma 5.4.1. Let M = X, Y, S, δ, λ be a finite automaton, and |X| =2.
Let |W
M
2,s
| =2.Ifs is a 0-step state and s
a successor state of s,thens
is
not a 0-step state.
166 5. Structure of Feedforward Inverses
Proof. Assume that s is a 0-step state and s
a successor state of s.We
prove by reduction to absurdity that s
is not a 0-step state. Suppose to the
contrary that s
is a 0-step state. Since s and s
are 0-step states, we have
|λ(s, X)| = |λ(s
,X)| =2.Sinces
is a successor state of s, it is easy to see
that |W
M
2,s
| 3. This contradicts |W
M
2,s
| = 2. We conclude that s
is not a
0-step state.
Lemma 5.4.2. Let M = X, Y, S, δ, λ be a finite automaton, and |X| =2.
(a) If s in S is a 1-step state and s
a successor state of s,thens
is not
a 0-step state.
(b) Let s
and s
be two different successor states of s ∈ S.Ifs, s
and
s
are not 0-step states and |W
M
2,s
| =2,then|λ(s
,X)| = |λ(s
,X)| =1and
λ(s
,X) = λ(s
,X),therefore,s is a 1-step state.
Proof. (a) Assume that s in S is a 1-step state and s
a successor state of
s. We prove by reduction to absurdity that s
is not a 0-step state. Suppose to
the contrary that s
is a 0-step state. Since s is a 1-step state and s
a0-step
state, we have |λ(s, X)| =1and|λ(s
,X)| =2.Sinces
is a successor state
of s, it is easy to see that there exist x
0
,x
0
,x
1
,x
1
∈ X such that x
0
= x
0
and
λ(s, x
0
x
1
)=λ(s, x
0
x
1
). This contradicts that s is a 1-step state. We conclude
that s
is not a 0-step state.
(b) Since s, s
and s
are not 0-step states, we have |λ(s, X)| = |λ(s
,X)| =
|λ(s
,X)| =1.From|W
M
2,s
| = 2, it follows that λ(s
,X) = λ(s
,X). There-
fore, s is a 1-step state.
Lemma 5.4.3. Let M = X, Y, S, δ,λ be weakly invertible with delay 2,
and w
2,M
= |X| = |Y | =2.LetS
0
= {s|s ∈ S, |W
M
2,s
| = w
2,M
}.
(a) If s
and s
are two different successor states of s ∈ S
0
,thens
is a
0-step state if and only if s
is a 0-step state.
(b) If s in S
0
is a 2-step state and s
a successor state of s,thens
is a
0-step state.
Proof. (a) Assume that s
and s
are two different successor states of
s ∈ S
0
. We prove by reduction to absurdity that s
is a 0-step state if and
only if s
is a 0-step state. Suppose to the contrary that one state in {s
,s
}
is a 0-step state and the other is not. Without loss of generality, suppose
that s
is a 0-step state and s
is not. Then we have |λ(s
,X)| =2and
|λ(s
,X)| =1.Sinces
and s
are two different successor states of s and
|w
M
2,s
| =2,wehave|λ(s, X)| = 1. (Otherwise, we obtain |w
M
2,s
| =3,which
contradicts s ∈ S
0
.) Since s is in S
0
, from Theorem 2.1.3 (b), s
is in S
0
.Thus
we have λ(s
3
,X)∪λ(s
4
,X)=Y ,wheres
3
and s
4
are two different successors
of s
.Letx
1
in X satisfy λ(s
,x
1
)=λ(s
,x
1
). Since s
is a 0-step state, such
an x
1
is existent. Denote s
1
= δ(s
,x
1
). From λ(s
3
,X) ∪ λ(s
4
,X)=Y ,we
5.4 Two Step Delay 167
can find x
2
and x
2
in X and s
in {s
3
,s
4
} such that λ(s
1
,x
2
)=λ(s
,x
2
).
Let x
0
, x
0
, x
1
in X satisfy s
= δ(s, x
0
), s
= δ(s, x
0
)ands
= δ(s
,x
1
).
Then x
0
= x
0
and λ(s, x
0
x
1
x
2
)=λ(s, x
0
x
1
x
2
). This contradicts that M is
weakly invertible with delay 2. We conclude that s
is a 0-step state if and
only if s
is a 0-step state.
(b) Assume that s in S
0
is a 2-step state and s
a successor state of s.
We prove by reduction to absurdity that s
is a 0-step state. Suppose to the
contrary that s
is not a 0-step state. Then |λ(s
,X)| =1.Sinces is a 2-step
state, we have |λ(s, X)| =1.Lets
be a successor state of s other than
s
.From(a),s
is not a 0-step state. Thus |λ(s
,X)| =1.Froms ∈ S
0
,
we obtain λ(s
,X) ∩ λ(s
,X)=∅. It immediately follows that s is a 1-step
state. This contradicts that s is a 2-step state. We conclude that s
is a 0-step
state.
Lemma 5.4.4. Let M = X, Y, S, δ,λ be a weakly invertible finite automa-
ton with delay 2.Letw
2,M
= |X| = |Y | =2and S
0
= {s|s ∈ S, |W
M
2,s
| =
w
2,M
}.
(a) Let s and s
be two different successor states of s
−1
∈ S
0
.Lets
1
and s
2
be two different successor states of s,ands
1
and s
2
be two different
successor states of s
. Assume that s
1
and s
2
are not 0-step states and s
is a 0-step state. Then s
1
and s
2
are not 0-step states and s
is a 0-step
state. Moreover, λ(s
1
,X)=λ(s
2
,X) if and only if λ(s
1
,X)=λ(s
2
,X);if
λ(s
1
,X)=λ(s
2
,X),thenλ(s
1
,X)=λ(s
2
,X) = λ(s
1
,X);andifλ(s
1
,X) =
λ(s
2
,X),thenλ(s
1
,X)=λ(s
1
,X) if and only if λ(s, x
1
) = λ(s
,x
1
),where
x
1
and x
1
in X satisfy δ(s, x
1
)=s
1
and δ(s
,x
1
)=s
1
.
(b) Let s
1
and s
2
be two different successor states of s,ands
1
and s
2
be
two different successor states of s
,wheres and s
are two different successor
states of a state in S
0
.Ifλ(s
1
,X)=λ(s
2
,X) and |λ(s
1
,X)| =1,then
|λ(s
1
,X)| =1and λ(s
1
,X)=λ(s
2
,X) = λ(s
1
,X).
Proof. (a) Since s is a 0-step state, using Lemma 5.4.3 (a), s
is a 0-step
state. Since s is a 0-step state, using Lemma 5.4.1 and Lemma 5.4.2 (a), s
−1
is a 2-step state. We prove that s
1
and s
2
are not 0-step states. For any i ∈
{1, 2},sinces
a successor state of s
−1
and s
i
a successor state of s
,there
exist x
0
, x
1
∈ X such that δ(s
−1
,x
0
)=s
and δ(s
−1
,x
0
x
1
)=s
i
.Sinces
−1
is
a 2-step state and s a 0-step state, there exist x
0
, x
1
∈ X such that x
0
= x
0
and λ(s
−1
,x
0
x
1
)=λ(s
−1
,x
0
x
1
). Clearly, δ(s
−1
,x
0
x
1
)=s
j
for some j ∈
{1, 2}.SinceM is weakly invertible with delay 2, λ(s
j
,X) ∩ λ(s
i
,X)=∅.
It immediately follows that |λ(s
i
,X)| =1,thatis,s
i
is not a 0-step state.
Denote λ(s
i
,X)={e
i
} and λ(s
i
,X)={e
i
} for i =1, 2. Suppose e
1
= e
2
.
We prove by reduction to absurdity that e
1
= e
2
= e
1
,thatis,e
i
= e
1
for
i =1, 2. Suppose to the contrary that e
i
= e
1
for some i ∈{1, 2}.Sinces
−1
is
168 5. Structure of Feedforward Inverses
a 2-step state and s is a 0-step state, there exist x
0
, x
1
, x
0
, x
1
∈ X such that
x
0
= x
0
, λ(s
−1
,x
0
x
1
)=λ(s
−1
,x
0
x
1
), δ(s
−1
,x
0
)=s and δ(s
−1
,x
0
x
1
)=s
i
.
Let δ(s
−1
,x
0
x
1
)=s
j
. Noticing e
1
= e
2
,wehavee
j
= e
i
,thatis,λ(s
j
,x
2
)=
λ(s
i
,x
2
) for any x
2
∈ X. It follows that λ(s
−1
,x
0
x
1
x
2
)=λ(s
−1
,x
0
x
1
x
2
).
This contradicts that s
−1
is a 2-step state. We conclude that e
1
= e
2
= e
1
.
Using this result, we obtain that e
1
= e
2
implies e
1
= e
2
. From symmetry,
e
1
= e
2
implies e
1
= e
2
. Therefore, e
1
= e
2
if and only if e
1
= e
2
.
Suppose e
1
= e
2
.Wethenhavee
1
= e
2
. It follows that there exists
i ∈{1, 2} such that e
1
= e
i
.Letx
1
, x
1
and x
2
∈ X satisfy δ(s, x
1
)=s
1
and
δ(s
,x
j
)=s
j
, j =1, 2. We prove by reduction to absurdity that λ(s, x
1
) =
λ(s
,x
i
). Suppose to the contrary that λ(s, x
1
)=λ(s
,x
i
). Since e
1
= e
i
,
for any x
2
∈ X we have λ(s
1
,x
2
)=λ(s
i
,x
2
). It follows that λ(s, x
1
x
2
)=
λ(s
,x
i
x
2
). Since s and s
be two different successor states of s
−1
and s
−1
is
a 2-step state, we obtain λ(s
−1
,x
0
x
1
x
2
)=λ(s
−1
,x
0
x
i
x
2
), where x
0
and x
0
are different elements in X satisfying δ(s
−1
,x
0
)=s and δ(s
−1
,x
0
)=s
.This
contradicts that s
−1
is a 2-step state. We conclude that λ(s, x
1
) = λ(s
,x
i
).
Inthecaseofe
1
= e
1
,wehavei = 1. This yields λ(s, x
1
) = λ(s
,x
1
). In
the case of e
1
= e
1
,wehavei = 2. This yields λ(s, x
1
) = λ(s
,x
2
). Since
s
is a 0-step state, we have λ(s
,x
1
) = λ(s
,x
2
). Thus λ(s, x
1
)=λ(s
,x
1
).
Therefore, e
1
= e
1
if and only if λ(s, x
1
) = λ(s
,x
1
).
(b) Suppose that λ(s
1
,X)=λ(s
2
,X)and|λ(s
1
,X)| =1.Thens
1
and s
2
are not 0-step states. Since s is a successor state of a state in S
0
,fromTheo-
rem 2.1.3 (b), s is a state in S
0
,thatis,|W
M
2,s
| = 2. From Lemma 5.4.2 (b), s
is a 0-step state. From (a), s
1
is not a 0-step state. Thus |λ(s
1
,X)| =1.Since
λ(s
1
,X)=λ(s
2
,X), using (a), we obtain λ(s
1
,X)=λ(s
2
,X) = λ(s
1
,X).
Lemma 5.4.5. Let M = X,Y, S, δ,λ be a c-order semi-input-memory fi-
nite automaton SIM(M
a
,f),andM
a
= Y
a
,S
a
,δ
a
,λ
a
be strongly cyclic.
If c 2=w
2,M
, X = Y = {0, 1} and M is weakly invertible with delay 2,
then there exist single-valued mappings h
0
from X
c−1
× S
a
to {0, 1}, h
1
from
X
c−2
× S
a
to {0, 1}, f
0
from X
c
× S
a
to Y , f
1
from X
c−1
× S
a
to Y ,andf
2
from X
c−2
× S
a
to Y , such that
h
0
(x
−2
,...,x
−c
,s
a
)=0→ h
0
(x
−1
,...,x
−c+1
,δ
a
(s
a
)) = 1,
h
1
(x
−3
,...,x
−c
,s
a
)=1→ h
0
(x
−3
,...,x
−c−1
,δ
−1
a
(s
a
)) = 0, (5.2)
and
5.4 Two Step Delay 169
f(x
0
,...,x
−c
,s
a
)
=
⎧
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎩
f
2
(x
−3
,...,x
−c
,s
a
) ⊕ x
−2
,
if h
0
(x
−2
,...,x
−c
,s
a
)=1&h
1
(x
−3
,...,x
−c
,s
a
)=1,
f
1
(x
−2
,...,x
−c
,s
a
) ⊕ x
−1
,
if h
0
(x
−2
,...,x
−c
,s
a
)=1&h
1
(x
−3
,...,x
−c
,s
a
)=0,
f
0
(x
−1
,...,x
−c
,s
a
) ⊕ x
0
,
if h
0
(x
−2
,...,x
−c
,s
a
)=0&h
1
(x
−2
,...,x
−c+1
,δ
a
(s
a
)) = 1,
f
1
(x
−2
,...,x
−c
,s
a
) ⊕ x
0
⊕ x
−1
⊕ x
−1
h
2
(x
−2
,...,x
−c+1
,δ
a
(s
a
)),
if h
0
(x
−2
,...,x
−c
,s
a
)=0&h
1
(x
−2
,...,x
−c+1
,δ
a
(s
a
)) = 0,
(5.3)
where
h
2
(x
−3
,...,x
−c
,s
a
)=f
1
(0,x
−3
,...,x
−c
,s
a
)⊕f
1
(1,x
−3
,...,x
−c
,s
a
). (5.4)
Proof. Define
f
0
(x
−1
,...,x
−c
,s
a
)=f(0,x
−1
,...,x
−c
,s
a
),
f
1
(x
−2
,...,x
−c
,s
a
)=f(0, 0,x
−2
,...,x
−c
,s
a
),
f
2
(x
−3
,...,x
−c
,s
a
)=f(0, 0, 0,x
−3
,...,x
−c
,s
a
).
Define h
0
and h
1
as follows. h
0
(x
−2
,...,x
−c
,s
a
) = 1 if and only if 0,x
−2
,...,
x
−c
, s
a
is not a 0-step state. h
1
(x
−3
,...,x
−c
,s
a
) = 1 if and only if
f(x
0
,x
−1
, 0, x
−3
, ...,x
−c
,s
a
)doesnotdependonx
−1
and x
0
.SinceM is a
semi-input-memory finite automaton SIM(M
a
,f)andM
a
is strongly cyclic,
M is strongly connected. From Theorem 2.1.3 (f), it follows that |W
M
2,s
| =2
holds for any state s of M . From Lemma 5.4.4 (b), h
1
(x
−3
,...,x
−c
,s
a
)=1
if and only if f(x
0
,x
−1
, 1,x
−3
,...,x
−c
,s
a
) does not depend on x
−1
and x
0
.
To prove h
0
(x
−2
,...,x
−c
,s
a
)=0→ h
0
(x
−1
,...,x
−c+1
,δ
a
(s
a
)) = 1, sup-
pose h
0
(x
−2
, ..., x
−c
, s
a
) = 0. Since M is weakly invertible with delay 2,
any state of M is a j-step state for some j,0 j 2. From the defin-
ition of h
0
, 0,x
−2
,...,x
−c
,s
a
is a 0-step state. Using Lemma 5.4.3 (a),
this yields that 1,x
−2
,...,x
−c
,s
a
is a 0-step state. From Lemma 5.4.1,
x
0
,x
−1
,...,x
−c+1
,δ
a
(s
a
) is not a 0-step state for any x
−1
, x
0
∈ X.There-
fore, h
0
(x
−1
,...,x
−c+1
,δ
a
(s
a
)) = 1.
To prove h
1
(x
−3
,...,x
−c
,s
a
)=1→ h
0
(x
−3
,...,x
−c−1
,δ
−1
a
(s
a
)) = 0,
suppose h
1
(x
−3
,...,x
−c
,s
a
)=1.Thenf (x
0
,...,x
−c
,s
a
)doesnotdepend
on x
0
and x
−1
for any x
−2
∈ X. It follows that x
−1
,...,x
−c
,s
a
is not
a 0-step state for any x
−2
, x
−1
∈ X. We prove by reduction to absurdity
that h
0
(x
−3
,...,x
−c−1
,δ
−1
a
(s
a
)) = 0 holds for any x
−c−1
∈ X. Suppose to
the contrary that h
0
(x
−3
,..., x
−c−1
, δ
−1
a
(s
a
)) = 1 for some x
−c−1
∈ X.
From the definition of h
0
, 0, x
−3
, ..., x
−c−1
, δ
−1
a
(s
a
) is not a 0-step
170 5. Structure of Feedforward Inverses
state. From Lemma 5.4.3 (a), 1,x
−3
,...,x
−c−1
,δ
−1
a
(s
a
) is not a 0-step
state. Using Lemma 5.4.2 (b), we have λ(0,x
−2
,...,x
−c
,s
a
,X) = λ(1,
x
−2
, ..., x
−c
, s
a
,X). Thus f(x
0
,...,x
−c
,s
a
) depends on x
−1
. Therefore,
h
1
(x
−3
,...,x
−c
,s
a
) = 0. This contradicts h
1
(x
−3
,...,x
−c
,s
a
)=1.Wecon-
clude that h
0
(x
−3
,...,x
−c−1
,δ
−1
a
(s
a
)) = 0 holds for any x
−c−1
.
Below we prove that f can be expressed by f
0
, f
1
, f
2
, h
0
,andh
1
.There
are four cases to consider.
Case h
0
(x
−2
,...,x
−c
,s
a
)=1 & h
1
(x
−3
,...,x
−c
,s
a
)=1:
Let s
x
−2
,x
−1
= x
−1
,x
−2
,x
−3
,...,x
−c
,s
a
.Sinceh
1
(x
−3
, ..., x
−c
, s
a
)=
1, λ(s
x
−2
,x
−1
, x
0
) does not depend on x
−1
and x
0
,thatis,|λ(s
x
−2
,0
, X)| =
|λ(s
x
−2
,1
, X)| =1andλ(s
x
−2
,0
,X)=λ(s
x
−2
,1
,X). Letting e = λ(s
x
−2
,0
, 0),
we have λ(s
x
−2
,x
−1
,x
0
)=e for any x
−1
,x
0
∈ X.Let¯x
−2
∈ X \{x
−2
}.
From Lemma 5.4.4 (b), |λ(s
¯x
−2
,0
,X)| =1andλ(s
¯x
−2
,0
,X)=λ(s
¯x
−2
,1
,X) =
λ(s
x
−2
,0
,X). It follows that λ(s
¯x
−2
,x
−1
,x
0
)=e ⊕ 1 for any x
−1
,x
0
∈ X.
Therefore,
f(x
0
,x
−1
,...,x
−c
,s
a
)=λ(x
−1
,x
−2
,x
−3
,...,x
−c
,s
a
,x
0
)
= λ(0,x
−2
,x
−3
,...,x
−c
,s
a
, 0)
= λ(0, 0,x
−3
,...,x
−c
,s
a
, 0) ⊕ x
−2
= f
2
(x
−3
,...,x
−c
,s
a
) ⊕ x
−2
.
Case h
0
(x
−2
,...,x
−c
,s
a
)=1 & h
1
(x
−3
,...,x
−c
,s
a
)=0:
Since h
0
(x
−2
,...,x
−c
,s
a
) = 1, from the definition of h
0
, s
x
−2
,0
is not
a 0-step state. Using Lemma 5.4.3 (a), s
x
−2
,1
is not a 0-step state. It fol-
lows that λ(s
x
−2
,x
−1
, 0) = λ(s
x
−2
,x
−1
, 1) holds for any x
−1
∈ X.Since
h
1
(x
−3
,...,x
−c
,s
a
)=0,wehaveλ(s
x
−2
,0
, 0) = λ(s
x
−2
,1
, 0). Therefore,
f(x
0
,x
−1
,...,x
−c
,s
a
)=λ(x
−1
,x
−2
,...,x
−c
,s
a
,x
0
)
= λ(x
−1
,x
−2
,...,x
−c
,s
a
, 0)
= λ(0,x
−2
,...,x
−c
,s
a
, 0) ⊕ x
−1
= f
1
(x
−2
,...,x
−c
,s
a
) ⊕ x
−1
.
Case h
0
(x
−2
,...,x
−c
,s
a
)=0 & h
1
(x
−2
,...,x
−c+1
,δ
a
(s
a
)) = 1 :
Since h
0
(x
−2
,...,x
−c
,s
a
) = 0, from the definition of h
0
, s
x
−2
,0
is a 0-
step state. Using Lemma 5.4.3 (a), s
x
−2
,1
is a 0-step state. It follows that
λ(s
x
−2
,x
−1
,x
0
)=λ(s
x
−2
,x
−1
, 0) ⊕ x
0
. Therefore,
f(x
0
,x
−1
,...,x
−c
,s
a
)=λ(x
−1
,...,x
−c
,s
a
,x
0
)
= λ(x
−1
,...,x
−c
,s
a
, 0) ⊕ x
0
= f
0
(x
−1
,...,x
−c
,s
a
) ⊕ x
0
.
Case h
0
(x
−2
,...,x
−c
,s
a
)=0 & h
1
(x
−2
,...,x
−c+1
,δ
a
(s
a
)) = 0 :
5.4 Two Step Delay 171
Since h
0
(x
−2
,...,x
−c
,s
a
) = 0, as proven in the preceding case, s
x
−2
,0
and
s
x
−2
,1
are 0-step states. It follows that λ(s
x
−2
,x
−1
,x
0
)=λ(s
x
−2
,x
−1
, 0) ⊕ x
0
for any x
−1
,x
0
∈ X. Using Lemma 5.4.1, x
0
,x
−1
,x
−2
,...,x
−c+1
,δ
a
(s
a
),
denoted by s
x
−2
,x
−1
,x
0
, is not a 0-step state for any x
−1
,x
0
∈ X.Itfol-
lows that λ(s
x
−2
,x
−1
,x
0
, 0) = λ(s
x
−2
,x
−1
,x
0
, 1) for any x
−1
,x
0
∈ X.Onthe
other hand, from h
1
(x
−2
, ..., x
−c+1
, δ
a
(s
a
)) = 0, we have λ(s
x
−2
,x
−1
,0
, 0) =
λ(s
x
−2
,x
−1
,1
, 0) for any x
−1
∈ X. Using Lemma 5.4.4 (a), λ(s
x
−2
,0,0
, 0) =
λ(s
x
−2
,1,0
, 0) if and only if λ(s
x
−2
,0
, 0) = λ(s
x
−2
,1
, 0). It follows that
λ(s
x
−2
,0
, 0) ⊕ λ(s
x
−2
,1
, 0) = λ(s
x
−2
,0,0
, 0) ⊕ λ(s
x
−2
,1,0
, 0) ⊕ 1
= f(0, 0, 0,x
−2
,...,x
−c+1
,δ
a
(s
a
))⊕f(0, 0, 1,x
−2
,...,x
−c+1
,δ
a
(s
a
))⊕1
= f
1
(0,x
−2
,...,x
−c+1
,δ
a
(s
a
)) ⊕ f
1
(1,x
−2
,...,x
−c+1
,δ
a
(s
a
)) ⊕ 1
= h
2
(x
−2
,...,x
−c+1
,δ
a
(s
a
)) ⊕ 1.
Thus λ(s
x
−2
,0
, 0)⊕λ(s
x
−2
,x
−1
, 0) = x
−1
(h
2
(x
−2
,...,x
−c+1
,δ
a
(s
a
))⊕1). This
yields
λ(s
x
−2
,x
−1
, 0) = λ(s
x
−2
,0
, 0) ⊕ x
−1
(h
2
(x
−2
,...,x
−c+1
,δ
a
(s
a
)) ⊕ 1)
= f
1
(x
−2
,...,x
−c
,s
a
) ⊕ x
−1
(h
2
(x
−2
,...,x
−c+1
,δ
a
(s
a
)) ⊕ 1).
Therefore,
f(x
0
,x
−1
,...,x
−c
,s
a
)=λ(x
−1
,x
−2
,...,x
−c
,s
a
,x
0
)
= λ(x
−1
,x
−2
,...,x
−c
,s
a
, 0) ⊕ x
0
= f
1
(x
−2
,...,x
−c
,s
a
) ⊕ x
−1
(h
2
(x
−2
,...,x
−c+1
,δ
a
(s
a
)) ⊕ 1) ⊕ x
0
.
Lemma 5.4.6. Let M = X,Y, S, δ,λ be a c-order semi-input-memory fi-
nite automaton SIM(M
a
,f),andM
a
= Y
a
,S
a
,δ
a
,λ
a
be strongly cyclic. If
c 2, w
2,M
=1, X = Y = {0, 1} and M is weakly invertible with delay 2,
then there exists a single-valued mapping f
2
from X
c−2
× S
a
to Y such that
f(x
0
,...,x
−c
,s
a
)=f
2
(x
−3
,...,x
−c
,s
a
) ⊕ x
−2
.
Proof.SinceM is a semi-input-memory finite automaton SIM(M
a
,f)
and M
a
is strongly cyclic, M is strongly connected. From Theorem 2.1.3
(f), it follows that |W
M
2,s
| = 1 holds for any state s of M . This yields
that λ(x
−1
,x
−2
,...,x
−c
,s
a
,x
0
), x
−1
,x
0
=0, 1 are the same. Since M
is weakly invertible with delay 2, we have λ(0, 0,x
−3
,...,x
−c
,s
a
, 0) =
λ(0, 1,x
−3
,...,x
−c
,s
a
, 0). Thus
f(x
0
,x
−1
,...,x
−c
,s
a
)=λ(x
−1
,...,x
−c
,s
a
,x
0
)
= λ(0,x
−2
,...,x
−c
,s
a
, 0)
= λ(0, 0,x
−3
,...,x
−c
,s
a
, 0) ⊕ x
−2
= f
2
(x
−3
,...,x
−c
,s
a
) ⊕ x
−2
,
172 5. Structure of Feedforward Inverses
where f
2
(x
−3
,...,x
−c
,s
a
)=f(0, 0, 0,x
−3
,...,x
−c
,s
a
).
Lemma 5.4.7. Let M = X,Y, S, δ,λ be a c-order semi-input-memory fi-
nite automaton SIM(M
a
,f),andM
a
= Y
a
,S
a
,δ
a
,λ
a
be strongly cyclic. If
c 2, w
2,M
=4, X = Y = {0, 1} and M is weakly invertible with delay 2,
then there exists a single-valued mapping f
0
from X
c
× S
a
to Y such that
f(x
0
,...,x
−c
,s
a
)=f
0
(x
−1
,...,x
−c
,s
a
) ⊕ x
0
.
Proof.SinceM is a semi-input-memory finite automaton SIM(M
a
,f)
and M
a
is strongly cyclic, M is strongly connected. From Theorem 2.1.3
(f), it follows that |W
M
2,s
| = 4 holds for any state s of M. This yields that
λ(x
−1
,...,x
−c
,s
a
, 0) = λ(x
−1
,...,x
−c
,s
a
, 1). Thus f(x
0
,x
−1
,...,x
−c
,
s
a
)=λ(x
−1
,...,x
−c
,s
a
,x
0
)=λ(x
−1
, ..., x
−c
, s
a
,0)⊕ x
0
= f
0
(x
−1
,...,
x
−c
,s
a
) ⊕ x
0
,wheref
0
(x
−1
,...,x
−c
,s
a
)=f(0,x
−1
,...,x
−c
,s
a
).
Theorem 5.4.1. Let M = X, Y, S, δ, λ be a c-order semi-input-memory
finite automaton SIM(M
a
,f),andM
a
= Y
a
,S
a
,δ
a
,λ
a
be strongly cyclic.
Let c 2 and X = Y = {0, 1}.ThenM is weakly invertible with delay 2 if
and only if one of the following conditions holds:
(a) There exists a single-valued mapping f
0
from X
c
× S
a
to Y such that
f(x
0
,...,x
−c
,s
a
)=f
0
(x
−1
,...,x
−c
,s
a
) ⊕ x
0
.
(b) There exists a single-valued mapping f
2
from X
c−2
× S
a
to Y such
that
f(x
0
,...,x
−c
,s
a
)=f
2
(x
−3
,...,x
−c
,s
a
) ⊕ x
−2
.
(c) There exist single-valued mappings h
0
from X
c−1
× S
a
to {0, 1}, h
1
from X
c−2
×S
a
to {0, 1}, f
0
from X
c
×S
a
to Y , f
1
from X
c−1
×S
a
to Y ,and
f
2
from X
c−2
× S
a
to Y , such that (5.2) and (5.3) hold, where h
2
is defined
by (5.4).
Proof. only if : From Theorem 2.1.3 (a), w
2,M
is in {1, 2, 4}. In the case of
w
2,M
= 4, from Lemma 5.4.7, the condition (a) holds. In the case of w
2,M
=1,
from Lemma 5.4.6, the condition (b) holds. In the case of w
2,M
=2,from
Lemma 5.4.5, the condition (c) holds.
if : Suppose that one of conditions (a), (b) and (c) holds. In the case of
(a), clearly, M is weakly invertible with delay 0. Thus M is weakly invertible
with delay 2. In the case of (b), it is easy to verify that M is weakly invertible
with delay 2.
Below we discuss the case (c). Suppose that the condition (c) holds.
Let s = x
−1
,x
−2
,...,x
−c
,s
a
, s
i
= i, x
−1
,...,x
−c+1
,δ
a
(s
a
) and s
i,j
=
j, i, x
−1
, ..., x
−c+2
, δ
2
a
(s
a
), i, j =0, 1. To prove s is a t-step state for some
t,0 t 2, there are several cases to consider.