Tao R. Finite Automata and Application to Cryptography

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

1.3 Linear Finite Automata 21

A linear ﬁnite automaton is called a linear shift register, if its state transition

matrix is P

f(z)

for some f(z).

Let M

= X, Y, S

,δ

,λ

 be a linear ﬁnite automaton over GF (q)with

structure matrices A

, B

, C

, D

and structure parameters l, m, n

, i =

1,...,h. The linear ﬁnite automaton with structure matrices A, B, C, D is

called the union of M

, ..., M

,where

A =

⎡

⎢

⎣

⎤

⎥

⎦

,B=

⎡

⎢

⎣

⎤

⎥

⎦

C =[C

... C

],D= D

+ D

+ ···+ D

In the deﬁnition, some M

may be autonomous, where B

and D

are zero

matrices.

Theorem 1.3.5. Let M be a linear ﬁnite automaton over GF (q).Then

there exist linear shift registers M

, ..., M

over GF (q) such that M is

similar to the union of M

, ..., M

Proof.LetA, B, C, D be structure matrices of M. It is known that there

exists a nonsingular matrix P over GF (q) such that

PAP

−1

⎡

⎢

⎣

(z)

⎤

⎥

⎦

where f

(z), ..., f

(z) are the elementary divisors of A.LetM



be a linear

ﬁnite automaton with structure matrices A



, B



, C



, D,whereA



= PAP

−1



= PB, C



= CP

−1

. Clearly, M and M



are similar. Let M

be a linear

shift register with structure matrices P

(z)

, B

, C

, D

, i =1,...,h,where

PB =

⎡

⎢

⎣

⎤

⎥

⎦

,CP

−1

=[C

... C

],D= D

+ D

+ ···+ D

Clearly, M



is the union of M

, ..., M

. 

Let M = X, Y, S, δ, λ be a linear ﬁnite automata over GF (q)with

structure matrices A, B, C, D and structure parameters l, m, n.LetS

{δ(0,α),α∈ X

∗

}. Denote the restrictions of δ and λ on S

× X by δ

and λ

respectively. It is easy to verify that δ

and λ

are single-valued mappings

22 1. Introduction

from S

×X to S

and Y , respectively. Thus M

= X, Y, S

,δ

,λ

 is a ﬁnite

subautomaton of M.ItiseasytoseethatS

is a subspace of S.Denotethe

dimension of S

by n

.LetR be an n × n

matrix so that columns of R

form a basis of S

.LetT be a left inverse matrix of R. Deﬁne A

= TAR,

= TB, C

= CR,andD

= D.LetM



= X, Y, S



,δ



,λ



 be a linear

ﬁnite automaton over GF (q) with structure matrices A

,where



is the vector space of dimension n

over GF (q). Then M



and M

are

isomorphic. In fact, for any s

and s

in S

, there exist s



and s



in S



such

that s

= Rs



, i =1, 2. Thus Ts

= Ts

if and only if s



= s



. It follows that

= s

if and only if Ts

= Ts

.Letϕ be a single-valued mapping from S



to S

deﬁned by ϕ(s



)=Rs



for any s



in S



. Clearly, ϕ is bijective. For any



in S



and for any x in X,sinceRs



is in S

, from the deﬁnitions of S

and

, δ

(ϕ(s



),x)isinS

. Clearly, ϕ(δ



,x)) is in S

.Since

Tδ

(ϕ(s



),x)=TARs



+ TBx = A



+ B

= T (R(A



+ B

x)) = Tϕ(δ



,x)),

we have δ

(ϕ(s



),x)=ϕ(δ



,x)). We also have

(ϕ(s



),x)=CRs



+ Dx = C



+ D

x = λ



,x).

Thus ϕ is an isomorphism from M



to M

. Therefore, M



and M

are

isomorphic. M



is referred to as a minimal linear ﬁnite subautomaton of

M. Since each of minimal linear ﬁnite subautomata of M is isomorphic

to M

, they are isomorphic. Since M



and M

are isomorphic, we have



= {δ



(0,α),α ∈ X

∗

}.LetM

be the linear autonomous ﬁnite automa-

ton with structure matrices A, C. M

is referred to as the maximal linear

autonomous ﬁnite subautomaton of M. From Corollary 1.3.2, for any state

s



 of the union of M

and M



,thestates

+ Rs



of M and s



 are

equivalent. Conversely, for any state s of M,thestates, 0 of the union of

