=Paper=
{{Paper
|id=Vol-451/paper-11
|storemode=property
|title=The SLGAD Procedure for Inference on Logic Programs with Annotated Disjunctions
|pdfUrl=https://ceur-ws.org/Vol-451/paper15riguzzi.pdf
|volume=Vol-451
|dblpUrl=https://dblp.org/rec/conf/rcra/Riguzzi08
}}
==The SLGAD Procedure for Inference on Logic Programs with Annotated Disjunctions==
https://ceur-ws.org/Vol-451/paper15riguzzi.pdf
The SLGAD Procedure for Inference on Logic
Programs with Annotated Disjunctions
Fabrizio Riguzzi
ENDIF, Università di Ferrara, Via Saragat, 1, 44100 Ferrara, Italy.
fabrizio.riguzzi@unife.it
No Institute Given
Abstract
Logic Programs with Annotated Disjunctions (LPADs) allow to ex-
press probabilistic information in logic programming. The semantics
of an LPAD is given in terms of well founded models of the normal
logic programs obtained by selecting one disjunct from each ground
LPAD clause. The paper presents SLGAD resolution that computes
the (conditional) probability of a ground query from an LPAD and
is based on SLG resolution for normal logic programs. The perfor-
mances of SLGAD are evaluated on classical benchmarks for normal
logic programs under the well founded semantics, namely the stalemate
game and the ancestor relation. SLGAD is compared with Cilog2 and
SLDNFAD, an algorithm based on SLDNF, on the programs that are
modularly acyclic. The results show that SLGAD deals correctly with
cyclic programs and, even if it is more expensive than SLDNFAD on
problems where SLDNFAD succeeds, is faster than Cilog2 when the
query is true in an exponential number of instances.
Topics: Probabilistic Logic Programming, Well Founded Semantics,
Logic Programs with Annotated Disjunctions, SLG resolution.
1 Introduction
The combination of logic and probability is a long standing problem in
philosophy and artificial intelligence, dating back to [2]. Recently, the work
on this topic has thrived leading to the proposal of novel languages that
combine relational and statistical aspects, such as Independent Choice Logic,
ProbLog, Stochastic Logic Programs, Bayesian Logic Programs, PRISM and
CLP(BN ). Each of these languages has a different semantics that makes it
suitable for different domains: the identification of the best setting for each
language is currently under study.
When we are reasoning about actions and effects and we have causal
independence among different causes for the same effect, Logic Programs
with Annotated Disjunctions (LPADs) [15] seem particularly suitable. They
extend logic programs by allowing program clauses to be disjunctive and
by annotating each atom in the head with a probability. A clause can be
causally interpreted in the following way: the truth of the body causes the
Proceedings of the 15th International RCRA workshop (RCRA 2008):
Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion
Udine, Italy, 12–13 December 2008
truth of one of the atoms in the head non-deterministically chosen on the
basis of the annotations. The semantics of LPADs is given in terms of the
well founded model [13] of the normal logic programs obtained by selecting
one head for each disjunctive clause.
In order to compute the (conditional) probability of queries, various
options are possible. [14] showed that ground acyclic LPADs can be con-
verted to Bayesian networks. However, the conversion requires the complete
grounding of the LPAD, thus making the technique impractical.
[14] also showed that acyclic LPADs can be converted to Independent
Choice Logic (ICL) programs. Thus inference can be performed by using
the Cilog2 system [9]. An algorithm for performing inference directly with
LPADs was proposed in [10]. The algorithm, that will be called SLDNFAD
in the following, is an extension of SLDNF derivation and uses Binary Deci-
sion Diagrams, similarly to what is presented in [8] for the ProbLog language.
Both Cilog2 and SLDNFAD are complete and correct for programs for which
the Clark’s completion semantics [7] and the well founded semantics coin-
cide, as for acyclic [1] and modularly acyclic programs [12].
In this paper we present the SLGAD top-down procedure for performing
inference with possibly (modularly) cyclic LPADs. SLGAD is based on the
SLG procedure [4] for normal logic programs and extends it in a minimal
way.
SLGAD is evaluated on classical benchmarks for well founded semantics
inference algorithms, namely the stalemate game and the ancestor relation.
In both cases, various extensional databases are considered, encoding linear,
cyclic or tree-shaped relations. SLGAD is compared with Cilog2 and SLD-
NFAD on the modularly acyclic programs. The results show that SLGAD is
able to deal with cycles and, while being more expensive than SLDNFAD on
problems where SLDNFAD succeeds, is faster than Cilog2 when the query
is true in an exponential number of instances.
The paper is organized as follows. In Section 2 we present the syntax
and semantics of LPADs together with some properties of normal programs
and of LPADs. Section 3 provides the definition of the SLGAD procedure,
Section 4 presents the experiments and, finally, Section 5 concludes and
presents directions for future work.
2 Preliminaries
A Logic Program with Annotated Disjunctions [15] T consists of a finite set
of formulas of the form
(H1 : α1 ) ∨ (H2 : α2 ) ∨ . . . ∨ (Hn : αn ) : −B1 , B2 , . . . Bm
called annotated disjunctive clauses. In such a clause the Hi are logical
atoms, the Bi are logical literals and the αi are real numbers in the interval
2
!
[0, 1] such that ni=1 αi ! 1. The head of LPAD clauses implicitly contains
an extra atom null that!does not appear in the body of any clause and
whose annotation is 1 − ni=1 αi .
the form above, we define head(C) as {(Hi : αi )|1 !
For a clause C of !
i ! n} ∪ {(null : 1 − ni=1 αi )}, body(C) as {Bi |1 ! i ! m}, Hi (C) as Hi
and αi (C) as αi . For example, the formula
C = itching(X, strong) : 0.3 ∨ itching(X, moderate) : 0.5 : −measles(X).
is an annotated disjunctive clause in which
head(C) = {(itching(X, strong) : 0.3), (itching(X, moderate) : 0.5),
(null, 0.2)},
body(C) = {measles(X)}
Moreover, H1 (C) = itching(X, strong), α1 (C) = 0.3 and so on.
Let HB (T ) be the Herbrand base of T and let IT be the set of all the
possible Herbrand interpretations of P (i.e., subsets of HB (T )). If T contains
function symbols, then HB (T ) is infinite, otherwise it is finite.
In order to define the semantics of a non-ground LPAD T , we must
generate the grounding T ! of T . Each ground annotated disjunctive clause
represents a probabilistic choice among the ground non-disjunctive clauses
obtained by selecting only one head. The intuitive interpretation of a ground
clause is that the body represents an event that, when it happens (i.e. it
becomes true), causes an atom in the head (an effect) to happen (i.e. to
become true). If the atom selected is null, this is equivalent to having no
effect.
The semantics of an LPAD, given in [15], requires the grounding to be
finite, so the program must not contain function symbols.
By choosing a head atom for each ground clause of an LPAD we get a
normal logic program called an instance of the LPAD. A probability dis-
tribution is defined over the space of instances by assuming independence
among the choices made for each clause.
A choice κ is a set of triples (C, θ, i) where C ∈ T , θ is a substitution
that grounds C and i ∈ {1, . . . , |head(C)|}. (C, θ, i) means that, for ground
clause Cθ, the head Hi θ was chosen. A choice κ is consistent if (C, θ, i) ∈
κ, (C, θ, j) ∈ κ ⇒ i = j, i.e. only one head is selected for a ground clause.
For different groundings of the same clause, different heads can be chosen: it
is possible for a consistent choice κ to be such that (C, θ, i) ∈ κ, (C, θ! , j) ∈ κ
with θ &= θ! and i &= j¿
A consistent choice is a selection σ if for each clause Cθ in the grounding
of T there is a triple (C, θ, i) in σ. We denote the set of all selections of a
program T by ST . Note that, since the program T does not contain function
symbols, the grounding of T is finite and so is σ.
3
A consistent choice κ identifies a normal logic program Tκ = {(Hi (C) :
−body(C))θ|(C, θ, i) ∈ κ} that is called a sub-instance of T . If σ is a selec-
tion, Tσ is called an instance. For a consistent choice κ, let U (κ) be the set
of instances that are supersets of Tκ , i.e., the set of instances Tσ with σ a
selection such that σ ⊇ κ.
We now assign a probability to a consistent choice κ. The probability Pκ
of a consistent choice κ is"the product of the probabilities of the individual
choices made, i.e. Pκ = (C,θ,i)∈κ αi (C). The probability of instance Tσ is
Pσ . Note that if T contains function symbols, σ would be infinite and so
Pσ would always be 0, being an infinite product of numbers all smaller than
one.
The semantics of the instances of an LPAD is given by the well founded
semantics (WFS) [13]. Given a normal program T , we call W F M (T ) its well
founded partial model. For each instance Tσ , we require that the W F M (Tσ )
is two-valued, since we want to model uncertainty solely by means of disjunc-
tions. An LPAD T is called sound iff, for each selection σ in ST , W F M (Tσ )
is two-valued. In the following we consider only sound programs.
The probability of an interpretation I ∈ IT according to T is given by
the sum of the probabilities of the instances that have I as the well founded
model, i.e. #
PT (I) = Pσ .
σ∈ST ,W F M (Tσ )=I
The probability of a formula χ according to T is given by the sum of the
probabilities of interpretations in which the formula is true, i.e.
#
PT (χ) = P (I).
I∈IT ,I|=χ
Equivalently, the probability of a formula χ is given by the sum of the
probabilities of the instances in which the formula is true according to the
WFS: #
PT (χ) = Pσ
Tσ |=W F S χ
Note that this semantics is well defined because, since the instances are finite,
the probabilities Pσ are not all 0. A semantics for LPADs with function
symbols must take a different approach and is subject of future work.
Example 1. Consider the dependency of a person’s itching from him having
allergy or measles:
C1 = itching(X, strong) : 0.3 ∨ itching(X, moderate) : 0.5 : −measles(X).
C2 = itching(X, strong) : 0.2 ∨ itching(X, moderate) : 0.6 : −allergy(X).
C3 = allergy(david).
C4 = measles(david).
This program models the fact that itching can be caused by allergy or measles.
4
Measles causes strong itching with probability 0.3, moderate itching with
probability 0.5 and no itching with probability 1 − 0.3 − 0.5 = 0.2; allergy
causes strong itching with probability 0.2, moderate itching with probability
0.6 and no itching with probability 1 − 0.2 − 0.6 = 0.2.
For example, itching(david, strong) is true in 5 of the 9 instances of the
program and its probability is
0.3 · 0.2 + 0.3 · 0.6 + 0.3 · 0.2 + 0.5 · 0.2 + 0.2 · 0.2 = 0.44
Example 2. Consider a probabilistic game in which a position is winning
with a certain probability if there is a move to another position that is losing
for the opponent. This game can be represented by
win(X, white) : 0.8 : − move(X, Y ), ¬win(Y, black).
win(X, black) : 0.8 : − move(X, Y ), ¬win(Y, white).
plus facts for the move predicate.
If move represents an acyclic relation1 , then the program is sound. Oth-
erwise, there are instances that do not have a total well founded model,
namely those where the win head is selected for all the ground clauses whose
instance of the move(X, Y ) atom is in the cycle.
An LPAD is (modularly) acyclic [12] if all of its instances are (modularly)
acyclic.
An LPAD is range restricted if all the variables appearing in the head of
clauses also appear in the body.
3 SLGAD Resolution Algorithm
In this section we present Linear resolution with Selection function for Gen-
eral logic programs with Annotated Disjunctions (SLGAD) that extends SLG
resolution [6, 4] for dealing with LPADs.
In the following we give a brief sketch of the implementation of SLG
resolution as presented in [4]. SLG builds a search forest for a subgoal (i.e.
a (partially instantiated) atom) by performing depth first search. Besides a
stack S of subgoals, SLG keeps a table T in which it stores, for each subgoal
A considered in the computation, the set of answers (i.e. instantiations of
the subgoal) already computed Anss, the set of resolvents that wait for new
answers for A, separated into a set P oss that has A selected and a set N egs
that has ¬A selected, and a boolean flag Comp that indicates whether A
has been completely evaluated. After every resolution step for a subgoal A,
1
A binary relation R is acyclic if the graph containing an edge from node a to node b
if R(a, b) holds is acyclic
5
SLG tests whether all possible answers for A have been computed: if so, it
sets Comp to true. When it encounters a case of a possible loop through
negation, it “delays” the selected literal ¬A by inserting it into a dedicated
data structure of the resolvent. Delayed literals are then removed if they
turn out to be true.
SLG uses X-clauses to represent resolvents with delayed literals.
Definition 3.1 (X-Clause). An X-clause X is a clause of the form A: −D|B
where A is an atom, D is a sequence of ground negative literals and (possibly
unground) atoms and B is a sequence of literals. Literals in D are called
delayed literals. If B is empty, an X-clause is called an X-answer clause.
An ordinary program clause is seen as a X-clause with an empty set of
delayed literals.
SLG is based on the operation of SLG resolution and SLG factoring on
X-clauses. In particular, SLG resolution is performed between an X-clause
A : −|A and a program clause or between an X-clause and an X-answer.
In SLGAD, X-clauses are replaced by XD-clauses.
Definition 3.2 (XD-Clause). An XD-clause G is a quadruple (X, C, θ, i)
where X is an X-clause, C is a clause of T , θ is a substitution for (some
of ) the variables of C and i ∈ {1, . . . , |head(C)|}. Let X be A : −D|B: if B
is empty, the XD-clause is called an XD-answer clause.
In SLGAD, SLG resolution between an X-clause A : −|A and a program
clause is replaced by SLGAD goal resolution and SLG resolution between
an X-clause and an X-answer is replaced by SLGAD answer resolution.
Definition 3.3 (SLGAD Goal Resolution). Let A be a subgoal and let C
be a clause of T such that A is unifiable with an atom Hi in the head of C.
Let C ! be a variant of C with variables renamed so that A and C ! have no
variables in common. We call the XD-clause
((A : −|body(C ! ))θ, C ! , θ, i)
the SLGAD goal resolvent of A with C on head Hi , where θ is the most
general unifier of A and Hi! . C ! is kept in the resolvent because we must be
able to recover the ground program clause to which the XD-clause refers.
Definition 3.4 (SLGAD Answer Resolution). Let G be an XD-clause
(A : −D|L1 , . . . , Ln , C, θ, i)
where n > 0 and Lj be the selected atom. Let F be an XD-answer clause with
an empty set of delayed literals, and let F ! , of the form (A! : −|, E ! , θ! , i! ),
be a variant of F with variables renamed so that G and F ! have no variables
in common. If Lj and A! are unifiable then we call the XD-clause
((A : −D|L1 , . . . , Lj−1 , Lj+1 , . . . , Ln )δ, C, θδ, i)
6
Figure 1: Procedure SLGAD
1 function SLGAD(A,T )
2 begin
3 Initialize Count, T , S, DFN, PosMin and NegMin as in SLG;
4 κ := ∅;
5 let ψ be the set of all the values for κ after an execution of
6 SLG SUBGOAL(A,PosMin,NegMin) such that T contains
7 A as !an answer;
8 return κ∈ψ Pκ
9 end
the SLGAD answer resolvent of G with F , where δ is the most general unifier
of A! and Lj .
SLG factoring is replaced by SLGAD factoring.
Definition 3.5 (SLGAD Factoring). Let G be an XD-clause
(A : −D|L1 , . . . , Ln , C, θ, i)
where n > 0 and Lj be the selected atom. Let F be an XD-answer clause,
and let F ! , of the form (A! : −D! |, E ! , θ! , i! ), be a variant of F with variables
renamed so that G and F ! have no variable in common. If D! is not empty
and Lj and A! are unifiable then the SLGAD factor of G with F is
((A : −D, Lj |L1 , . . . , Lj−1 , Lj+1 , . . . , Ln )δ, C, θδ, i)
where δ is the most general unifier of A! and Lj .
SLGAD goal resolution, SLGAD answer resolution and SLGAD factoring
are equivalent to their SLG counterparts on the underlying X-clauses.
The SLGAD algorithm is defined with a procedural pseudo-code that
contains a non-deterministic choice point. The main function of the algo-
rithm is shown in Figure 1. It takes as input a ground atom A and a program
T and it keeps four global variables. The first three are shared with SLG:
the table T , the stack of subgoals S and the counter Count. The fourth
variable is specific of SLGAD and is used to record all the clauses used in
the SLGAD derivation together with the heads selected: it is a choice κ,
i.e., a set of triples (C, θ, i) where C is a clause of T , θ is a substitution
that grounds C and i is the index of an atom in the head of C. We assume
that the global variables are copied in different branches of the search tree
generated by the choice points, so that a modification in a branch does not
influence the other branches. The search tree is explored depth first.
The SLGAD algorithm modifies in a minimal way SLG: it is composed of
the same procedures as SLG [4], plus procedure ADD CLAUSE. We refer to
7
Figure 2: Procedures SLG SUBGOAL
1 procedure SLG SUBGOAL(A,PosMin,NegMin)
2 begin
3 for each SLGAD goal resolvent G of A with some clause C ∈ T
4 on the head Hi do begin
5 SLG NEWCLAUSE(A, G,PosMin,NegMin);
6 end;
7 SLG COMPLETE(A,PosMin,NegMin,κ);
8 end;
[4] for a detailed description of the individual SLG procedures, here we report
only the differences, that are indicated in italics in the figures. Procedure
SLG SUBGOAL (see Figure 2) differs from that of SLG because in line 3
each SLGAD goal resolvent is considered rather than each SLG resolvent.
Procedure SLG NEWCLAUSE performs resolution on the selected positive
or negative literal in the body of the clause or adds an answer if the body is
empty. SLG NEWCLAUSE is the same as in SLG with X-clauses replaced
by XD-clauses. The main difference is in procedure SLG ANSWER (see
Figure 3) where a call to ADD CLAUSE is added in line 4.
If the answer G is not subsumed by an answer already present in the
table, ADD CLAUSE is called (see Figure 4) that modifies κ and returns a
Boolean value to SLG ANSWER in the variable Derivable. If G = (X, C, θ, i)2 ,
ADD CLAUSE may add a new triple (C, θ, j) to the current κ set. If the pro-
gram is range restricted, Cθ is ground. ADD CLAUSE first checks whether
the clause Cθ already appears in the current choice with a head index differ-
ent from i: if so, it fails the derivation. Otherwise, it non-deterministically
selects a head index j from {1, . . . , |head(C)|}: if j = i this means that
the subgoal in the head is derivable in the sub-instance represented by κ,
so it sets Derivable to true. If j &= i, then Derivable is set to false. In
backtracking, all elements of {1, . . . , |head(C)|} are selected.
Since every clause relevant to a subgoal is eventually reduced to an XD-
-answer, it is sufficient to update κ only in SLG ANSWER by means of
ADD CLAUSE. The cases where j &= i are necessary because we must con-
sider also the possibility that the subgoal A is derived not using head i of
clause Cθ. It may be that A could be derived in a possibility j &= i us-
ing other clauses and/or that the possibility j is used to derive a subgoal
necessary for this second derivation branch: if we do not consider these
possibilities we could miss some explanations for A.
2
C is the clause of the program from which the XD-clause G was obtained by SL-
GAD goal resolution, i is the index of the head used in the goal resolution and θ is the
composition of the substitutions of all the derivations and factorings performed on G
8
Figure 3: Procedure SLG ANSWER
1 procedure SLG ANSWER(A, G,PosMin,NegMin)
2 begin
3 if G is not subsumed by any answer in Anss(A) in T then
3 begin
4 ADD CLAUSE(G,Derivable);
5 if Derivable then begin
6 insert G into Anss(A);
7 if G has no delayed literals then begin;
8 reset N egs(A) to empty;
9 let L be the list of all pairs (B, H ! ), where
10 (B, H) ∈ P oss(A) and
11 H is the SLGAD answer resolvent of H with G;
12 for each (B, H ! ) in L do begin
13 SLG NEWCLAUSE(B,H’,PosMin,NegMin);
14 end;
15 end else begin /* G has a non empty delay */
16 if no other answer in Anss(A) has the same head
17 as G does then
18 begin
19 let L be the list of all pairs (B, H ! ), where
20 (B, H) ∈ P oss(A)
21 and H is the SLGAD factor of H with G;
22 for each (B, H ! ) in L do begin
23 SLG NEWCLAUSE(B, H ! ,PosMin,NegMin);
24 end;
25 end;
26 end;
27 end;
28 end;
29 end;
9
Figure 4: Procedure ADD CLAUSE
1 procedure ADD CLAUSE(G,Derivable)
2 begin
3 let G be (X, C, θ, i);
4 if ∃k : (C, θ, k) ∈ κ, k &= i then begin
5 fail;
6 end else begin
7 choose an index j from {1, . . . , |head(C)|} (choice point);
8 if i = j then begin
9 Derivable:= true;
10 end else begin
11 Derivable:= false;
12 end
13 κ := κ ∪ {(C, θ, j)};
14 end
15 end
SLG ANSWER then behaves differently depending on the value of Deriv-
able: if it is true, a new answer has been found so the rest of the code of
the SLG ANSWER procedure of SLG is performed with X-clauses replaced
by XD-clauses, otherwise it exits without modifying the global variables.
Procedure SLG POSITIVE, that performs resolution on a positive lit-
eral, modifies the one of SLG by replacing SLG resolution with SLGAD an-
swer resolution and SLG factoring with SLGAD factoring. The other SLG
procedure are modified simply by replacing X-clauses with XD-clauses.
If the conditional probability of a ground atom A given another ground
atom E must be computed, rather then computing PT (A ∧ E) and PT (E)
separately, an optimization can be done: we first identify the choices for
all successful derivations for E and then we look for the choices for the
successful derivations of A starting from a choice of E.
SLGAD is sound and complete with respect to the LPAD semantics and
the proof is based on the theorem of partial correctness of SLG [6, 5]: SLG
is sound and complete given an arbitrary but fixed computation rule when
it does not flounder. The proof of soundness and completeness can be found
in [11].
4 Experiments
We tested SLGAD on some synthetic problems similar to those that were
used as benchmarks for SLG [4, 3]: win, ranc and lanc. win is an imple-
mentation of the stalemate game and contains the clause
10
win(X):0.8 :- move(X,Y),\+ win(Y).
ranc and lanc model the ancestor relation with right and left recursion
respectively:
rancestor(X,Y):0.8 :- move(X,Y).
rancestor(X,Y):0.8 :- move(X,Z),rancestor(Z,Y).
lancestor(X,Y):0.8 :- move(X,Y).
lancestor(X,Y):0.8 :- lancestor(Z,Y),move(X,Z).
Various definitions of move are considered: a linear and acyclic relation,
containing the tuples (1, 2), . . . , (N − 1, N ), a linear and cyclic relation,
containing the tuples (1, 2), . . . , (N − 1, N ), (N, 1), and a tree relation, that
represents a complete binary tree of height N , containing 2N − 2 tuples. For
win, all the move relations are used, while for ranc and lanc only the linear
ones.
SLDAG was compared with Cilog2 and SLDNFAD. Cilog2 [9] computes
probabilities by identifying consistent choices on which the query is true
then it makes them mutually incompatible with an iterative algorithm.
SLDNFAD [10] extends SLDNF in order to store choices and computes the
probability with an algorithm based on Binary Decision Diagrams.
For SLGAD and SLDNFAD we used the implementations in Yap Prolog3
available in the cplint suite4 . SLGAD code is based on the SLG system5 .
For Cilog2 we ported the code available on the web6 to Yap. All the exper-
iments were performed on Linux machines with an Intel Core 2 Duo E6550
(2,333 MHz) processor and 4 GB of RAM.
The execution times for the query win(1) to the win program are shown
in Figures 5(a), 5(b) and 6 as a function of N for linear, cyclic and tree move
respectively.
The execution times for the query ancestor(1,N) to the ranc program
are shown in Figures 7(a) and 7(b) as a function of N for linear and cyclic
move respectively.
The execution times for the query ancestor(1,N) to the lanc program
are shown in Figures 8(a) and 8(b) as a function of N for linear and cyclic
move respectively.
win has an exponential number of instances where the query is true and
the graphs show the combinatorial explosion. On win with tree move the
graph in Figure 6 shows the execution times only up to N = 4 because for
N = 4 SLGAD did not terminate after one day.
On the ancestor dataset, the proof tree has only one successful branch
with a number of nodes proportional to N . However, the execution time
3
http://www.ncc.up.pt/∼vsc/Yap/
4
http://www.ing.unife.it/software/cplint/, also included in the CVS version of
Yap
5
http://engr.smu.edu/∼wchen/slg.html
6
http://www.cs.ubc.ca/spider/poole/aibook/code/cilog/CILog2.html
11
70
SLGAD SLGAD
600 Cilog2 60
SLDNFAD
500
50
Time (s)
Time (s)
400 40
300 30
200 20
100 10
0 0
5 10 15 20 25 30 5 10 15 20 25
N N
(a) Linear move. (b) Cyclic move.
Figure 5: Execution times for win with linear and cyclic move.
3
SLGAD
Cilog2
2.5 SLDNFAD
2
Time (s)
1.5
1
0.5
0
1 2 3 4
N
Figure 6: Execution times for win with tree move
SLGAD SLGAD
Cilog2 7000
4000 SLDNFAD
6000
Time (s)
Time (s)
3000 5000
4000
2000
3000
2000
1000
1000
0 0
0.1 0.5 0.9 1.3 1.7 0.1 0.5 0.9 1.3 1.7
N x 10
4 N x 10
4
(a) Linear move. (b) Cyclic move.
Figure 7: Execution times for ranc
12
SLGAD SLGAD
4000 4000
Time (s)
Time (s)
3000 3000
2000 2000
1000 1000
0 0
0.1 0.5 0.9 1.3 1.7 0.1 0.5 0.9 1.3 1.7
N x 10
4 N x 10
4
(a) Linear move. (b) Cyclic move.
Figure 8: Execution times for lanc.
of SLGAD increases more than linearly as a function of N because each
derivation step requires a lookup and an insert into the table T that is
implemented as a tree-like data structure (2-3 tree in the SLG system).
Each insert and lookup take logarithmic time.
SLGAD is compared with Cilog2 and SLDNFAD on the problems that
are modularly acyclic and right recursive, i.e. win with linear and tree
move (Figures 5(a) and 6) and ranc with linear move (Figure 7(a)). On
the other problems a comparison was not possible because Cilog2 and SLD-
NFAD would go into a loop. In win all the algorithms show the combinato-
rial explosion, with SLGAD performing better than Cilog2 and worse than
SLDNFAD. On ranc with linear move (Figure 7(a)), SLGAD takes longer
than Cilog2 and SLDNFAD, with Cilog2, SLDNFAD and SLGAD taking
8.3, 1165.4 and 4726.8 seconds for N = 20000 respectively.
5 Conclusions and Future Works
We have presented the SLGAD top-down procedure for computing the prob-
ability of LPADs queries that is based on SLG and we have experimentally
compared it with Cilog2 and SLDNFAD.
In the future, we plan to study the possibility of answering queries in an
approximate way by returning an upper and a lower bound of the correct
probability. Moreover, we plan to consider extensions of the language such
as aggregates in the body and probabilities in the head that depend on
literals in the body.
References
[1] K. R. Apt and M. Bezem. Acyclic programs. New Generation Comput.,
9(3/4):335–364, 1991.
13
[2] R. Carnap. Logical Foundations of Probability. University of Chicago
Press, 1950.
[3] L. F. Castro, T. Swift, and D. S. Warren. Suspending and resuming
computations in engines for SLG evaluation. In Practical Aspects of
Declarative Languages, volume 2257 of LNCS, pages 332–350. Springer,
2002.
[4] W. Chen, T. Swift, and D. S. Warren. Efficient top-down computa-
tion of queries under the well-founded semantics. J. Log. Program.,
24(3):161–199, 1995.
[5] W. Chen and D. Warren. Towards effective evaluation of general logic
programs. Technical report, State University of New York at Stony
Brook, 1993.
[6] W. Chen and D. S. Warren. Query evaluation under the well founded
semantics. In Symposium on Principles of Database Systems, pages
168–179. ACM Press, 1993.
[7] K. L. Clark. Negation as failure. In Logic and Databases. Plenum Press,
1978.
[8] L. De Raedt, A. Kimmig, and H. Toivonen. ProbLog: A probabilis-
tic prolog and its application in link discovery. In International Joint
Conference on Artificial Intelligence, pages 2462–2467, 2007.
[9] D. Poole. Abducing through negation as failure: stable models within
the independent choice logic. J. Log. Program., 44(1-3):5–35, 2000.
[10] F. Riguzzi. A top down interpreter for LPAD and CP-logic. In Congress
of the Italian Association for Artificial Intelligence, volume 4733 of
LNAI, pages 109–120. Springer, 2007.
[11] F. Riguzzi. The SLGAD procedure for inference on
logic programs with annotated disjunctions. Techni-
cal Report CS-2008-01, University of Ferrara, 2008.
http://www.unife.it/dipartimento/ingegneria/informazione/informati
ca/rapporti-tecnici-1/cs-2008-01.pdf/view.
[12] K. A. Ross. Modular acyclicity and tail recursion in logic programs.
In Symposium on Principles of Database Systems, pages 92–101. ACM
Press, 1991.
[13] A. Van Gelder, K. A. Ross, and J. S. Schlipf. The well-founded seman-
tics for general logic programs. J. of the ACM, 38(3):620–650, 1991.
14
[14] J. Vennekens and S. Verbaeten. Logic programs with annotated
disjunctions. Technical Report CW386, K. U. Leuven, 2003.
http://www.cs.kuleuven. ac.be/∼joost/techrep.ps.
[15] J. Vennekens, S. Verbaeten, and M. Bruynooghe. Logic programs with
annotated disjunctions. In International Conference on Logic Program-
ming, volume 3131 of LNCS. Springer, 2004.
15