Databases Reference
In-Depth Information
This proves Theorem 2(ii).
Proof of Theorem 2(iii).
To prove that there is a situation in which
PP
[Public]
is neither recursive nor a cylinder, we show that no partial recursive function
e(e
0) is a semi-cylinder function for
PP
[Public]. Then by Young's result
on semi-cylinders [YOUN63], it follows immediately that
PP
[Public] is neither
recursive nor a cylinder.
The following graph theory concepts are needed for the proof of the result.
≥
Definitions
Let D be a digraph whose points (nodes) are in N and whose lines (edges) are
ordered pairs of natural numbers. By x
∈
D we mean x is a point in D. If x
∈
D
and y
y (D) we mean that either x = y or (x, y) is a directed
line in D, or there exist distinct points y1, y2, .. . yn such that x = y1, y = yn
and for each i (1
∈
D then by x
→
D, then D(x) is the connected
component of D containing x. The in-degree (out-degree) respectively of x is
the number of points y such that (y, z) ((x, y) respectively) is a directed line in
D. We assume that the in-degree as well as out-degree of each point is atmost
2. A point is a root (leaf respectively) if its in-degree (out-degree respectively)
is 0. We denote r(x) (t(x) respectively)) to be the least point y such that y is
a root (leaf respectively) and y
≤
i
≤
n-1) yi
→
yi+1.Ifx
∈
→
x (x
→
y respectively) in D.
By x//y is meant x and y belong to different connected components. If x/y,
then x and y belong to the same connected component, but it is not the case
that x
x. If (x,y) and (x,z) are lines, then z is denoted by y* with
respect to x (note that y is denoted by z* with respect to x).
A digraph is labeled if some of its points are distinguished from one another
by names drawn from some given infinite list. By the term introduce the labels
K1,K2, ----Kn(n
→
y or y
→
1) to the digraph D is mean the following: Find the least
n numbers x1, x2, ....xn which are not points in D. Adjoin these numbers as
points in D so that each point forms a new connected component. Label each
xi (1
≥
n) by Ki.
By the term extend the digraph D to digraph D* is meant the following:
Let r1, r2, ... rn be the roots of D and let t1, t2, .....tm be its leaves.
Find the least 4n+4m numbers x
1
<x
2
<x
3
< .....X
4
n
<y
1
<y
2
<
y
3
<....y
4
m
not in D. Adjoin these numbers as new points and include the
following lines:
(x1,r1), (x2,r1), (x1,x3), (x2,x4), (x5,r2), (x6,r2), (x5,x7), (x6,x8), - - - - - -
(x4n-3, rn), (x4n-2, rn), (x4n-3,x4n-1), (x4n-2, x4n), (t1,y1), (t1,y2), (y3,y1),
(y4,y2), (t2,y5), (t2,y6), (y7,y5), (y8,y6), ...., (tm,y4m-3), (tm,y4m-2), (y4m-
1, y4m-3), (y4m,y4m-2).
The resulting digraph is D*.
A point is private if a privacy constraint classified that point.
Figure 3 illustrates the concepts we have described above.
≤
i
≤
