Tao R. Finite Automata and Application to Cryptography

Подождите немного. Документ загружается.

5. Structure of Feedforward Inverses

Renji Tao

Institute of Software, Chinese Academy of Sciences

Beijing 100080, China trj@ios.ac.cn

Summary.

In Chaps. 1 and 3, we have adopted two methods, the state tree method

and the R

transformation method, to deal with the structure problem.

The former is suitable for general ﬁnite automata but not easy to manip-

ulate for large parameters. Contrarily, the latter is easy to manipulate but

only suitable for very special ﬁnite automata — linear or quasi-linear ones.

For nonlinear ﬁnite automata, the investigation meets with diﬃculties.

A feedforward invertible ﬁnite automaton is more complex in structure

as compared with its feedforward inverse. We ﬁrst explore the structure

problem for the simple. This chapter presents two approaches to the inves-

tigation for small delay cases. A decision criterion for feedforward inverse

ﬁnite automata with delay τ is proven and used to derive an explicit ex-

pression for ones of delay 0 which lays a foundation of a canonical form for

one key cryptosystems in Chap. 8. In another approach based on mutual

invertibility of ﬁnite automata, we give an explicit expression for feed-

forward inverse ﬁnite automata with delay 1 and for binary feedforward

inverse ﬁnite automata with delay 2.

Key words: semi-input-memory ﬁnite automata, feedforward inverse,

weakly invertible

In Chaps. 1 and 3, we have adopted two methods, the state tree method

and the R

transformation method, to deal with the structure problem.

The former is suitable for general ﬁnite automata but not easy to manipulate

for large parameters. Contrarily, the latter is easy to manipulate but only

suitable for very special ﬁnite automata — linear or quasi-linear ones over

ﬁnite ﬁelds. In general, for nonlinear ﬁnite automata, the investigation meets

up with diﬃculties for lack of mathematical tools.

Although semi-input-memory ﬁnite automata are nonlinear, they have

simpler structure as compared with general ﬁnite automata. So a feedforward

154 5. Structure of Feedforward Inverses

invertible ﬁnite automaton is more complex in structure as compared with its

feedforward inverse. We ﬁrst explore the structure problem for the simple. In

this chapter, we present two approaches to the investigation for small delay

cases. A decision criterion for feedforward inverse ﬁnite automata with delay

τ is proven and used to derive an explicit expression for ones of delay 0 which

lays a foundation of a canonical form for one key cryptosystems in Chap. 8.

In another approach based on mutual invertibility of ﬁnite automata, we give

an explicit expression for feedforward inverse ﬁnite automata with delay 1

and for binary feedforward inverse ﬁnite automata with delay 2.

5.1 A Decision Criterion

Let M



= Y , X, S



, δ



, λ



 be a c-order semi-input-memory ﬁnite automaton

SIM(M

,f), where S



= Y

× S

, M

= Y

,δ

,λ

 is an autonomous

ﬁnite automaton, and f is a single-valued mapping from Y

c+1

× λ

)to

X. The restriction of f on a subset of Y

c+1

× λ

) is still denoted by f.

Let u

,...,u

be n (  1 ) diﬀerent states of M

= Y

,δ

,λ

.If

)=u

i+1

, i =1,...,n− 1, δ

)=u

, {u

,...,u

} is called a cycle of

= Y

,δ

,λ

 is said to be cyclic ,ifS

is a cycle of M

. M

said to be strongly cyclic ,ifY

= S

, λ

)=s

holds for any s

∈ S

,and

is cyclic.

Theorem 5.1.1. M



is a feedforward inverse with delay τ if and only if

there exists a ﬁnite subautomaton

of M

such that

is cyclic and

SIM(

,f) is a feedforward inverse with delay τ.

Proof.SinceSIM(

,f) is a ﬁnite subautomaton of M



,theif part is

evident. To prove the only if part, suppose that M



is a feedforward inverse

with delay τ . Then there exists a ﬁnite automaton M = X, Y, S, δ, λ such

that M



is a weak inverse with delay τ of M.Lets be in S. Then there

exists s



= y

−1

,...,y

−c

,t in S



such that s



τ-matches s.Letδ

(t)=t

and δ

i+1

(t)=δ

(δ

(t)) for any i  0. Consider the inﬁnite sequence t,

(t), δ

(t), ... Since S

is ﬁnite, some states occur repetitively in the se-

quence. Let the earliest repetitive states be δ

(t)andδ

p+r

(t). Take

{δ

(t),δ

p+1

(t),...,δ

p+r−1

(t)}. Clearly,

is closed in M

. Thus there exists

a ﬁnite subautomaton

of M

such that the state alphabet of

On the other hand, let

S = {δ(s, α) | α ∈ X

∗

, |α|  p}.Itisevidentthat

is closed with respect to X in M. Thus there exists a ﬁnite subautomaton

M of M such that the input, output and state alphabets of

M are X, Y

and

S, respectively. We prove SIM(

,f)isaweakinversewithdelayτ

5.1 A Decision Criterion 155

M.Let¯s be in

S. Then there exists α in X

∗

such that |α|  p and ¯s =

δ(s, α). Let λ(s, α)=β = y

...y

k−1

,wherek = |α|. Clearly, δ



,β)=

y

k−1

,...,y

k−c

,δ

(t).Fromk  p, δ

(t)isin

. It follows that δ



,β)is

also a state of the ﬁnite subautomaton SIM(

,f)ofM



. Since the state s



of M



τ-matches the state s of M and β = λ(s, α), the state δ



,β)ofM



τ-

matches the state δ(s, α)(=¯s)ofM.Thusthestateδ



,β)ofSIM(

,f)

τ-matches the state ¯s of

M. We conclude that SIM(

,f) is a feedforward

inverse with delay τ of

M. Therefore, SIM(

,f)isaweakinversewith

delay τ. 

For any t in S

,weusef

to denote a single-valued mapping from Y

c+1

to X, deﬁned by f

,...,y

)=f(y

,...,y

,λ

(t)), y

,...,y

∈ Y . For any

τ,0 τ  c,andanyt ∈ S

,let

(τ)

={x

...x

...y

,...,x

∈ X, y

,...,y

∈ Y,f

,...,y

)=x

c−τ

Algorithm of F

(τ)

,t∈ S

Input : An autonomous ﬁnite automaton M

= Y

,δ

,λ

,asingle-

valued mapping f from Y

c+1

× λ

)toX.

Output :SetsF

(τ)

, t ∈ S

Procedure :

1. Take F

= F

(τ)

, t ∈ S

2. For each t ∈ S

, each x

∈ X, each y

∈ Y , i =1,...,c, if there exists

c+1

∈ X such that x

...x

c+1

...y

c+1

∈ F

holds for any y

c+1

∈ Y ,

then delete elements x

...x

...y

, x

∈ X, y

∈ Y from F



,for

any t



∈ δ

−1

(t)(={t

∈ S

| δ

)=t}).

3. Repeat Step 2 until no element can be deleted.

4. Output F

(τ)

= F

, t ∈ S

,andstop.

From the algorithm of F

(τ)

,t∈ S

, it is easy to show the following lemma.

Lemma 5.1.1. (a) F

(τ)

⊆ F

(τ)

, t ∈ S

(b) If t = δ

(u) and F

(τ)

= ∅,thenF

(τ)

= ∅.

,anyx

...x

...y

∈ F

(τ)

and any x

c+1

∈ X,there

exists y

c+1

∈ Y such that x

...x

c+1

...y

c+1

is in F

(τ)

,wherev = δ

(t).

Theorem 5.1.2. M



is a feedforward inverse with delay τ if and only if

there exists t in S

such that F

(τ)

= ∅.

Proof. only if : Suppose that M



is a feedforward inverse with delay τ.

Then there exists a ﬁnite automaton M = X, Y, S, δ, λ such that M



is a

weak inverse with delay τ of M.Lets be a state of M. Then there exists

a state s



= y

−1

,...,y

−c

,t of M



such that s



τ-matches s. Thus for any

,...in X and any y

,...in Y ,ify

...= λ(s, x

...), then there

156 5. Structure of Feedforward Inverses

exist x

−τ

,...,x

−1

in X such that λ



...)=x

−τ

...x

−1

... From

the construction of M



,itiseasytoseethatx

i−τ

= f(y

,...,y

i−t

,λ

(δ

(t))),

i =0, 1,...Thus for any i  c, x

i−c

...x

i−c

...y

is in F

(τ)

,whereu = δ

(t).

For any u ∈{δ

(t),i= c, c+1,...}, deﬁne F



= {x

i−c

...x

i−c

...y

| i  c,

i−c

, ..., x

∈ X, u = δ

(t), there exist x

, ..., x

i−c−1

∈ X such that

λ(δ(s, x

... x

i−c−1

),x

i−c

...x

)=y

i−c

...y

}.ThenwehaveF



⊆ F

(τ)

for any u ∈{δ

(t),i = c, c +1,...}. We prove the proposition: for any u ∈

{δ

(t),i = c, c +1,...},anya

...a

...b

∈ F



,andanya

c+1

∈ X,there

exists b

c+1

∈ Y such that a

...a

c+1

... b

c+1

∈ F



,wherev = δ

(u).

In fact, from the deﬁnition of F



, there exist i  c, x

,...,x

∈ X,and

,...,y

∈ Y such that λ(s, x

...x

)=y

...y

, x

i−c

...x

i−c

...y

...a

...b

,andu = δ

(t). Let b

c+1

= λ(δ(s, x

...x

),a

c+1

). Clearly,

λ(s, x

...x

c+1

)=y

...y

c+1

.Sincev = δ

(u)=δ

i+1

(t), from the deﬁn-

ition of F



,wehavex

i−c+1

...x

c+1

i−c+1

...y

c+1

= a

...a

c+1

...b

c+1

∈ F



Since {δ

(t),i = c, c +1,...} is ﬁnite, there exist diﬀerent elements

,...,u

in {δ

(t),i= c, c +1,...} such that δ

)=u

i+1

, i =1,...,n− 1

and δ

)=u

.SinceF



⊆ F

(τ)

holds for any u ∈{u

,...,u

},usingthe

above proposition, by induction on steps of the algorithm of F

(τ)

,t ∈ S

,it

is easy to prove that F



⊆ F

(τ)

holds for any u ∈{u

,...,u

}. For any u ∈

,...,u

},fromF



= ∅,wehaveF

(τ)

= ∅.

if : Suppose that F

(τ)

= ∅ for some t in S

. From Lemma 5.1.1 (b),

it is easy to see that F

(τ)

= ∅ for any u in {δ

(t),i =0, 1,...}.Since

{δ

(t),i =0, 1,...} is ﬁnite, there exist diﬀerent elements u

,...,u

{δ

(t),i=0, 1,...} such that δ

)=u

i+1

, i =1,...,n−1andδ

)=u

We construct M = X, Y, S, δ, λ as follows. Take S = {x

...x

...y

,u|

...x

...y

∈ F

(τ)

, u = u

,...,u

}.Letx

...x

...y

,u be in S.

Then x

...x

...y

∈ F

(τ)

and u ∈{u

,...,u

}. From Lemma 5.1.1 (c),

for any x

c+1

∈ X, there exists y

c+1

∈ Y such that x

...x

c+1

...y

c+1

∈ F

(τ)

where v = δ

(u). Clearly, v ∈{u

,...,u

}. It follows that x

...x

c+1

...

c+1

,v is in S. Choose arbitrarily such a y

c+1

, and deﬁne δ(x

...x

...

,u,x

c+1

)=x

...x

c+1

...y

c+1

,δ

(u) and λ(x

...x

...y

,u,

c+1

)=y

c+1

.WeprovethatM



is a weak inverse with delay τ of M. For any

state s = x

−c−1

...x

−1

−c−1

...y

−1

,u of M,lets



= y

−1

,...,y

−c

,δ

(u)

which is a state of M



. For any x

,... in X,letλ(s, x

...)=y

...,

where y

,... ∈ Y . From the construction of M,itiseasytoseethat

δ(s, x

...x

)=x

i−c

...x

i−c

...y

,δ

i+1

(u), i =0, 1,... Therefore, for any

i  0, we have x

i−c

...x

i−c

...y

∈ F

(τ)

,wherev = δ

i+1

(u). From F

(τ)

⊆ F

(τ)

, it follows that f(y

, ..., y

i−c

, λ

(δ

i+1

(u))) = x

i−τ

, i =0, 1,...

Let δ



...y

i−1

)=s



, i =0, 1,... Then s



= y

i−1

, ..., y

i−c

, δ

i+1

(u),

i =0, 1,... Thus λ



)=f (y

,...,y

i−c

,λ

(δ

i+1

(u))) = x

i−τ

, i =0, 1,...

5.2 Delay Free 157

It follows that λ



...)=x

−τ

...x

−1

... Thus s



τ-matches s.We

conclude that M



is a weak inverse with delay τ of M. Therefore, M



is a

feedforward inverse with delay τ . 

Corollary 5.1.1. If there exists a cycle C of M

such that for any u ∈ C

and any y

−1

,...,y

−c

∈ Y, |f(Y,y

−1

,...,y

−c

,λ

(u))| = |X| holds, then for

any τ,0  τ  c, M



is a feedforward inverse with delay τ.

Proof. It is easy to verify that for any u ∈ C,anyx

...x

...y

∈ F

(τ)

and any x

c+1

∈ X, there exists y

c+1

∈ Y such that f (y

c+1

,...,y

,λ

(δ

(u))) =

c−τ+1

. It follows that x

...x

c+1

...y

c+1

∈ F

(τ)

,wherev = δ

(u) ∈ C.

For any u ∈ C, from the algorithm of F

(τ)

,t ∈ S

,wehaveF

(τ)

= F

(τ)

=

∅. From Theorem 5.1.2, M



is a feedforward inverse with delay τ. 

5.2 Delay Free

Lemma 5.2.1. Let M = X, Y , S, δ, λ, M



= Y , X, S



, δ



, λ



 and



= Y , X, S



, δ



, λ



 be ﬁnite automata, and s



∈ S



. Assume that

|λ



,Y)| < |X| and that λ





,y)=λ



,y) holds for any s



∈ S



\{s



}

and any y ∈ Y .IfM



is a weak inverse with delay 0 of M,thenM



is a

weak inverse with delay 0 of M.

Proof. Suppose that M



is a weak inverse with delay 0 of M.Lets

be a state of M. Then there exists a state ϕ(s)ofM



such that ϕ(s)0-

matches s. Clearly, ϕ(s) is also a state of M



. We prove that the state

ϕ(s)ofM



0-matches the state s of M. For any x

, x

, ... ∈ X,let

... = λ(s, x

...), where y

, y

, ... ∈ Y . We prove by reduction to

absurdity a proposition: δ



(ϕ(s),y

...y

) = s



holds for j = −1, 0, 1,... Sup-

pose to the contrary that δ



(ϕ(s),y

...y

)=s



holds for some j  −1.

From y

...y

= λ(s, x

...x

), for any x ∈ X there exists y

∈ Y such

that y

...y

= λ(s, x

...x

x). Since the state ϕ(s)ofM



0-matches

the state s of M,wehaveλ



(ϕ(s),y

...y

)=x

...x

x. It follows

that λ



)=λ



(δ



(ϕ(s),y

...y

),y

)=x.Sincex may take any el-

ement in X,wehave|λ



,Y)| = |X|. This contradicts the assumption of

the theorem. Thus the proposition holds. Since λ





,y)=λ



,y)holds

for any s



∈ S



\{s



} and y ∈ Y , using the above proposition, we have



(ϕ(s),y

...)=λ



(ϕ(s),y

...). Since λ



(ϕ(s),y

...)=x

...,we

have λ



(ϕ(s),y

...)=x

... Thus the state ϕ(s)ofM



0-matches the

state s of M. Therefore, M



is a weak inverse with delay 0 of M . 

Theorem 5.2.1. M is a feedforward invertible with delay 0 if and only if

there exists SIM(M

,f) such that SIM(M

,f) is a weak inverse with delay

158 5. Structure of Feedforward Inverses

0 of M and |f(Y, y

−1

,..., y

−c

,λ

(t))| = |X| holds for any state t of M

and

any y

−1

,...,y

−c

in Y .

Proof.Theif part is trivial. The only if part can be obtained by applying

repeatedly Lemma 5.2.1. 

Let M



= Y, X, S



,δ



,λ



 be a c-order semi-input-memory ﬁnite au-

tomaton SIM(M

, f), where S



= Y

× S

, M

= Y

,δ

,λ

 is

an autonomous ﬁnite automaton, and f is a single-valued mapping from

c+1

× λ

)toX.

From Corollary 5.1.1, if |f(Y, y

−1

,...,y

−c

,λ

(t))| = |X| holds for any

state t of M

and any y

−1

,...,y

−c

in Y ,thenM



is a feedforward inverse

with delay 0. Below we prove that the suﬃcient condition is also necessary

in the case of |X| = |Y |.

Lemma 5.2.2. Let M

be cyclic, and |X| = |Y |. If there exist v in S

and

,...,y

c−1

in Y such that |f(Y,y

c−1

,...,y

,λ

(v))| < |X|,thenM



is not

a feedforward inverse with delay 0.

Proof.Letv ∈ S

and y

,...,y

c−1

∈ Y . Suppose that |f(Y, y

,...,y

c−1

(v))| < |X|.ThenX \ f(Y,y

c−1

,...,y

,λ

(v)) = ∅ holds and for any

,...,x

c−1

in X,anyx

in X \ f(Y,y

c−1

,...,y

,λ

(v)) and any y

in Y ,

...x

...y

is not in F

(0)

. Therefore, for any x

,...,x

c−1

in X,anyx

in X \ f(Y,y

c−1

,...,y

,λ

(v)) and any y

in Y , x

...x

...y

is not in

(0)

.Letu ∈ S

with δ

(u)=v. From the algorithm of F

(τ)

,t∈ S

, for any

−1

,...,x

c−1

in X and any y

−1

in Y , x

−1

...x

c−1

−1

...y

c−1

is not

in F

(0)

We prove a proposition: for any j,1 j  c,andanyp, q ∈ S

,ifδ

(p)=q

and x

−j

...x

c−j

−j

...y

c−j

∈ F

(0)

holds for any x

−j

,...,x

c−j

in X and any

−j

,...,y

−1

in Y ,thenx

−j−1

...x

c−j−1

−j−1

...y

c−j−1

∈ F

(0)

holds for any

−j−1

, ..., x

c−j−1

in X and any y

−j−1

,...,y

−1

in Y . In fact, from the algo-

rithm of F

(τ)

,t∈ S

, it is suﬃcient to prove that for any x

−j

,...,x

c−j−1

X and any y

−j

,...,y

−1

in Y , there exists x

c−j

in X such that x

−j

... x

c−j

−j

... y

c−j−1

y ∈ F

(0)

holds for any y in Y . There are two cases to consider.

Inthecaseof|f(Y , y

c−j−1

, ..., y

−j

, λ

(q))| < |X|, we choose an element in

X \ f(Y,y

c−j−1

,...,y

−j

, λ

(q)) as x

c−j

.Thenx

−j

...x

c−j

−j

...y

c−j−1

y ∈

(0)

holds for any y in Y . Therefore, x

−j

...x

c−j

−j

...y

c−j−1

y ∈ F

(0)

holds

for any y in Y . In the case of |f (Y,y

c−j−1

,..., y

−j

, λ

(q))| = |X|,from|X| =

|Y |,itiseasytoseethatforanyx in X there exists uniquely y in Y such

that f(y, y

c−j−1

,...,y

−j

,λ

(q)) = x.Letx

c−j

= f(y

c−j

,...,y

−j

,λ

(q)).

Then for any y in Y \{y

c−j

},wehavef(y, y

c−j−1

,...,y

−j

,λ

(q)) = x

c−j

Thus x

−j

...x

c−j

−j

...y

c−j−1

y ∈ F

(0)

holds for any y in Y \{y

c−j

}.There-

fore, x

−j

...x

c−j

−j

...y

c−j−1

y ∈ F

(0)

holds for any y in Y \{y

c−j

}.Since

5.2 Delay Free 159

−j

...x

c−j

−j

...y

c−j

∈ F

(0)

holds, x

−j

...x

c−j

−j

...y

c−j−1

y ∈ F

(0)

holds

for any y in Y .

We have proven in the ﬁrst paragraph of the proof that x

−1

... x

c−1

−1

... y

c−1

∈ F

(0)

holds for any x

−1

, x

, ..., x

c−1

in X and any y

−1

Y . Using the above proposition c times, we have that there exists w ∈ S

such that x

−c−1

...x

−1

−c−1

...y

−1

∈ F

(0)

holds for any x

−1

,...,x

−c−1

X and any y

−1

,...,y

−c−1

in Y . It follows that F

(0)

= ∅ holds. Since M

cyclic, from Lemma 5.1.1 (b), we have F

= ∅ holds for any t ∈ S

.From

Theorem 5.1.2, M



is not a feedforward inverse with delay 0. 

Theorem 5.2.2. If |X| = |Y |,thenM



is a feedforward inverse with delay 0

if and only if there exists a cycle C of M

such that |f(Y,y

−1

,...,y

−c

,λ

(u))|

= |X| holds for any u ∈ C and any y

−1

,...,y

−c

∈ Y .

Proof. From Corollary 5.1.1, the if part holds.

To prove the only if part, suppose that M



is a feedforward inverse

with delay 0. From Theorem 5.1.1, there exists a cycle C of M

such

that SIM(

,f) is a feedforward inverse with delay 0, where

Y

,C,δ

,λ

. From Lemma 5.2.2, |f (Y, y

−1

,...,y

−c

,λ

(u))| = |X| holds

for any u ∈ C and any y

−1

,...,y

−c

∈ Y . 

Theorem 5.2.2 can be proven using mutual invertibility (Theorem 2.2.2)

as follows.

It is easy to verify the following proposition.

Proposition 5.2.1. For any ﬁnite automaton M = X, Y, S, δ, λ, M is

weakly invertible with delay 0 if and only if for any state s of M , λ

an injection from X to Y .

Let M



= Y,X,S



,δ



,λ



 be a c-order semi-input-memory ﬁnite automa-

ton SIM(M

,f)with|X| = |Y |. From Theorem 5.1.1, M



is a feedforward

inverse with delay 0 if and only if there exists a ﬁnite subautomaton

of M

such that

is cyclic and SIM(

,f) is a feedforward inverse with delay 0.

Since SIM(

,f) is strongly connected, using Theorem 2.2.2, SIM(

,f)

is a feedforward inverse with delay 0 if and only if SIM(

,f) is weakly in-

vertible with delay 0. From |X| = |Y |, using Proposition 5.2.1, SIM(

,f)

is a feedforward inverse with delay 0 if and only if |f(Y, y

−1

,...,y

−c

,λ

(u))| =

|X| holds for any state u of

and any y

−1

,...,y

−c

in Y .LetC be the state

alphabet of

. Clearly, C is a cycle of M

.ThusM



is a feedforward inverse

with delay 0 if and only if |f (Y,y

−1

,...,y

−c

,λ

(u))| = |X| holds for any u ∈

C and any y

−1

,...,y

−c

∈ Y . This completes another proof of Theorem 5.2.2.

160 5. Structure of Feedforward Inverses

5.3 One Step Delay

Let M = X, Y, X

× S

,δ,λ be a c-order semi-input-memory ﬁnite au-

tomaton SIM(M

,f), where M

= Y

,δ

,λ

 is an autonomous ﬁnite

automaton, and f is a single-valued mapping from X

c+1

× λ

)toY .

Lemma 5.3.1. Let M = X, Y ,S, δ, λ be a semi-input-memory ﬁnite

automaton SIM(M

,f).

(a) M is strongly connected if and only if M

is cyclic.

(b) If M

is cyclic, |X| = |Y | and M is weakly invertible with delay τ,

then |W

τ+1,s

| = w

τ+1,M

and |W

τ,s

| = w

τ,M

hold for any s ∈ S.

Proof. (a) It is trivial from deﬁnitions.

(b) From (a), M is strongly connected. From Theorem 2.1.3 (f), |W

τ,s

| =

τ,M

holds for any s ∈ S. Using Theorem 2.1.3 (c), it immediately follows

that |W

τ+1,s

| = w

τ+1,M

holds. 

Lemma 5.3.2. Let M = X, Y, S, δ,λ be weakly invertible with delay 1,and

|X| = |Y | = q.Let|W

1,s

| = w

1,M

. Divide q successors of s into blocks such

that δ(s, x

) and δ(s, x

) belong to the same block if and only if λ(s, x

λ(s, x

). Then the number of blocks is w

1,M

, each block consists of q/w

1,M

diﬀerent states, the set of the outputs of length 1 on each state in a block has

1,M

elements and such q/w

1,M

sets for the block constitute a partition of

Y .

Proof. Denote the successors δ(s, x), x ∈ X of s by s

,...,s

(they are

not necessary to be diﬀerent from each other). From Theorem 2.1.3 (b),

we have |W

1,s

| = w

1,M

, j =1,...,q. Divide s

,...,s

into blocks such

that s

= δ(s, x

)ands

= δ(s, x

) belong to the same block if and only if

λ(s, x

)=λ(s, x

). Since |W

1,s

| = w

1,M

, the number of blocks is w

1,M

.From

Theorem 2.1.3 (e), |I

y,s

| = q/w

1,M

holds for any y ∈ W

1,s

.Thuseachblock

consists of q/w

1,M

elements. Since M is weakly invertible with delay 1, the

sets of the outputs of length 1 on any two elements in a block are disjoint. It

follows that any two elements in a block are diﬀerent states. For any block

T ,from|W

1,s

| = w

1,M

, j =1,...,q,wehave|W

1,t

| = w

1,M

for any t ∈ T .

From |T | = q/w

1,M

and W

1,t

∩ W

1,t



= ∅ for any diﬀerent t and t



in T ,it

follows that the sets W

1,t

, t ∈ T constitute a partition of Y . 

We use Y

w

to denote the set of all subsets with w elements of Y ,that

is, Y

w

= {T |T ⊆ Y, |T | = w}.

Let ϕ be a single-valued mapping from X to Y

w

and |X| = |Y |.Letψ

be a uniform mapping from X to {1,...,w},thatis,w is a divisor of |X|

and |ψ

−1

(j)| = |X|/w for any j,1 j  w.If



x∈ψ

−1

(j)

ϕ(x)=Y holds for

5.3 One Step Delay 161

any j,1 j  w, ψ is called a valid partition of ϕ.WeuseP

to denote

the set of all valid partitions of ϕ. Denote n

= |P

|; n

= 0 means no valid

partition of ϕ.

We make an order of elements in Y . It leads to an ordering of elements

in each subset of Y .Weusem(j, T )todenotethej-th element of T in the

ordering.

Lemma 5.3.3. Let M = X,Y, S, δ,λ be a c-order semi-input-memory ﬁ-

nite automaton SIM(M

,f),andM

be strongly cyclic. Let M be weakly

invertible with delay 1,and|X| = |Y |.Thenf can be expressed as

f(x

−1

,...,x

−c

)=m(ψ

−c

,...,x

−1

),ϕ

−c

,...,x

−2

−1

)),

where ψ

−c

,...,x

−1

∈ P

−c+1

,...,x

−1

,δ

)

,andϕ

−c

,...,x

−2

is a single-

valued mapping from X to Y

w

1,M



Proof. Deﬁne ϕ

−c

,...,x

−2

−1

)=λ(x

−1

,...,x

−c

,X). From Lemma

5.3.1 (a), M is strongly connected. From Lemma 5.3.1 (b), we have |W

1,s

| =

1,M

for any s ∈ S. Thus for any x

−c

,...,x

−2

∈ X and s

∈ S

, ϕ

−c

,...,x

−2

is a single-valued mapping from X to Y

w

1,M



. For any state s = x

−1

,...,

−c

 of M , deﬁne ψ

−c

,...,x

−1

)=j,whereλ(s, x

)isthej-th element

of λ(s, X). Since |λ(s, X)| = |W

1,s

| = w

1,M

, ψ

−c

,...,x

−1

is a single-valued

mapping from X to {1,...,w

1,M

}. Noticing that ψ

−1

−c

,...,x

−1

(j)=I

when the j-th element of W

1,s

is y

, from Theorem 2.1.3 (g), we have

|ψ

−1

−c

,...,x

−1

(j)| = |I

| = q/w

1,M

. Therefore, ψ

−c

,...,x

−1

is uniform.

From the deﬁnitions, it is easy to verify that

f(x

−1

,...,x

−c

)=m(ψ

−c

,...,x

−1

),ϕ

−c

,...,x

−2

−1

)).

To prove ψ

−c

,...,x

−1

∈ P

−c+1

,...,x

−1

,δ

)

, take arbitrarily an integer

j,1 j  w

1,M

. From the deﬁnition, x ∈ ψ

−1

−c

,...,x

−1

(j) if and only if

λ(s, x)=y

,wheres = x

−1

,...,x

−c

, y

is the j-th element of W

1,s

Since M is weakly invertible with delay 1, λ(x

, x

−1

, ..., x

−c+1

, δ

), X)

and λ(x



, x

−1

, ..., x

−c+1

, δ

), X)aredisjointifλ(s, x

)=λ(s, x



)=y

and x

= x



.Thatis,ϕ

−c+1

,...,x

−1

,δ

)

)andϕ

−c+1

,...,x

−1

,δ

)



)are

disjoint, if x



∈ ψ

−1

−c

,...,x

−1

(j)andx

= x



.Since|ψ

−1

−c

,...,x

−1

(j)| =

| = q/w

1,M

, |ϕ

−c+1

,...,x

−1

,δ

)

(x)| = w

1,M

and |Y | = q,wehave



x∈ψ

−1

−c

,...,x

−1

(j)

−c+1

,...,x

−1

,δ

)

(x)=Y.

Thus ψ

−c

,...,x

−1

is a valid partition of ϕ

−c+1

,...,x

−1

,δ

)

. 

162 5. Structure of Feedforward Inverses

Lemma 5.3.4. Let M = X,Y, S, δ,λ be a c-order semi-input-memory ﬁ-

nite automaton SIM(M

,f), M

be strongly cyclic, and |X| = |Y |.Iff can

be expressed as

f(x

−1

,...,x

−c

)=m(ψ

−c

,...,x

−1

),ϕ

−c

,...,x

−2

−1

)),

where ψ

−c

,...,x

−1

∈ P

−c+1

,...,x

−1

,δ

)

,andϕ

−c

,...,x

−2

is a single-

valued mapping from X to Y

w

,thenM is weakly invertible with delay 1

and w

1,M

= w.

Proof. For any state s = x

−1

,...,x

−c

 of M ,anyx

, x



∈ X,

let y

= λ(s, x

)andy



= λ(s, x



), where y



∈ Y . Suppose

that y

= y



.ToprovethatM is weakly invertible with delay 1, it is

suﬃcient to prove x

= x



. Suppose to the contrary that x

= x



.Since

= y



,wehavef(x

−1

,...,x

−c

)=f(x



−1

,...,x

−c

). Therefore,

thevaluesofψ

−c

,...,x

−1

)andψ

−c

,...,x

−1



)arethesame;wedenote

the value by j. On the other hand, since ψ

−c

,...,x

−1

is a valid partition of

−c+1

,...,x

−1

,δ

)

,wehave



x∈ψ

−1

−c

,...,x

−1

(j)

−c+1

,...,x

−1

,δ

)

(x)=Y.

From |ψ

−1

−c

,...,x

−1

(j)| = q/w, |ϕ

−c+1

,...,x

−1

,δ

)

(x)| = w and |Y | = q,it

follows that ϕ

−c+1

,...,x

−1

,δ

)

(x), x ranging over elements in ψ

−1

−c

,...,x

−1

(j),

constitute a partition of Y .Sincex

= x



, ϕ

−c+1

,...,x

−1

,δ

)

)and

−c+1

,...,x

−1

,δ

)



) are disjoint. It follows that

m(ψ

−c+1

,...,x

−1

,δ

)

),ϕ

−c+1

,...,x

−1

,δ

)

))

= m(ψ

−c+1

,...,x

−1



,δ

)



),ϕ

−c+1

,...,x

−1

,δ

)



)).

Therefore,

f(x

−1

,...,x

−c+1

,δ

)) = f(x



−1

,...,x

−c+1

,δ

)),

that is, y

= y



. This contradicts y

= y



. Thus the hypothesis x

= x



does not hold. We conclude that x

= x



From the deﬁnition of the valid partition, it is easy to see that for

any state s = x

−1

,...,x

−c

, s

 of M,thenumberoftheelementsin

f(X, x

−1

,...,x

−c

)isw,thatis,|λ(s, X)| = w. From Lemma 5.3.1 (a), M

is strongly connected. Using Lemma 5.3.1 (b), we have w

1,M

= |λ(s, X)| =

w. 

Theorem 5.3.1. Let M = X, Y, S, δ, λ be a c-order semi-input-memory

ﬁnite automaton SIM(M

,f),M

= Y

,δ

,λ

 be strongly cyclic, and