Answer Set Programming (ASP) is a logic programming language for nonmonotonic reasoning. Propositional ASP programs are usually evaluated by DPLL algorithms combining unit propagation with operators that are specific of ASP. Among them, unfounded set propagation is used for handling recursive programs by many ASP solvers. This paper reports a comparison of two available solutions for unfounded set propagation, the one adopted in DLV and that based on source pointers. The paper also discusses the impact of splitting the input program in components according to head-to-body dependencies. Both solutions and variants have been implemented in the same solver, namely WASP. An advantage in properly splitting the program in components is highlighted by an experiment on a selection of problems taken from the 3rd ASP Competition. In this experiment the algorithm based on source pointers performs better. © Springer International Publishing Switzerland 2013.
Comparing alternative solutions for unfounded set propagation in ASP
DODARO, CARMINE;
2013-01-01
Abstract
Answer Set Programming (ASP) is a logic programming language for nonmonotonic reasoning. Propositional ASP programs are usually evaluated by DPLL algorithms combining unit propagation with operators that are specific of ASP. Among them, unfounded set propagation is used for handling recursive programs by many ASP solvers. This paper reports a comparison of two available solutions for unfounded set propagation, the one adopted in DLV and that based on source pointers. The paper also discusses the impact of splitting the input program in components according to head-to-body dependencies. Both solutions and variants have been implemented in the same solver, namely WASP. An advantage in properly splitting the program in components is highlighted by an experiment on a selection of problems taken from the 3rd ASP Competition. In this experiment the algorithm based on source pointers performs better. © Springer International Publishing Switzerland 2013.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.