Information Technology Reference
In-Depth Information
JSP so by the classical unary result it is equal to c μ for some μ
(0 ,
]. It
follows that (9) holds for w .
Now fix k and c and assume k
= c . Then none of the 2 2 q of the ʳ [ k,c,h,d ] double.
Let g ( r, n )standfor w ( ʳ [ k,c,h,d ] ( a s ,a t )
|
ʔ ( a 1 ,...,a m )) where s, t
∈{
1 ,...,m
}
and ʔ ( a 1 ,...,a m )isasabovewith v s = k , v t = c ,
A , n = n k,c and
r = n [ k,c,h,d ] . Using Theorem 1 we can argue just as in the classical unary
case (see [6, Chapter 17]) to obtain (10) for w with some ʻ
s, t
/
]forthese
particular k , c . Note that by BSP it also follows that the ʻ obtained for other
pairs k
(0 ,
= c must be the same.
Adapting the same method we can also resolve the remaining case: Consider
some fixed k
1 ,..., 2 p + q
∈{
}
.L t g ( r, n )and h ( r, n ) and r
w ( ʳ [ k,k,h,d ] ( a s ,a t )
|
ʔ ( a 1 ,...,a m )) ( h
= d ), w ( ʳ [ k,k,h,h ] ( a s ,a t )
|
ʔ ( a 1 ,...,a m )) re-
spectively where s, t
∈{
1 ,...,m
}
and ʔ ( a 1 ,...,a m )isasabove,with v s = v t =
k , s<t ,
A , n = n k,k and r = n [ k,k,h,d ] or r = n [ k,k,h,h ] respectively.
Define ˇ = h (0 , 0) and ʾ = g (0 , 0) and let ʽ be the (unique) element in (0 ,
s, t
/
]
such that
h (1 , 1) = 1+ ˇʽ
1+ ʽ .
(12)
Such a unique ʽ exists since 0 = h (0 , 0)
h (1 , 1) < 1 (by regularity and
1+ ˇx
1+ x
Theorem 1) and the function x
is decreasing from 1 to ˇ as x runs from
0to
.From
2 q
=1
w
ʳ [ k,k,h,d ] ( a 1 ,a 2 )
|
( ʲ k ( a 1 )
ʲ k ( a 2 ))
h,d =1
we find that
2 q ˇ +(2 2 q
2 q ) ʾ =1 .
(13)
We shall first show that to conclude the proof it suces to prove that for all
n
N
r
h ( r, n )= r + ˇʽ
n + ʽ
2 + ʾʽ
n + ʽ
and g ( r, n )=
( r
∈{
0 , 1 ,...,n
}
) .
(14)
= c , h ( r, n )= r + ʻ
This is because by BSP and the above result for k
2 2 q
n + ʻ
for all
1
n
N
and r
∈{
0 , 1 ,...,n
}
so (14) forces ʽ = ʻ and ˇ =
2 2 q and hence by (13)
also ʾ = 2 2 q so (9) and (10) follow.
Hence it remains to prove (14). For n = 0 it follows by the definition of ˇ and
ʾ . Considering e.g.
w ʲ k ( a 1 )
ʳ [ k,k,h,h ] ( a 1 ,a 3 )
ʲ k ( a 2 )
ʲ k ( a 3 )
ʳ [ k,k,h,d ] ( a 1 ,a 2 )
we can see that g (0 , 1) h (0 , 0) = h (0 , 1) g (0 , 0), that is,
ˇg (0 , 1)= ʾh (0 , 1) .
(15)
Search WWH ::




Custom Search