NDLI: Enhancing DLV instantiator by backjumping techniques

Content Provider	Springer Nature Link
Author	Leone, Nicola Catala, Gelsomina Scarcello, Francesco Perri, Simona
Copyright Year	2008
Abstract	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.
Ending Page	228
Page Count	34
Starting Page	195
File Format	PDF
ISSN	10122443
e-ISSN	15737470
Journal	Annals of Mathematics and Artificial Intelligence
Issue Number	2-4
Volume Number	51
Language	English
Publisher	Springer Netherlands
Publisher Date	2008-02-26
Publisher Place	Dordrecht
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Disjunctive logic programming Logic programming Logic in artificial intelligence Nonmonotonic reasoning Answer set programming Computer Science Artificial Intelligence (incl. Robotics) Mathematics Stable model semantics Artificial intelligence Deductive databases Complexity
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Artificial Intelligence

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On look-ahead heuristics in disjunctive logic programming

A generalization of the Lin-Zhao theorem

Dealing with explicit preferences and uncertainty in answer set programming

An introduction to fuzzy answer set programming

Possibilistic uncertainty handling for answer set programming

Answer set based design of knowledge systems

Stable models and difference logic

My work with Victor Marek: a mathematician looks at answer set programming

Using Database Optimization Techniques for Nonmonotonic Reasoning (1999)

Enhancing DLV instantiator by backjumping techniques

Similar Documents

On look-ahead heuristics in disjunctive logic programming

A generalization of the Lin-Zhao theorem

Dealing with explicit preferences and uncertainty in answer set programming

An introduction to fuzzy answer set programming

Possibilistic uncertainty handling for answer set programming

Answer set based design of knowledge systems

Stable models and difference logic

My work with Victor Marek: a mathematician looks at answer set programming

Using Database Optimization Techniques for Nonmonotonic Reasoning (1999)

Enhancing DLV instantiator by backjumping techniques