INTELIGENCIA ARTIFICIAL, Vol 14, No 48 (2010)

Efficient Computation of the Degree of Belief for a Subclass of Two Conjunctive Forms

Guillermo De Ita, Carlos Guillén

Abstract


Assuming a Knowledge Base (KB) ∑ expressed by a two Conjunctive Form (2-CF),
we determine a set of recurrence equations which allow us to design an
incremental technique for counting models of ∑ by a simple traversal of
its constraint graph G_∑. We show that if the constraint graph of ∑ has no intersecting cycles
then it is possible to count efficiently the number of models of ∑.

One of the advantages of our technique, furthermore that it has
a polynomial time complexity, is that applying it backwards, we can
determine the charge (the number of true and false logical values) that
each variable has into the set of models of the input 2-CF.

The charge of the variables allow us to design an efficient scheme of reasoning.
Given the KB ∑ such that G∑ has no intersecting cycles, and new information F (a literal or a binary clause), the degree of belief in F with respect to ∑, denoted as P_F|∑, is computed efficiently even in the case that F is not a logical consequence from ∑.

Full Text: PDF