TY - JOUR
T1 - An extended semantics for logic programs with annotated disjunctions and its efficient implementation
AU - Riguzzi, Fabrizio
AU - Swift, Terrance
PY - 2010/12/1
Y1 - 2010/12/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84883407735&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84883407735&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:84883407735
SN - 1613-0073
VL - 598
JO - CEUR Workshop Proceedings
JF - CEUR Workshop Proceedings
T2 - 25th Italian Conference on Computational Logic, CILC 2010
Y2 - 7 July 2010 through 9 July 2010
ER -