and M



and s are equivalent. Thus M and the union of M

and M



are

equivalent.

Take a formal symbol z.Let

F =



∞



τ=−∞

| a

∈ GF (q),τ=0, ±1, ±2,..., and the number

of nonzero a

for negative subscript τ is ﬁnite



Any a(z)=



∞

τ=−∞

in F,max n(a

=0ifτ<n) is called the low

degree of a(z). We also denote a(z)by



∞

τ=k

for any integer k  the

low degree of a(z). In the case of a

= 0 for any integer τ,weuse0to

denote a(z). Notice that the low degree of 0 is −∞. For any two elements

1.3 Linear Finite Automata 23

a(z)=



∞

τ=−∞

and b(z)=



∞

τ=−∞

in F, we deﬁne the sum of

a(z)andb(z)asanelement



∞

τ=−∞

+ b

in F, denoted by a(z)+b(z).

We deﬁne the product of a(z)andb(z)asanelement



∞

τ=−∞

of F,

denoted by a(z)b(z), where



i+j=τ,ik,jh

k and h are lower degrees of a(z)andb(z), respectively. It is easy to verify

that F is a ﬁeld and GF (q) is its subﬁeld in the isomorphic sense (a

GF (q) corresponds to a

in F).

Let Ω =[ω

,ω

,...] be an inﬁnite sequence over GF (q). The element



∞

τ=0

in F is called the generating function or z-transformation of Ω.

For any Ω,weuseΩ(z)todenoteitsz-transformation.

Let Φ =[ϕ

,ϕ

,...] be an inﬁnite sequence over the column vector space of

dimension k over GF (q). Let ϕ

=[ϕ

1τ

,...,ϕ

kτ

]

, for any nonnegative inte-

ger τ .WeuseΦ

to denote [ϕ

,ϕ

,...], that is, the i-th component sequence

of Φ.[Φ

(z),...,Φ

(z)]

is called the generating function or z-transformation

of Φ, denoted by Φ(z). It is easy to verify that the z-transformation of the

linear combination of sequences, say a

+ ···+ a

, is the linear combina-

tion of z-transformations, namely, a

(z)+···+ a

(z),where a

, ..., a

∈

GF (q), Φ

, ..., Φ

are r inﬁnite sequences over GF (q)orr inﬁnite sequences

over a column vector space over GF (q).

Let M = X, Y, S, δ, λ be a linear ﬁnite automaton over GF (q)with

structure matrices A, B, C, D and structure parameters l, m, n. For any s

in S and any x

,... in X,lets

i+1

= δ(s

), y

= λ(s

), i =0, 1,...

Then

τ+1

= As

+ Bx

= Cs

+ Dx

, (1.7)

τ =0, 1,...

We use X(z), Y (z), and S(z) to denote z-transformations of the input se-

quence [x

,...], the output sequence [y

,...], and the state sequence

,...], respectively. We use X

(z), Y

(z), S

(z), x

iτ

, y

iτ

,ands

iτ

to de-

note the i-th components of X(z), Y (z), S(z), x

, y

,ands

, respectively.

From (1.7), we have

24 1. Introduction

S(z)=

⎡

⎢

⎣

(z)

⎤

⎥

⎦

⎡

⎢

⎣

∞



τ=0

1τ

∞



τ=0

nτ

⎤

⎥

⎦

⎡

⎢

⎣

∞



τ=1





j=1

j,τ−1



j=1

j,τ−1



∞



τ=1





j=1

j,τ−1



j=1

j,τ−1



⎤

⎥

⎦

⎡

⎢

⎣

+ z



j=1

∞



τ=1

j,τ−1

τ−1

+ z



j=1

∞



τ=1

j,τ−1

τ−1

+ z



j=1

∞



τ=1

j,τ−1

τ−1

+ z



j=1

∞



τ=1

j,τ−1

τ−1

⎤

⎥

⎦

⎡

⎢

⎣

+ z



j=1

(z)+z



j=1

(z)

+ z



j=1

(z)+z



j=1

(z)

⎤

⎥

⎦

= s

+ zAS(z)+zBX(z),

where a

and b

areelementsatrowi and column j of A and B, respectively.

It follows that

(E − zA)S(z)=s

+ zBX(z),

where E stands for the n × n identity matrix over GF (q). Since the constant

term of the determinant |E − zA| is 1, we have

(E − zA)

−1

=(E − zA)

∗

/|E − zA|,

where (E − zA)

∗

is the adjoint matrix of E − zA, i.e., the matrix of which

the element at row i and column j is the cofactor at row j and column i of

E − zA.Thus

1.3 Linear Finite Automata 25

S(z)=(E − zA)

−1

+ z(E − zA)

−1

BX(z)

(E − zA)

∗

|E − zA|

z(E − zA)

∗

|E − zA|

X(z). (1.8)

Since

iτ



j=1

jτ



j=1

jτ

,i=1,...,m, τ =0, 1,...,

we have

(z)=



j=1

(z)+



j=1

(z),i=1,...,m,

where c

and d

are elements at row i and column j of C and D, respectively.

It follows that Y (z)=CS(z)+DX(z). From (1.8), we have

Y (z)=C(E − zA)

−1

+(zC(E − zA)

−1

B + D)X(z)

C(E − zA)

∗

|E − zA|



zC(E − zA)

∗

|E − zA|

+ D



X(z). (1.9)

Let

G(z)=C(E − zA)

−1

= C(E − zA)

∗

/|E − zA|, (1.10)

H(z)=zC(E − zA)

−1

B + D = zC(E − zA)

∗

B/|E − zA| + D.

Then (1.9) is

Y (z)=G(z)s

+ H(z)X(z). (1.11)

In (1.11), G(z)s

is the z-transformation of the free response of the initial

state s

,andH(z)X(z)isthez-transformation of the force response of the

input sequence x

... G(z)iscalledthefree response matrix of M,and

H(z)iscalledthetransfer function matrix of M. Clearly, if matrices G(z)

and H(z) over the ﬁeld F satisfy the condition that (1.11) holds for any s

and

any X(z), then G(z)andH(z) are the free response matrix and the transfer

function matrix of M, respectively. In other words, the free response matrix

and the transfer function matrix of M are uniquely determined by (1.11).

Notice that from (1.10), each element of G(z)andH(z) may be expressed as

a rational fraction of z with a nonzero constant term of the denominator.

In the case of

A =

⎡

⎢

⎣

01··· 00

00··· 00

00··· 01

−a

··· −a

n−2

−a

n−1

⎤

⎥

⎦

, (1.12)

26 1. Introduction

we have

|E − zA| =1+a

n−1

z + ···+ a

n−1

+ a

, (1.13)

(E − zA)

∗

⎡

⎢

⎣

n−1

(z) z

n−2

(z) ··· z

n−2

(z) z

n−1

−1

n−1

(z) z

n−2

(z) ··· z

n−3

(z) z

n−2

−(n−2)

n−1

(z) z

−(n−3)

n−2

(z) ··· z

(z) z

−(n−1)

n−1

(z) z

−(n−2)

n−2

(z) ··· z

−1

(z) z

⎤

⎥

⎦

where

(z)=1+



i=1

n−i

,ψ

(z)=



i=k+1

−a

n−i

, (1.14)

k =1,...,n− 1.

1.4 Concepts on Invertibility

A ﬁnite automaton M = X, Y, S,δ, λ is said to be invertible, if for any s, s



in S,andanyα, α



in X

, λ(s, α)=λ(s



,α



) yields α = α



.Inotherwords,

M is invertible, if and only if for any s in S and any α in X

, α can be

uniquely determined by λ(s, α).

Evidently, if M is invertible, then M



= X, Y, S



,δ



,λ



 is invertible in

thecasewhereM



≺ M or M



 M.

M is invertible, if and only if for any s, s



in S,anyx, x



in X,andany

α, α



in X

, λ(s, xα)=λ(s



) implies x = x



, that is, for any s in S,

any x in X,andanyα in X

, x can be uniquely determined by λ(s, xα). In

fact, the only if part is trivial. To prove the if part, suppose that λ(s, α)=

λ(s



,α



)fors, s



in S and α, α



in X

.Weproveα = α



. Denote α = x

...,



= x



...,forsomex

, x



in X, i =0, 1,... To prove x

= x



for i  0,

let s

= δ(s, x

...x

i−1

)ands



= δ(s



...x



i−1

). From λ(s, x

...)=

λ(s, x



...), we have λ(s

i+1

...)=λ(s



i+1

...). Since for any t, t



in S,anyx, x



in X,andanyβ, β



in X

, λ(t, xβ)=λ(t



β) yields x =



,wehavex

= x



.Thusα = α



A ﬁnite automaton M = X, Y, S, δ, λ is said to be invertible with delay τ ,

τ being a nonnegative integer, if for any s in S and any x

in X, i =0, 1,...,τ,

can be uniquely determined by λ(s, x

...x

), that is, for any s, s



in S

and any x

, x



in X, i =0, 1,...,τ, λ(s, x

...x

)=λ(s



...x



) yields

= x



Evidently, if M is invertible with delay τ,thenM



= X, Y, S



,δ



,λ



 is

invertible with delay τ in the case where M



≺ M or M



 M.

1.4 Concepts on Invertibility 27

Clearly, if M is invertible with delay τ ,thenM is invertible. Below we

prove that its converse proposition also holds.

Let M = X, Y, S, δ,λ be a ﬁnite automaton. Construct a graph G

(V,Γ) as follows. Let

R = {(δ(s, x),δ(s



)) | x = x



,λ(s, x)=λ(s



),x,x



∈ X, s, s



∈ S}.

InthecaseofR = ∅, let the vertex set V of G

be the minimal subset

of S × S satisfying the following conditions: (a) R ⊆ V ,(b)if(s, s



) ∈ V

and λ(s, x)=λ(s



)forx, x



∈ X,then(δ(s, x),δ(s



)) ∈ V .Letthearc

set Γ of G

be the set of all arcs ((s, s



), (δ(s, x),δ(s



))) satisfying the

following conditions: (s, s



) ∈ V , x, x



∈ X,andλ(s, x)=λ(s



). In the

case of R = ∅,letG

be the empty graph.

Theorem 1.4.1. M is invertible if and only if G

has no circuit. Moreover,

if G

has no circuit and the level of G

is ρ − 1, then M is invertible with

delay ρ +1 and not invertible with delay τ for any τ  ρ.

Proof. Suppose that G

has a circuit, say w. From the construction of

, for any vertex on w, there exists a path of which the terminal vertex

is the vertex on w and the initial vertex is in R. Thus there exists a path

...u

such that the initial vertex of u

is in R and u

r+1

...u

is a

circuit for some r,1 r  k.Let(s



) be the initial vertex of u

, i =

1, 2,...,k. Then the terminal vertex of u

is (s



). From the construction

of G

, there exist x

, x



∈ X, i =1, 2,...,k, such that δ(s

)=s

i+1

δ(s



)=s



i+1

, i =1, 2,...,k−1, δ(s

)=s

, δ(s



)=s



,andλ(s

)

= λ(s



), i =1, 2,...,k.From(s



) ∈ R, there exist s

, s



∈ S, x

, x



∈

X, such that δ(s

)=s

, δ(s



)=s



, λ(s

)=λ(s



)andx

= x



Taking

α = x

...x

r−1

...x

...,



= x



...x



r−1



...x



...x



...,

we then have λ(s

,α)=λ(s



,α



). Since x

= x



, M is not invertible.

Conversely, suppose that G

has no circuit. Then the level of G

an integer, say ρ − 1. In the case of R = ∅,itisevidentthatρ = −1

and M is invertible with delay 0 (= ρ + 1). In the case of R = ∅,for

any states s

and s



of M , and any input sequences α = x

...x

ρ+1

and



= x



...x



ρ+1

of length ρ +2,x

, x



∈ X, i =0, 1,...,ρ+1, we prove

by reduction to absurdity that λ(s, α)=λ(s, α



) implies x

= x



. Suppose

to the contrary that λ(s

...x

ρ+1

)=λ(s



...x



ρ+1

)andx

= x



for some states s

, s



in S and some input letters x

, x



, i =0, 1,...,ρ+1

in X. Denote s

= δ(s

i−1

), s



= δ(s



i−1



i−1

), i =1, 2,...,ρ+2. Since

28 1. Introduction

λ(s

...x

ρ+1

)=λ(s



...x



ρ+1

), we have λ(s

)=λ(s



), i =

0, 1,...,ρ+1. From x

= x



,wehave(s



) ∈ R, and for any i,1 i  ρ+1,

there exists an arc, say u

, such that the initial vertex of u

is (s



)andthe

terminal vertex of u

is (s

i+1



i+1

). Thus u

...u

ρ+1

is a path of G

.Since

the length of the path is ρ +1, the level of G

is at least ρ. This contradicts

that the level of G

is ρ − 1. We conclude that M is invertible with delay

ρ +1.

Let 0  τ  ρ. Since the level of G

is ρ − 1, there exists a path of length

τ of G

,sayu

...u

. Denote the initial vertex of u

by (s



)andthe

terminal vertex of u

by (s

i+1



i+1

), i =1, 2,...,τ. From the construction

of G

, without loss of generality, suppose that (s



)isinR.Fromthe

deﬁnition of R, there exist x

, x



in X and s

, s



in S, such that δ(s

, δ(s



)=s



, λ(s

)=λ(s



)andx

= x



. From the construc-

tion of G

, there exist x

, x



in X, i =1, 2,...,τ, such that δ(s

i+1

, δ(s



)=s



i+1

,andλ(s

)=λ(s



), i =1, 2,...,τ.Thuswehave

λ(s

...x

)=λ(s



...x



). From x

= x



, M is not invertible with

delay τ. 

Corollary 1.4.1. If M is invertible, then there exists τ  n(n − 1)/2 such

that M is invertible with delay τ, where n is the element number in the state

alphabet of M.

Proof. Suppose that M is invertible. Whenever G

is the empty graph,

M is invertible with delay 0 and 0  n(n − 1)/2. Whenever G

is not the

empty graph, then G

= V,Γ has no circuit. This yields that s

= s

for any (s

)inV .Thus|V |  n(n − 1).Itisevidentthat(s

) ∈ R

ifandonlyif(s

) ∈ R. From the construction of G

, this yields that

) ∈ V ifandonlyif(s

) ∈ V , and that ((s

), (s

)) ∈ Γ if and

only if ((s

), (s

)) ∈ Γ . Therefore, the number of vertices with level

i is at least 2, for any i,0 i  ρ,whereρ − 1isthelevelofG

.Then

we have 2(ρ +1) n(n − 1). Take τ = ρ +1. Thenτ  n(n − 1)/2. From

Theorem 1.4.1, M is invertible with delay τ. 

Let M = X, Y, S, δ,λ and M



= Y,X,S



,δ



,λ



 be two ﬁnite automata.

For any states s in S and s



in S



,if

(∀α)

(∃α

)

∗

[ λ



,λ(s, α)) = α

α & |α

| = τ ],

i.e., for any α ∈ X

there exists α

∈ X

∗

such that λ



,λ(s, α)) = α

α and

|α

| = τ,(s



,s) is called a match pair with delay τ or say that s



τ-matches

s. Clearly, if s



τ-matches s and β = λ(s, α)forsomeα in X

∗

,thenδ



,β)

τ-matches δ(s, α).



is called an inverse with delay τ of M, if for any s in S and any s



,(s



,s)isamatchpairwithdelayτ. M is called an original inverse with

1.4 Concepts on Invertibility 29

delay τ of M



,ifM



is an inverse with delay τ of M. M



is called an inverse

with delay τ,ifM



is an inverse with delay τ of some ﬁnite automaton. M



is called an inverse,ifM



is an inverse with delay τ for some τ.

Clearly, if M



is an inverse with delay τ of M,thenM



is an inverse with

delay τ of M



= X, Y, S



,δ



,λ



 inthecasewhereM



≺ M or M



 M.If



is an inverse with delay τ of M,thenM



= Y,X,S



,δ



,λ



 is an inverse

with delay τ of M inthecasewhereM



≺ M



or M



 M



. Therefore, if



is an inverse with delay τ ,thenM



= Y,X,S



,δ



,λ



 is an inverse with

delay τ in the case where M



≺ M



or M



 M



Theorem 1.4.2. If M is invertible with delay τ, then there exists a τ -order

input-memory ﬁnite automaton M



such that M



is an inverse with delay τ

of M.

Proof.SinceM is invertible with delay τ , for any s ∈ S and any x

, ..., x

∈ X, x

can be uniquely determined by λ(s, x

...x

). Thus

we can construct a single-valued mapping f from Y

τ+1

to X satisfying the

condition: if y

...y

= λ(s, x

...x

), s ∈ S and x

,...,x

∈ X,then

f(y

,...,y

)=x

.LetM



Y,X,S



,δ



,λ



 be the τ-order input-memory

ﬁnite automaton M

. From the deﬁnition of f and the construction of M

it is easy to verify that for any s ∈ S,anys



∈ S



and any x

,... ∈ X,



,λ(s, x

...)) = x

−τ

...x

−1

...

holds for some x

−τ

,...,x

−1

∈ X. Therefore, M



is an inverse with delay τ

of M. 

Corollary 1.4.2. M is invertible with delay τ if and only if there exists a

ﬁnite automaton M



such that M



is an inverse with delay τ of M.

A ﬁnite automaton M = X, Y, S, δ, λ is said to be weakly invertible,if

for any s in S,andanyα, α



in X

, λ(s, α)=λ(s, α



) implies α = α



.In

other words, M is weakly invertible, if and only if for any s in S and any α

in X

, α can be uniquely determined by s and λ(s, α), if and only if for any

s in S, λ

is injective.

Evidently, if M is weakly invertible, then M



= X, Y, S



,δ



,λ



 is

weakly invertible in the case where M



≺ M or M



 M.

M is weakly invertible, if and only if for any s in S,anyx, x



in X,and

any α, α



in X

, λ(s, xα)=λ(s, x



) implies x = x



, that is, for any s in

S,anyx in X,andanyα in X

, x can be uniquely determined by s and

λ(s, xα). In fact, the only if part is trivial. To prove the if part, suppose that

λ(s, α)=λ(s, α



)fors in S and α, α



in X

.Weproveα = α



. Denote

α = x

..., α



= x



...,forsomex

, x



in X, i =0, 1,... We prove

30 1. Introduction

= x



by induction on i. Basis : i =0.Sinceforanyt in S,anyx, x



in X,andanyβ, β



in X

, λ(t, xβ)=λ(t, x



) implies x = x



,wehave

= x



. Induction step : Suppose that x

= x



holds for i =0, 1,...,n.

Denote s



= δ(s, x

...x

). Then s



= δ(s, x



...x



). From λ(s, x

...)=

λ(s, x



...), we have λ(s



n+1

n+2

...)=λ(s





n+1



n+2

...). Since for

any t in S,anyx, x



in X,andanyβ, β



in X

, λ(t, xβ)=λ(t, x



) implies

x = x



,wehavex

n+1

= x



n+1

. We conclude that x

= x



holds for any i  0,

that is, α = α



A ﬁnite automaton M = X, Y, S, δ, λ is said to be weakly invertible

with delay τ , τ being a nonnegative integer, if for any s in S and any x

X, i =0, 1,...,τ, x

can be uniquely determined by s and λ(s, x

...x

that is, for any s in S and any x

, x



in X, i =0, 1,...,τ, λ(s, x

...x

λ(s, x



...x



) implies x

= x



Evidently, if M is weakly invertible with delay τ,thenM



= X, Y ,



, δ



, λ



 is weakly invertible with delay τ inthecasewhereM



≺ M or



 M.

Clearly, if M is weakly invertible with delay τ,thenM is weakly invertible.

Below we prove that its converse proposition also holds.

Let M = X, Y, S, δ,λ be a ﬁnite automaton. Construct a graph G



(V,Γ) as follows. Let



= {(δ(s, x),δ(s, x



)) | x = x



,λ(s, x)=λ(s, x



),x,x



∈ X, s ∈ S}.

InthecaseofR



= ∅, let the vertex set V of G



be the minimal subset of

S × S satisfying the following conditions: (a) R



⊆ V ,(b)if(s, s



) ∈ V and

λ(s, x)=λ(s



)forx, x



∈ X,then(δ(s, x),δ(s



)) ∈ V . Let the arc set Γ

of G



be the set of all arcs ((s, s



), (δ(s, x),δ(s



))) satisfying the condition:

(s, s



) ∈ V , x, x



∈ X,andλ(s, x)=λ(s



). In the case of R



= ∅,letG



be the empty graph.

Theorem 1.4.3. M is weakly invertible if and only if G



has no circuit.

Moreover, if G



has no circuit and the level of G



is ρ − 1, then M is

weakly invertible with delay ρ +1 and not weakly invertible with delay τ for

any τ  ρ.

Proof. Replacing s



, R, G

, “invertible” in the proof of Theorem 1.4.1

by s

, R



, G



, “weakly invertible”, respectively, we obtain a proof of the

theorem. Below we give the details.

Suppose that G



has a circuit, say w. From the construction of G



,for

anyvertexonw, there exists a path of which the terminal vertex is the vertex

on w and the initial vertex is in R



. Thus there exists a path u

...u

such

that the initial vertex of u

is in R



and u

r+1

...u

is a circuit for some

r,1 r  k.Let(s



) be the initial vertex of u

, i =1, 2,...,k.Then