Information Technology Reference
In-Depth Information
A
j
=
A
j
for
j
=
k
and
A
k
=
A
k
∪{¬
L
}
for some
k
≤
n
. By induction
where
hypothesis, a clause
D
subsuming
C
can be derived from
A
at
A
k
by Algorithm 3. In
fact, if
D
is derived at some
A
j
(
j
=
k
)
, then it can be sent to
A
k
because
D
belongs
to
P
and hence
D
∈L
(
l
(
j, k
))
. We now construct a distributed proof of a clause
D
subsuming
C
from
by adding
L
to
C
appearing in the distributed proof of
D
from
A
. This is possible because
L
A
∈L
(
l
(
i,j
))
for any
i,j
∈
V
by the constructions (3)
and (4). Hence,
D
can be derived at
A
k
by Algorithm 3.
Algorithm 3 can be seen as a simple extension of partition-based theorem proving
by Amir and McIlraith [3] since the communication languages are extended to in-
clude the literals from the production field. However, this small change is essential for
consequence finding. For theorem proving, Amir and McIlraith [3, Section 2.3] have
mentioned how to deal with a query
Q
that comprise symbols drawn from multiple
partitions. For this, a new partition
A
Q
is added with the language
S
(
A
Q
)=
S
(
Q
)
and
Q
. Following addition of this new partition,
Cycle Cut must be run on the new graph, and then refutation is performed at
A
Q
consists of the clausal form of
¬
A
Q
.This
method, however, cannot be elegantly applied for consequence finding in general since
we do not know the exact theorems or even the possible candidates of theorems to be
found in consequence finding. Of course, we can consider the production field
P
=
L
for restricted consequence finding. But even with a small
,tofind
all consequences with theorem proving we need to query for
a
,
b
,
c
, then possibly
a
P
,say
L
=
{
a,b,c
}
∨
b
,
a
c
and
checking all possible proofs would also work but have high complexity too). Alterna-
tively, considering the new partition
∨
c
and
b
∨
c
, and eventually
a
∨
b
∨
c
(though querying the last clause
a
∨
b
∨
A
P
with the language
S
(
L
)
makes the graph more
tightly connected and cyclic. Applying Cycle Cut would then the resulting communi-
cation language of an existing edge to include
S
(
L
)
, which has a similar effect as the
equation (3).
Another important change from the MP algorithm by Amir and McIlraith [3] is to use
the production field
P
i
=
l
(
i,j
)
±
in Step 3 of Algorithm 3 for consequence finding.
This restricts the computations that needs to be done and thus improves efficiency. The
use of production fields also enables us to emulate
default reasoning
by adding each
default literal in a production field to be skipped [14,15]. Hence, our algorithm can be
extended to
partition-based default reasoning
.
4
Cooperative Consequence Finding
Partition-based distributed consequence finding is particularly useful when we have a
large knowledge base that should be divided to easily handle each piece of knowledge.
However, the algorithm can also be applied to naturally distributed knowledge-based
systems in which each theory of an agent grows individually so that multiple agents may
have the same knowledge and information simultaneously. Although such possessed
knowledge is considered to be redundant in partition-based theories, there is no problem
in
decentralized
,
multi-agent
and
peer-to-peer
systems. In such naturally distributed
systems, one problem would be to break cycles in the induced graph because no agent
should not know an optimal way to minimize the cost of cutting cycles (although we
could devise a decentralized version of Cycle Cut algorithm).
