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)