Information Technology Reference
In-Depth Information
Binary Su
cientness Postulate, BSP.
For a partial state description ʔ
(
a
1
,
...,a
m
)
with signature mn as on page 210:
w
(
ʲ
k
(
a
m
+1
)
|
ʔ
)
depends only on m
k
and m,
and for
1
≤
s<t
≤
m with
s, t
∈
/
A and v
s
=
k, v
t
=
c,
w
(
ʳ
[
k,c,h,d
]
(
a
s
,a
t
)
|
ʔ
)
depends only on n
[
k,c,h,d
]
and n
k,c
, and on whether or not
ʳ
[
k,c,h,d
]
doubles.
Note that BSP implies BEx.
Theorem 2.
Let w be a probability function on L and assume p
+
q
≥
2
, q
≥
1
.
Then w satisfies Ex, Reg and BSP just when there are μ, ʻ
]
such that
for a partial state description ʔ
(
a
1
,...,a
m
)
given by (2) with signature mn we
have
∈
(0
,
∞
ʔ
)=
m
k
+
μ
2
p
+
q
m
+
μ
w
(
ʲ
k
(
a
m
+1
)
|
,
(9)
1
,...,
2
q
and for s, t
∈{
1
,...,m
}
, s<t,
s, t
∈
/
A, h, d
∈{
}
and k
=
v
s
, c
=
v
t
we have
ʻ
2
2
q
ʔ
)=
n
[
k,c,h,d
]
+
w
(
ʳ
[
k,c,h,d
]
(
a
s
,a
t
)
|
[
k
=
c
or (
k
=
c
and
h
=
d
)]
,
(10)
n
k,c
+
ʻ
n
[
k,k,h,d
]
2
ʻ
2
2
q
+
w
(
ʳ
[
k,k,h,d
]
(
a
s
,a
t
)
|ʔ
)=
[
k
=
c
and
h
=
d
])
.
(11)
n
k,k
+
ʻ
Before proving the theorem, note that from (5) we can see that the above
formulae uniquely define a probability function
C
ʻ,μ
satisfying Ex and Reg.
Explicitly, for
ʔ
as above,
C
ʻ,μ
(
ʔ
)=
k
m
k
−
1
h,d
n
[
k,c,h,d
]
−
1
μ
ʻ
j
=0
(
j
+
2
p
+
q
)
(
j
+
2
2
q
)
j
=0
m−
1
j
=0
(
j
+
μ
)
n
k,c
−
1
j
=0
(
j
+
ʻ
)
k<c
h
n
[
k,k,h,h
]
−
1
h<d
n
[
k,k,h,d
]
−
1
ʻ
(
2
+
ʻ
(
j
+
2
2
q
)
2
2
q
)
j
=0
j
=0
×
n
k,k
−
1
j
=0
n
k,k
−
1
j
=0
(
j
+
ʻ
)
(
j
+
ʻ
)
k
k
where
k,c
range through 1
,...,
2
p
+
q
and
h, d
range through 1
,...,
2
q
and the
empty product equals 1.
Proof of Theorem 2.
Let
w
be a probability function satisfying Ex, Reg and
BSP. Define
w
1
on the unary language
L
1
=
{
R
1
,...,R
p
,P
1
,...,P
q
}
by
w
1
(
ʘ
)=
w
(
ʘ
Q
)
where
ʘ
is a state description of
L
1
and
ʘ
Q
obtains from it by changing each
P
i
(
a
j
)to
Q
i
(
a
j
,a
j
).
w
1
extends to a probability function satisfying Ex, Reg and
