caa a22 4500 46318694X CHVBK 20180406164856.0 cr unu---uuuuu 170326e20071201xx s 000 0 eng 10.1007/s10472-008-9087-4 doi (NATIONALLICENCE)springer-10.1007/s10472-008-9087-4 On look-ahead heuristics in disjunctive logic programming [Elektronische Daten] [Wolfgang Faber, Nicola Leone, Gerald Pfeifer, Francesco Ricca] Disjunctive logic programming (DLP), also called answer set programming (ASP), is a convenient programming paradigm which allows for solving problems in a simple and highly declarative way. The language of DLP is very expressive and able to represent even problems of high complexity (every problem in the complexity class ${{\Sigma}_{2}^{P}} = {\rm NP}^{{\rm NP}}$ ). During the last decade, efficient systems supporting DLP have become available. Virtually all of these systems internally rely on variants of the Davis-Putnam procedure (for deciding propositional satisfiability [SAT]), combined with a suitable model checker. The heuristic for the selection of the branching literal (i.e., the criterion determining the literal to be assumed true at a given stage of the computation) dramatically affects the performance of a DLP system. While heuristics for SAT have received a fair deal of research, only little work on heuristics for DLP has been done so far. In this paper, we design, implement, optimize, and experiment with a number of heuristics for DLP. We focus on different look-ahead heuristics, also called "dynamic heuristics” (the DLP equivalent of unit propagation [UP] heuristics for SAT). These are branching rules where the heuristic value of a literal Q depends on the result of taking Q true and computing its consequences. We motivate and formally define a number of look-ahead heuristics for DLP programs. Furthermore, since look-ahead heuristics are computationally expensive, we design two techniques for optimizing the burden of their computation. We implement all the proposed heuristics and optimization techniques in DLV—the state-of-the-art implementation of disjunctive logic programming, and we carry out experiments, thoroughly comparing the heuristics and optimization techniques on a large number of instances of well-known benchmark problems. The results of these experiments are very interesting, showing that the proposed techniques significantly improve the performance of the DLV system. Springer Science+Business Media B.V., 2008 Artificial intelligence nationallicence Logic programming nationallicence Nonmonotonic reasoning nationallicence Answer set programming nationallicence Heuristics nationallicence Stable models nationallicence Efficient evaluation nationallicence Faber Wolfgang Department of Mathematics, University of Calabria, 87036, Rende (CS), Italy aut Leone Nicola Department of Mathematics, University of Calabria, 87036, Rende (CS), Italy aut Pfeifer Gerald Department of Mathematics, University of Calabria, 87036, Rende (CS), Italy aut Ricca Francesco Department of Mathematics, University of Calabria, 87036, Rende (CS), Italy aut Annals of Mathematics and Artificial Intelligence Springer Netherlands 51/2-4(2007-12-01), 229-266 1012-2443 51:2-4<229 2007 51 10472 https://doi.org/10.1007/s10472-008-9087-4 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10472-008-9087-4 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Faber Wolfgang Department of Mathematics, University of Calabria, 87036, Rende (CS), Italy aut NATIONALLICENCE 700 1- Leone Nicola Department of Mathematics, University of Calabria, 87036, Rende (CS), Italy aut NATIONALLICENCE 700 1- Pfeifer Gerald Department of Mathematics, University of Calabria, 87036, Rende (CS), Italy aut NATIONALLICENCE 700 1- Ricca Francesco Department of Mathematics, University of Calabria, 87036, Rende (CS), Italy aut NATIONALLICENCE 773 0- Annals of Mathematics and Artificial Intelligence Springer Netherlands 51/2-4(2007-12-01), 229-266 1012-2443 51:2-4<229 2007 51 10472 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer