Logic Programming with Annotated Disjunctions (LPADs) is a formalism for modeling probabilistic information that has recently received increased attention. The LPAD semantics, while being simple and clear, suffers from the requirement of having function free-programs, which is a strong limitation. In this paper we present an extension of the semantics that removes this restriction and allows us to write programs modeling infinite domains, such as Hidden Markov Models. We show that the semantics is well-defined for a large class of programs. Moreover, we present the algorithm “Probabilistic Inference with Tabling and Answer subsumption” (PITA) for computing the probability of queries to programs according to the extended semantics. Tabling and answer subsumption not only ensure the correctness of the algorithm with respect to the semantics but also make it very efficient on programs without function symbols. PITA has been implemented in XSB and tested on six domains: two with function symbols and four without. The execution times are compared with those of ProbLog, cplint and CVE. PITA was almost always able to solve larger problems in a shorter time on both type of domains.
Many real world domains only can be represented effectively if we are able to model uncertainty. Recently, there has been an increased interest in logic languages representing probabilistic information due to their succesful use in Machine Learning.
Logic Programs with Annotated Disjunction (LPADs) [
The new semantics is based on a program transformation technique that not only
allows proving the correctness the semantics but also provides an efficient procedure
for computing the probability of queries from LPADs. The algorithm “Probabilistic
Inference with Tabling and Answer subsumption” (PITA) builds explanations for every
subgoal encountered during a derivation of the query. The explanations are compactly
represented using Binary Decision Diagrams (BDDs) that also allow an efficient
computation of the probability. Since all the explanations for a subgoal must be found,
tabling is very useful for storing such information. Tabling has already been shown
useful for probabilistic logic programming in [
PITA draws inspiration from [
PITA was tested on a number of datasets, both with and without function symbols,
in order to evaluate its efficiency. The execution times of PITA were compared with
those of cplint [
The paper is organized as follows. Section 2 illustrates the syntax and semantics of LPADs. Section 3 discusses the semantics of LPADs with function symbols. Section 4 gives an introduction to BDDs. Section 5 defines dynamic stratification for LPADs. Section 6 briefly recalls tabling and answer subsumption. Section 7 presents PITA and shows its correctness. Section 8 describes the experiments and Section 9 concludes the paper and presents directions for future works. 2
A Logic Program with Annotated Disjunctions [
If the LPAD is ground, a clause represents a probabilistic choice between the
nondisjunctive clauses obtained by selecting only one atom in the head. As usual, if the
LPAD T is not ground, T can be assigned a meaning by computing its grounding,
ground(T ). The semantics of LPADs, given in [
By choosing a head atom for each ground clause of an LPAD we get a normal logic
program called a possible world of the LPAD (called an instance of the LPAD in [
More specifically, an atomic choice is a triple (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(C) was chosen. A set of atomic choices κ is consistent if (C, θ, i) ∈ κ, (C, θ, j) ∈ κ ⇒ i = j, i.e., only one head is selected for a ground clause. A composite choice κ is a consistent set of atomic choices. The probability P (κ) of a composite choice κ is the product of the probabilities of the individual atomic choices, i.e. P (κ) = Q(C,θ,i)∈κ αi(C).
A selection σ is a composite choice that, for each clause Cθ in ground(T ), contains an atomic choice (C, θ, i) in σ. We denote the set of all selections σ of a program T by ST . A selection σ identifies a normal logic program wσ defined as follows wσ = {(hi(C)θ ← body(C))θ|(C, θ, i) ∈ σ}. wσ is called a possible world (or simply world) of T . WT denotes the set of all the possible worlds of T . Since selections are composite choices, we can assign a probability to possible worlds: P (wσ) = P (σ) = Q(C,θ,i)∈σ αi(C).
We consider only sound LPADs, in which every possible world has a total model
according to the Well-Founded Semantics (WFS) [
The probability of a ground atom φ according to an LPAD T is given by the sum of the probabilities of the possible worlds where the atom is true under the WFS: P (φ) = Pσ∈ST ,wσ|=φ P (σ). It is easy to see that P satisfies the axioms of probability. Example 1. Consider the dependency of sneezing on having the flu or hay fever: C1 = strong sneezing(X) : 0.3 ∨ moderate sneezing(X) : 0.5 ← f lu(X). C2 = strong sneezing(X) : 0.2 ∨ moderate sneezing(X) : 0.6 ← hay f ever(X). C3 = f lu(david).
C4 = hay f ever(david).
This program models the fact that sneezing can be caused by flu or hay fever. The query strong sneezing(david) is true in 5 of the 9 instances of the program and its probability is PT (strong sneezing(david)) = 0.3·0.2+0.3·0.6+0.3·0.2+0.5·0.2+0.2·0.2 = 0.44 Even if we assumed independence between the choices for individual ground clauses, this does not represents a restriction, in the sense that this still allow to represent all the joint distributions of atoms of the Herbrand base that are representable with a Bayesian network over those variables. Details of the proof are omitted for lack of space.
LPADs can be written by the user or learned from data. When written by the user, the best approach is to write each clause so that it models a causal mechanism of the domain and to choose the parameters on the basis of his knowledge of the mechanism.
If a non-ground LPAD T contains function symbols, then the semantics given in Section 2 is not well-defined. In this case, each possible world wσ is the result of an infinite number of choices and the probability P (wσ) of wσ is 0 since it is given by the product of an infinite number of factors all smaller than 1. Thus, the probability of a formula is 0 as well, since it is a sum of terms all equal to 0.
Therefore a new definition of the LPAD semantics is necessary. We provide such
a definition following the approach in [
A composite choice κ identifies a set of possible worlds ωκ that contains all the worlds relative to a selection that is a superset of κ, i.e., ωκ = {wσ|σ ∈ ST , σ ⊇ κ} We define the set of possible worlds associated to a set of composite choices K: ωK = Sκ∈K ωκ
Given a ground atom φ, we define the notion of explanation, covering set of composite choices and mutually incompatible set of explanations. A finite composite choice κ is an explanation for φ if φ is true in every world of ωκ. In Example 1, the composite choice {(C1, {X/david}, 1)} is an explanation for strong sneezing(david). A set of composite choices K is covering with respect to φ if every world wσ in which φ is true is such that wσ ∈ ωK . In Example 1, the set of composite choices
K1 = {{(C1, {X/david}, 1)}, {(C2, {X/david}, 1)}} (1) is covering for strong sneezing(david). Two composite choices κ1 and κ2 are incompatible if their union is inconsistent, i.e., if there exists a clause C and a substitution θ grounding C such that (C, θ, j) ∈ κ1, (C, θ, k) ∈ κ2 and j 6= k. A set K of composite choices is mutually incompatible if for all κ1 ∈ K, κ2 ∈ K, κ1 6= κ2 ⇒ κ1 and κ2 are incompatible. The set of composite choices
K2 = {{(C1, {X/david}, 1), (C2, {X/david}, 2)},
{(C1, {X/david}, 1), (C2, {X/david}, 3)},
{(C2, {X/david}, 1)}}
(2)
is mutually incompatible for the theory of Example 1. The following results of [
– Given a finite set K of finite composite choices, there exists a finite set K′ of
mutually incompatible finite composite choices such that ωK = ωK′ .
– If K1 and K2 are both mutually incompatible sets of composite choices such that
ωK1 = ωK2 then Pκ∈K1 P (κ) = Pκ∈K2 P (κ)
Thus, we can define a unique probability measure μ : ΩT → [
In the case of Example 1, K2 shown in equation 2 is a covering set of explanations for sneezing(david, strong) that is mutually incompatible, so
P (sneezing(david, strong)) = 0.3 · 0.6 + 0.3 · 0.2 + 0.2 = 0.44 4
Representing Explanations by Means of Decision Diagrams
In order to represent explanations we can use Multivalued Decision Diagrams [
Given a set of explanations K, we obtain a Boolean function fK in the following way. Each ground clause Cθ appearing in K is associated to a multivalued variable XCθ with as many values as atoms in the head of C. Each atomic choice (C, θ, i) is represented by the propositional equation XCθ = i. Equations for a single explanation are conjoined and the conjunctions for the different explanations are disjoined.
The set of explanations in Equation (1) can be represented by the function fK1 (X) = (XC1∅ = 1) ∨ (XC2∅ = 1). An MDD can be obtained from a Boolean function: from fK1 th MDD shown in Figure 1(a) is obtained.
3 3 0 0 2 12 a0a 1 a0a a1a ciao XC1∅1 ciao 1
XC2∅1 (b) BDD.
a1a ciao XC1∅ ciao 1
XC2∅ (a) MDD.
Decision diagrams can be built with various software packages that provide highly
efficient implementation of Boolean operations. However, most packages are restricted
to work on Binary Decision Diagram (BDD), i.e., decision diagrams where all the
variables are Boolean. To work on MDD with a BDD package, we must represent
multivalued variables by means of binary variables. Various options are possible, we found that
the following, proposed in [
One of the most important formulations of stratification is that of dynamic stratification.
[
Definition 2. For a normal program P , sets T and F of ground atoms, and a 3-valued interpretation I we define T rueI (T ) = {A : valI (A) 6= t and there is a clause B ← L1, ..., Ln in P and a ground substitution θ such that A = Bθ and for every 1 ≤ i ≤ n either Liθ is true in I, or Liθ ∈ T }; F alseI (F ) = {A : valI (A) 6= f and for every clause B ← L1, ..., Ln in P and ground substitution θ such that A = Bθ there is some i (1 ≤ i ≤ n), such that Liθ is false in I or Liθ ∈ F }.
The conditions valI (A) 6= t and valI (A) 6= f are inessential, but ensure that only new
facts are included in T rueI (T ) and F alseI (F ), and simplify the definition of dynamic
strata below. [
W F M0 = h∅; ∅i; W F Mα+1 = W F Mα ∪ hTW F Mα ; FW F Mα i;
W F Mα = Sβ<α W F Mβ , for limit ordinal α.
Let W F M (P ) denote the fixed point interpretation W F Mδ, where δ is the smallest
countable ordinal such that both sets TW F Mδ and FW F Mδ are empty. We refer to δ
as the depth of program P . The stratum of atom A, is the least ordinal β such that
A ∈ W F Mβ (where A may be either in the true or false component of W F Mβ ).
[
Dynamic stratification captures the order in which recursive components of a
program must be evaluated. Because of this, dynamic stratification is useful for modeling
operational aspects of program evaluation. Fixed-order dynamic stratification [
Example 2. The following program has a 2-valued well-founded model and so is dynamically stratified, but does not belong to other stratification classes, such as local, modular, or weak stratification.
s ← ¬s, p. p ← q, ¬r, ¬s. r ← p, ¬q. p ← ¬ p.
s ← ¬p, ¬q, ¬r. q ← r, ¬p. p, q, and r all belong to stratum 0, while s belongs to stratum 1. The simple program is fixed-order stratified, but not locally, modularly, or weakly stratified. Fixed-order stratification is more general than local stratification, and than modular stratification (since modular stratified programs can be decidably rearranged so that they have failing prefixes). It is neither more nor less general than weak stratification.
The above definitions of (fixed-order) dynamic stratification for normal programs can be straightforwardly adapted to LPADs – an LPAD is (fixed-order) dynamically stratified if each w ∈ WT is (fixed-order) dynamically stratified. 6
The idea behind tabling is to maintain in a table both subgoals encountered in a query evaluation and answers to these subgoals. If a subgoal is encountered more than once, the evaluation reuses information from the table rather than re-performing resolution against program clauses. Although the idea is simple, it has important consequences. First, tabling ensures termination of programs with the bounded term-size property. A program P has the bounded term-size property if there is a finite function f : N → N such that if a query term Q to P has size size(Q), then no term used in the derivation of Q has size greater than f (size(Q)). This makes it easier to reason about termination than in basic Prolog. Second, tabling can be used to evaluate programs with negation according to the WFS. Third, for queries to wide classes of programs, such as datalog programs with negation, tabling can achieve the optimal complexity for query evaluation. And finally, tabling integrates closely with Prolog, so that Prolog’s familiar programming environment can be used, and no other language is required to build complete systems. As a result, a number of Prologs now support tabling including XSB, YAP, B-Prolog, ALS, and Ciao. In these systems, a predicate p/n is evaluated using SLDNF by default: the predicate is made to use tabling by a declaration such as table p/n that is added by the user or compiler.
This paper makes use of a tabling feature called answer subsumption. Most
formulations of tabling add an answer A to a table for a subgoal S only if A is a not a variant
(as a term) of any other answer for S. However, in many applications it may be useful to
order answers according to a partial order or (upper semi-)lattice. In the case of a lattice,
answer subsumption may be specified by means of a declaration such as table p( ,or/3
zero/1). for an unary predicate p. where zero/1 is the bottom element of the lattice and
or/3 is the join operation of the lattice. For example, in the PITA algorithm for LPADs
presented in Section 7, if a table had an answer p(a, E1) and a new answer p(a, E2)
were derived, where E1 and E2 are probabilistic explanations, the answer p(a, E1) is
replaced by p(a, E3), where E3 is obtained by calling or(E1, E2, E3) and is the
logical disjunction of the first two explanations, as stored in a BDD3. Answer subsumption
over arbitrary upper semi-lattices is implemented in XSB for stratified programs [
Section 7 uses SLG resolution [
The first step of the PITA algorithm is to apply a program transformation to an LPAD to create a normal normal program that contains calls for manipulating BDDs. In our implementation, these calls provide a Prolog interface to the CUDD4 C library and use the following predicates5 – init, end: for allocation and deallocation of a BDD manager, a data structure used to keep track of the memory for storing BDD nodes; 3 The logical disjunction E3 can be seen as subsuming E1 and E2 over the partial order af implication defined on logical formulas. 4 http://vlsi.colorado.edu/˜fabio/ 5 BDDs are represented in CUDD as pointers to their root node. – zero(-BDD), one(-BDD), and(+BDD1,+BDD2,-BDDO), or(+BDD1,+BDD2, -BDDO), not(+BDDI,-BDDO): Boolean operations between BDDs; – add var(+N Val,+Probs,-Var): addition of a new multi-valued variable with N Val values and parameters Probs; – equality(+Var,+Value,-BDD): BDD represents Var=Value, i.e. that the random variable Var is assigned Value in the BDD; – ret prob(+BDD,-P): returns the probability of the formula encoded by BDD. add var(+N Val,+Probs,-Var) adds a new random variable associated to a new instantiation of a rule with N Val head atoms and parameters list Probs. The auxiliary predicate get var n(+R,+S,+Probs,-Var) is used to wrap add var/3 and avoid adding a new variable when one already exists for an instantiation. As shown below, a new fact var(R,S,Var) is asserted each time a new random variable is created, where R is an identifier for the LPAD clause, S is a list of constants, one for each variables of the clause, and Var is an integer that identifies the random variable associated with clause R under a particular grounding. The auxiliary predicates has the following definition get var n(R, S, P robs, V ar) ← (var(R, S, V ar) → true; length(P robs, L), add var(L, P robs, V ar), assert(var(R, S, V ar))). where Probs is a list of floats that stores the parameters in the head of rule R.
The PITA transformation applies to clauses, literals and atoms. If h is an atom, P IT Ah(h) is h with the variable BDD added as the last argument. If bj is an atom, P IT Ab(bj ) is bj with the variable Bj added as the last argument. In either case for an atom a, BDD(P IT A(a)) is the value of the last argument of P IT A(a),
If bj is negative literal ¬aj , P IT Ab(bj ) is the conditional (P IT A′b(aj ) → not(BNj , Bj ); one(Bj )), where P IT A′b(aj ) is aj with the variable BNj added as the last argument. In other words the input BDD, BNk, is negated if it exists; otherwise the BDD for the constant function 1 is returned.
A non-disjunctive fact Cr = h is transformed into the clause P IT A(Cr) = P IT Ah(h) ← one(BDD).
A disjunctive fact Cr = h1 : α1 ∨ . . . ∨ hn : αn. where the parameters sum to 1, is transformed into the set of clauses P IT A(Cr)6
P IT A(Cr, 1) = P IT Ah(h1) ← get var n(i, [], [α1, . . . , αn], V ar), equality(V ar, 1, BDD). . . .
P IT A(Cr, n) = P IT Ah(hn) ← get var n(r, [], [α1, . . . , αn], V ar), equality(V ar, n, BDD).
In the case where the parameters do not sum to one, the clause is first transformed into thh1e :liαst1o∨fp.a.r.a∨mehtners: iαsn[α∨1,n. u..ll, α:n1, −1−PP1nα1niα.ia]nbdutthtehne i(nnto+th1e)-cthlaculsaeusseab(othvee,owneheforer null) is not generated.
The definite clause Cr = h ← b1, b2, . . . , bm. is transformed into the clause P IT A(Cr) = P IT Ah(h) ← P IT Ab(b1), P IT Ab(b2), and(B1, B2, BB2), . . . , P IT Ab(bm), and(BBm−1, Bm, BDD). 6 The second argument of get var n is the empty list because, since we are considering only range restricted programs (cfr. below), a fact does not contain variables. The disjunctive clause
Cr = h1 : α1 ∨ . . . ∨ hn : αn ← b1, b2, . . . , bm. where the parameters sum to 1, is transformed into the set of clauses P IT A(Cr) P IT A(Cr, 1) = P IT Ah(h1) ← P IT Ab(b1), P IT Ab(b2), and(B1, B2, BB2), . . . , P IT Ab(bm), and(BBm−1, Bm, BBm), get var n(r, V C, [α1, . . . , αn], V ar), equality(V ar, 1, B), and(BBm, B, BDD). . . .
P IT A(Cr, n) = P IT Ah(hn) ← P IT Ab(b1), P IT Ab(b2), and(B1, B2, BB2), . . . , P IT Ab(bm), and(BBm−1, Bm, BBm), get var n(r, V C, [α1, . . . , αn], V ar), equality(V ar, n, B), and(BBm, B, BDD). where V C is a list containing each variable appearing in Cr. If the parameters do not sum to 1, the same technique used for disjunctive facts is used.
Example 3. Clause C1 from the LPAD of Example 1 is translated into strong sneezing(X, BDD) ← flu(X, B1), get var n(1, [X], [0.3, 0.5, 0.2], V ar), equality(V ar, 1, B), and(B1, B, BDD). moderate sneezing(X, BDD) ← flu(X, B1), get var n(1, [X], [0.3, 0.5, 0.2], V ar), equality(V ar, 2, B), and(B1, B, BDD). while clause C3 is translated into
f lu(david, BDD) ← one(BDD).
In order to answer queries, the goal solve(Goal,P) is used, which is defined by solve(Goal, P ) ← init, retractall(var( , , )), add bdd arg(Goal, BDD, GoalBDD), (call(GoalBDD) → ret prob(BDD, P ); P = 0.0), end. where add bdd arg(Goal, BDD, GoalBDD) implements P IT Ah(Goal). Moreover, various predicates of the LPAD should be declared as tabled. For a predicate p/n, the declaration is table p( 1,..., n,or/3-zero/1), that indicates that answer subsumption is used to form the disjunct of multiple explanations: At a minimum, the predicate of the goal should be tabled; as shown in Section 8 it is usually better to table every predicate whose answers have multiple explanations and are going to be reued often. Correctness of PITA In this section we show two results regarding the PITA transformation and its tabled evaluation7. These results ensure on one hand that the semantics is well-defined and on the other hand that the evaluation algorithm is correct. For the purposes of our semantics, we consider the BDDs produced as ground terms, and do not specify them further. We first state the correctness of the PITA transformation with respect to the well-founded semantics of LPADs. Because we allow LPADs to have 7 Due to space limitations, our presentation is somewhat informal: a formal presentation with all proofs and supporting definitions can be found at http://www.ing.unife.it/docenti/FabrizioRiguzzi/Papers/RigSwi10-TR.pdf. function symbols, care must be taken to ensure that explanations are finite. To accomplish this, we prove correctness for what we term dynamically-finitary programs, essentially those for which a derivation in the well-founded semantics does not depend on an infinite unfounded set 8.
Theorem 1 (Correctness of PITA Transformation). Let T be a sound dynamicallyfinitary LPAD. Then κ is an explanation for a ground atom a iff there is a P IT Ah(a)θ in W F M (P IT A(ground(T ))), such that κ is a path in BDD(P IT Ah(a)θ) to a 1 leaf.
Theorem 2 below states the correctness of the tabling implementation of PITA, since
the BDD returned for a tabled query is the disjunction of a set of covering explanations
for that query. The proof uses an extension of SLG evaluation that includes answer
subsumption but that is restricted to fixed-order dynamically stratified programs [
Theorem 2 (Correctness of PITA Evaluation). Let T be a range restricted, bounded term-size, fixed-order dynamically stratified LPAD and a a ground atom. Let E be an SLG evaluation of P IT Ah(a) against P IT A(T ), such that answer subsumption is declared on P IT Ah(a) using BDD-disjunction. Then E terminates with an answer ans for P IT Ah(a) and BDD(ans) represents a covering set of explanations for a. Thus range restricted, bounded term-size and fixed-order dynamically stratified LPADs have a finite set of explanations that are covering for a ground atom, so the semantics with function symbols is well-defined. 8
PITA was tested on two datasets that contain function symbols: the first is taken from
[
The first problem models a HMM with three states 1, 2 and 3 of which 3 is an end state. This problem is encoded by the program s(0,1):1/3 ∨ s(0,2):1/3 ∨ s(0,3):1/3.
s(T,1):1/3 ∨ s(T,2):1/3 ∨ s(T,3):1/3 ← T1 is T-1, T1>=0, s(T1,F), \+ s(T1,3) For this experiment, we query the probability of the HMM being in state 1 at time N for increasing values of N, i.e., we query the probability of s(N,1). In PITA, we did not use reordering of BDDs variables11. The execution times of PITA, CVE and cplint are shown in Figure 2. In this problem tabling provides an impressive speedup, since computations can be reused often.
0.8 0.7 0.6
N
Fig. 2. Three sided die.
The biological network problems compute the probability of a path in a large graph
in which the nodes encode biological entities and the links represents conceptual
relations among them. Each programs in this dataset contains a definition of path plus a
number of links represented by probabilistic facts. The programs have been sampled
from a very large graph and contain 200, 400, . . ., 5000 edges. Sampling was repeated
ten times, to obtain a series of 10 programs of increasing size. In each test we queried
the probability that the two genes HGNC 620 and HGNC 983 are related. We used the
definition of path of [
\ + member(Z, V 0), path(Z, Y, [Z|V 0], V 1).
We used this definition because it gave better results than the one without explicit loop checking. The possibility of using lists (that require function symbols) allowed in this case more modeling freedom. The predicates path/2 and edge/2 are tabled.
We ran PITA, ProbLog and cplint on the graphs in sequence starting from the smallest program and in each case we stopped after one day or at the first graph for 10 All experiments were performed on Linux machines with an Intel Core 2 Duo E6550 (2333
MHz) processor and 4 GB of RAM. 11 For each experiment, we used either group sift automatic reordering or no reordering of BDDs variables depending on which gave the best results. 10−4
ProbLog cplint PITA ProbLog cplint
PITA (b) Execution times. 500 1000 2000 2500 3000 500 1000 2000 2500 3000 104 103 10−1 15 20
5 10 Number of PhD students (b) uwcse. which the program ended for lack of memory12. In PITA, we used group sift reordering of BDDs variables. Figure 3(a) shows the number of subgraphs for which each algorithm was able to answer the query as a function of the size of the subgraphs, while Figure 3(b) shows the execution time averaged over all and only the subgraphs for which all the algorithms succeeded. PITA was able to solve more subgraphs and in a shorter time than cplint and ProbLog. For PITA the vast majority of time for larger graphs was spent on BDD maintenance. ProbLog ended for lack of memory in three cases out of ten, PITA in two and cplint in four. This shows that, even if tabling consumes more memory when finding the explanations, BDDs are built faster and using less memory, probably due to the fact that tabling allows less redundancy (only one BDD is stored for an answer) and a bottom-up construction of the BDDs, which is usually better. This shows that one should table every predicate whose answer have multiple explanations, as path/2 and edge/2 above.
The four datasets of [
This paper has made two contributions. The first, semantic, contribution extends LPADs to include functions. By way of proving correctness of the PITA transformation we also characterize those extended LPAD programs whose derived atoms have only finite explanations (dynamically-finitary LPADs); by way of proving correctness of PITA evaluation we characterize those that have only finite sets of explanations (LPADs with the bounded term-size property). Such results ensure that the semantics with function symbols is well-defined.
The PITA transformation also provides a practical reasoning algorithm that was directly used in the experiments of Section 8. The experiments substantiate the PITA approach. Accordingly PITA programs should be easily portable to other tabling engines such as that of YAP, Ciao and B Prolog if they support answer subsumption over general semi-lattices.
In the future, we plan to extend PITA to the whole class of sound LPADs by
implementing the SLG DELAYING and SIMPLIFICATION operations for answer subsumption.
In addition, we are developing a version of PITA that is able to answer queries in an
approximate way, similarly to [
For the missing points at the end of the lines the algorithm exhausted the available memory.