72 2. Mutual Invertibility and Search
In the case of r
1
1, we have j
max
= τ. Therefore,
c
τ
>t
τ
/2=
1+
τ
j=2
p
r
j
+···+r
τ
/2, if r
1
1.
Since the average search amount for executing Algorithm 1 on T
M,s,y
0
...y
l
is
greater than (l +1− τ)c
τ
, it is greater than (l +1− τ )
1+
τ
j=2
p
r
j
+···+r
τ
/2
in the case of r
1
1. We state this result as a theorem.
Theorem 2.3.6. Let M
i
,i=0, 1,...,τ be weakly invertible finite automata
with delay 0 of which input alphabets and output alphabets are X = F
m
.Let
M = C(M
0
,D
X,r
1
,M
1
,D
X,r
2
,M
2
,...,M
τ−1
,D
X,r
τ
,M
τ
)
with 1 r
1
r
2
··· r
τ
m,andM
i
be (m − r
i+1
)-preservable,
i =1,...,τ − 1.Ify
0
...y
l
∈ W
M
l+1,s
and l τ, then the average search
amount for executing Algorithm 1 is greater than
(l +1− τ)
1+
τ
j=2
p
r
j
+···+r
τ
/2.
Finally, we evaluate the search amount in worse case. Consider the search
process when Algorithm 1 is executing. For searching the tree T
M,s,y
0
...y
l
with
y
0
...y
l
∈ W
M
l+1,s
and l τ, in worse cases, all arcs in T
M,s,y
0
...y
l
except some
arcs mentioned below are searched. According to Corollary 2.3.2 (with val-
ues τ − 1, τ − 1 for parameters h, h
, respectively), there are p
r
1
branches
of T
M,δ(s,x
0
...x
l−τ
),y
l−τ +1
...y
l
with level τ − 1; only one in such branches, say
T
x
l−τ +1
M,δ(s,x
0
...x
l−τ
),y
l−τ +1
...y
l
, is searched, because only one path of length l +1
in T
M,s,y
0
...y
l
is searched. Next, according to Corollary 2.3.2 (with values
τ − 1, τ − 2 for parameters h, h
, respectively), there are p
r
2
branches
of T
M,δ(s,x
0
...x
l−τ +1
),y
l−τ +2
...y
l
with level τ − 2; only one in such branches,
say T
x
l−τ +2
M,δ(s,x
0
...x
l−τ +1
),y
l−τ +2
...y
l
, is searched, because only one path of length
l +1 in T
M,s,y
0
...y
l
is searched; and so on. According to Corollary 2.3.2
(with values τ − 1, 2 for parameters h, h
, respectively), there are p
r
τ −2
branches of T
M,δ(s,x
0
...x
l−3
),y
l−2
y
l−1
y
l
with level 2; only one in such branches,
say T
x
l−2
M,δ(s,x
0
...x
l−3
),y
l−2
y
l−1
y
l
is searched, because only one path of length
l +1in T
M,s,y
0
...y
l
is searched. Finally, according to Corollary 2.3.2 (with
values τ − 1, 1 for parameters h, h
, respectively), there are p
r
τ −1
branches of
T
M,δ(s,x
0
...x
l−2
),y
l−1
y
l
with level 1; only two arcs in such a branch are searched,
because only one path of length l +1 in T
M,s,y
0
...y
l
is searched. For any k,
2 k τ , from Corollary 2.3.3 (with value τ − 1,k− 1,k− 2 of the parame-
ter h, h
,l), the numbers of arcs of a branch of T
M,δ(s,x
0
...x
l−k
),y
l−k+1
...y
l
with
level k − 1is1+
τ
j=τ −k+2
p
τ
i=j
r
i
. Thus the number of arcs which are not
searched is