The DLV system for knowledge representation and reasoning
Top Cited Papers
- 1 July 2006
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computational Logic
- Vol. 7 (3), 499-562
- https://doi.org/10.1145/1149114.1149117
Abstract
Disjunctive Logic Programming (DLP) is an advanced formalism for knowledge representation and reasoning, which is very expressive in a precise mathematical sense: it allows one to express every property of finite structures that is decidable in the complexity class Σ P 2 (NP NP ). Thus, under widely believed assumptions, DLP is strictly more expressive than normal ( disjunction-free ) logic programming, whose expressiveness is limited to properties decidable in NP. Importantly, apart from enlarging the class of applications which can be encoded in the language, disjunction often allows for representing problems of lower complexity in a simpler and more natural fashion.This article presents the DLV system, which is widely considered the state-of-the-art implementation of disjunctive logic programming, and addresses several aspects. As for problem solving, we provide a formal definition of its kernel language, function-free disjunctive logic programs (also known as disjunctive datalog ), extended by weak constraints, which are a powerful tool to express optimization problems. We then illustrate the usage of DLV as a tool for knowledge representation and reasoning, describing a new declarative programming methodology which allows one to encode complex problems (up to Δ P 3 -complete problems) in a declarative fashion. On the foundational side, we provide a detailed analysis of the computational complexity of the language of DLV, and by deriving new complexity results we chart a complete picture of the complexity of this language and important fragments thereof.Furthermore, we illustrate the general architecture of the DLV system, which has been influenced by these results. As for applications, we overview application front-ends which have been developed on top of DLV to solve specific knowledge representation tasks, and we briefly describe the main international projects investigating the potential of the system for industrial exploitation. Finally, we report about thorough experimentation and benchmarking, which has been carried out to assess the efficiency of the system. The experimental results confirm the solidity of DLV and highlight its potential for emerging application areas like knowledge management and information integration.Keywords
Other Versions
This publication has 41 references indexed in Scilit:
- Computing preferred answer sets by meta-interpretation in Answer Set ProgrammingTheory and Practice of Logic Programming, 2003
- A logic programming approach to knowledge-state planning, II: TheArtificial Intelligence, 2003
- Answer set programming and plan generationArtificial Intelligence, 2002
- Complexity and expressive power of logic programmingACM Computing Surveys, 2001
- Enhancing Disjunctive Datalog by constraintsIEEE Transactions on Knowledge and Data Engineering, 2000
- Succinctness as a source of complexity in logical formalismsAnnals of Pure and Applied Logic, 1999
- Abduction from logic programs: Semantics and complexityTheoretical Computer Science, 1997
- Logic programming and negation: A surveyThe Journal of Logic Programming, 1994
- Logic programming and knowledge representationThe Journal of Logic Programming, 1994
- On the complexity of unique solutionsJournal of the ACM, 1984