caa a22 4500 463187008 CHVBK 20180406164856.0 cr unu---uuuuu 170326e20071201xx s 000 0 eng 10.1007/s10472-008-9090-9 doi (NATIONALLICENCE)springer-10.1007/s10472-008-9090-9 Enhancing DLV instantiator by backjumping techniques [Elektronische Daten] [Simona Perri, Francesco Scarcello, Gelsomina Catalano, Nicola Leone] Disjunctive logic programming (DLP) is a powerful formalism for knowledge representation and reasoning. The high expressiveness of DLP language, together with the recent availability of some efficient DLP system, has favoured the application of DLP in emerging areas like Knowledge Management and Information Integration. These applications have often to deal with huge input data, and have evidenced the need to improve the efficiency of DLP instantiators. Program instantiation is the first phase of a DLP computation; in this phase, variables are replaced by constants to generate a ground program which is then evaluated by propositional algorithms in the second phase of the computation. The instantiation process may be computationally expensive, and in fact its efficiency has been recognized to be a key issue for solving real-world problems by using disjunctive logic programming. Given a program P, a good instantiation for P is a ground program P′ having precisely the same answer sets as P and such that: (1) P′ can be computed efficiently from P, and (2) P′ does not contain "useless” rules, (P′ is as small as possible) and can thus be evaluated efficiently. In this paper, we present a structure-based backjumping algorithm for the instantiation of disjunctive logic programs, that meets the above requirements. In particular, given a rule r to be grounded, our algorithm exploits both the semantical and the structural information about r for computing efficiently the ground instances of r, avoiding the generation of "useless” rules. That is, from each general rule r, we compute only a relevant subset of its ground instances, avoiding the generation of "useless” instances, while fully preserving the semantic of the program. We have implemented this algorithm in DLV—the state-of-the-art implementation of DLP—and we have carried out an experimentation activity on an ample collection of benchmark problems. The experimental results are very positive: the new technique improves sensibly the efficiency of the DLV system on many program classes. Springer Science+Business Media B.V., 2008 Artificial intelligence nationallicence Logic programming nationallicence Nonmonotonic reasoning nationallicence Disjunctive logic programming nationallicence Answer set programming nationallicence Deductive databases nationallicence Stable model semantics nationallicence Perri Simona Department of Mathematics, University of Calabria, 87036, Rende (CS), Italy aut Scarcello Francesco DEIS, University of Calabria, 87036, Rende (CS), Italy aut Catalano Gelsomina Department of Mathematics, University of Calabria, 87036, Rende (CS), Italy aut Leone Nicola 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), 195-228 1012-2443 51:2-4<195 2007 51 10472 https://doi.org/10.1007/s10472-008-9090-9 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10472-008-9090-9 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Perri Simona Department of Mathematics, University of Calabria, 87036, Rende (CS), Italy aut NATIONALLICENCE 700 1- Scarcello Francesco DEIS, University of Calabria, 87036, Rende (CS), Italy aut NATIONALLICENCE 700 1- Catalano Gelsomina 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 773 0- Annals of Mathematics and Artificial Intelligence Springer Netherlands 51/2-4(2007-12-01), 195-228 1012-2443 51:2-4<195 2007 51 10472 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer