Logic Programs with Annotated Disjunctions (LPADs) allow to express 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. Inference on LPADs can be performed using either the system Ailog2, that was developed for the Independent Choice Logic, or SLDNFAD, an algorithm based on SLDNF. However, both of these algorithms run the risk of going into infinite loops and of performing redundant computations. In order to avoid these problems, we present SLGAD resolution that computes the (conditional) probability of a ground query from a range-restricted LPAD and is based on SLG resolution for normal logic programs. As SLG, it uses tabling to avoid some infinite loops and to avoid redundant computations. The performances of SLGAD are evaluated on classical benchmarks for normal logic programs under the well-founded semantics, namely a 2-person game and the ancestor relation, and on a game of dice. SLGAD is compared with Ailog2 and SLDNFAD on the problems in which they do not go into infinite loops, namely those that are described by a modularly acyclic program. On the 2-person game and the ancestor relation, SLGAD is more expensive than SLDNFAD on problems where SLDNFAD succeeds but is faster than Ailog2 when the query is true in an exponential number of instances. If the program requires the repeated computation of similar goals, as for the dice game, then SLGAD outperforms both Ailog2 and SLDNFAD.
SLGAD Resolution for Inference on Logic Programs with Annotated Disjunctions
RIGUZZI, Fabrizio
2010
Abstract
Logic Programs with Annotated Disjunctions (LPADs) allow to express 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. Inference on LPADs can be performed using either the system Ailog2, that was developed for the Independent Choice Logic, or SLDNFAD, an algorithm based on SLDNF. However, both of these algorithms run the risk of going into infinite loops and of performing redundant computations. In order to avoid these problems, we present SLGAD resolution that computes the (conditional) probability of a ground query from a range-restricted LPAD and is based on SLG resolution for normal logic programs. As SLG, it uses tabling to avoid some infinite loops and to avoid redundant computations. The performances of SLGAD are evaluated on classical benchmarks for normal logic programs under the well-founded semantics, namely a 2-person game and the ancestor relation, and on a game of dice. SLGAD is compared with Ailog2 and SLDNFAD on the problems in which they do not go into infinite loops, namely those that are described by a modularly acyclic program. On the 2-person game and the ancestor relation, SLGAD is more expensive than SLDNFAD on problems where SLDNFAD succeeds but is faster than Ailog2 when the query is true in an exponential number of instances. If the program requires the repeated computation of similar goals, as for the dice game, then SLGAD outperforms both Ailog2 and SLDNFAD.I documenti in SFERA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
