The DLV system for knowledge representation and reasoning

Nicola LeoneGerald PfeiferWolfgang FaberThomas EiterGeorg GottlobSimona PerriFrancesco Scarcello

article2002TOCL1,337 citations

Presents the DLV system, detailing the formal foundations, computational complexity, and architectural design of a leading disjunctive logic programming engine capable of solving complex declarative knowledge representation and optimization problems up to $\Delta^P_3$ -completeness.

Listen

Modern artificial intelligence, data integration, and knowledge management systems frequently need to represent and process complex, incomplete, and highly combinatorial knowledge. While declarative logic formalisms excel at expressing domain rules and constraints without requiring procedural code, evaluating expressive programs has traditionally suffered from prohibitive computational costs and a lack of robust, production-grade reasoning engines.

The article provides a comprehensive evaluation of the DLV system, an industrial-strength implementation of Disjunctive Logic Programming (DLP), demonstrating its formal semantics, theoretical computational foundations, system architecture, and real-world performance against alternative Answer Set Programming solvers.

The authors analyze the formal complexity of the full DLV language and its syntactic fragments across different reasoning tasks, establishing a complete theoretical taxonomy. To evaluate system performance, the authors conducted empirical benchmarks comparing DLV against state-of-the-art Answer Set Programming solvers (GnT, Smodels, and ASSAT) across problem domains ranging from polynomial-time database tasks to highly intractable benchmark problems up to the second layer of the Polynomial Hierarchy.

The evaluation revealed four key findings. First, DLV achieves superior scalability on data-intensive deductive database tasks, handling instances up to 10,000 nodes where competing systems exhausted memory at roughly 700 nodes due to inefficient program instantiation. Second, on hard problems at the second level of the Polynomial Hierarchy, DLV’s native handling of disjunction significantly outperformed GnT, solving problem instances up to thirty times larger. Third, on NP-complete search problems such as Hamiltonian Path, DLV solved instances up to size 105, whereas alternative solvers reached memory or time limits at sizes 45 to 50. Fourth, the complexity analysis demonstrated that DLV with weak constraints captures decision problems up to the third level of the Polynomial Hierarchy, enabling declarative optimization encodings that cannot be expressed in standard disjunctive datalog.

These findings indicate that expressive logic programming is practically viable for large-scale enterprise data integration, scheduling, and diagnosis. By dynamically tailoring evaluation algorithms to the exact syntactic complexity of a given input, DLV avoids the computational overhead typical of general-purpose reasoning engines, thereby reducing runtime and hardware costs for complex domain-specific modeling.

Organizations evaluating declarative knowledge systems should consider DLV, particularly for applications requiring complex optimization, reasoning with incomplete information, or large input data sets. System implementers should also leverage the Guess/Check/Optimize methodology to develop and debug logic-based business rules modularly.

The findings are bounded by the specific benchmark sets, resource limits of 256MB per component, and variations caused by rule encodings and domain predicate choices across different instantiators. Nevertheless, the theoretical proofs and empirical results provide high confidence that DLV is an efficient, robust platform for declarative problem solving across diverse complexity classes.

TU Wien University of Calabria complexity results datalog disjunctive logic programs DLV system answer-set programming disjunctive datalog

arXiv: cs/0211004

Paper: Nonmonotonic Reasoning, Preferential Models and Cumulative Logics, Sarit Kraus et al. (1990). Provides foundational mathematical and model-theoretic principles for non-monotonic consequence relations that underpin declarative non-monotonic logic programming formalisms like DLV.

Paper: Domain-Specific Heuristics in Answer Set Programming: A Declarative Non-Monotonic Approach, Richard Comploi-Taupe et al. (2023). Extends answer set programming solving methodologies beyond standard ground-and-solve architectures like DLV by introducing declarative, domain-specific heuristics evaluated over partial assignments.

Cover for The DLV system for knowledge representation and reasoning

Abstract

This paper 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 $\Delta^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.

Topics

complexity results datalog disjunctive logic programs information integration knowledge management optimization optimization problems reasoning stable model answer set semantics

Keywords

DLV system answer-set programming disjunctive datalog knowledge representation and reasoning nonmonotonic reasoning disjunctive deductive databases knowledge-state planning

1. INTRODUCTION
2. CORE LANGUAGE
2.2 Semantics
3. KNOWLEDGE REPRESENTATION IN DLV
3.1 Deductive Database Applications
3.2 The GCO Declarative Programming Methodology
4. THE COMPLEXITY OF THE DLV LANGUAGE
4.1 A Reminder of the Polynomial Hierarchy
4.2 Relevant Fragments of the DLV Language
4.3 Main Problems Considered
4.4 Derivation of Complexity Results
4.5 Summary of Results and Discussion
5. DLV FRONT-ENDS
5.1 Internal Front-Ends
5.2 External Front-Ends
6. THE IMPLEMENTATION OF THE DLV SYSTEM: AN OVERVIEW
7. EXPERIMENTS AND BENCHMARKS
7.1 Overview of Compared Systems
7.2 Benchmark Problems and Data
7.3 Results and Discussion
8. CONCLUSION
ACKNOWLEDGMENTS
REFERENCES
A. APPENDIX: SOKOBAN ENCODINGS

Knowls

Knowl 1 — Syntax and Ground Semantics of Disjunctive Datalog with Leveled and Weighted Weak Constraints
definition
A disjunctive datalog program with weak constraints consists of a finite set of disjunctive rules and weak constraints over a first-order vocabulary without non-nullary function symbols.

A classical literal $l$ is either an atom $p(t_1, \dots, t_n)$ or a strongly negated atom $\neg p(t_1, \dots, t_n)$ . A negation-as-failure (NAF) literal is of the form $l$ or $\text{not } l$ .

A disjunctive rule $r$ is an expression of the form: $a_1 \lor \dots \lor a_n \text{ :- } b_1, \dots, b_k, \text{not } b_{k+1}, \dots, \text{not } b_m.$ where $a_1, \dots, a_n, b_1, \dots, b_m$ are classical literals, $n \ge 0$ , and $m \ge k \ge 0$ . The set $H(r) = \{a_1, \dots, a_n\}$ is the head, $B^+(r) = \{b_1, \dots, b_k\}$ is the positive body, and $B^-(r) = \{b_{k+1}, \dots, b_m\}$ is the negative body. A rule with $n=0$ is an integrity constraint; a rule with $n=1$ is a normal rule; a rule with empty body ( $k=m=0$ ) is a fact.

A weak constraint $wc$ is an expression of the form: $\text{:$\sim$ } b_1, \dots, b_k, \text{not } b_{k+1}, \dots, \text{not } b_m. [w : l]$ where $w$ (the weight) and $l$ (the priority level or layer) are positive integer constants or variables (defaulting to 1 if omitted).

A rule or weak constraint is safe if each variable appears in at least one positive, non-comparative literal in its body. The Herbrand base $B_{\mathcal{P}}$ consists of all ground classical literals formable from predicates and constants in $\mathcal{P}$ . The ground instantiation $\text{Ground}(\mathcal{P})$ applies all substitutions from variables to Herbrand universe elements.

For a positive disjunctive program $\mathcal{P}$ (where $B^-(r) = \emptyset$ for all rules), a consistent interpretation $X \subseteq B_{\mathcal{P}}$ is closed under $\mathcal{P}$ if for every $r \in \text{Ground}(\mathcal{P})$ , $B^+(r) \subseteq X$ implies $H(r) \cap X \neq \emptyset$ . An interpretation $X$ is an answer set of a positive program $\mathcal{P}$ if it is subset-minimal among all consistent interpretations closed under $\mathcal{P}$ . For a general program $\mathcal{P}$ without weak constraints, the Gelfond-Lifschitz reduct $\text{Ground}(\mathcal{P})^X$ is formed by deleting each rule $r$ for which $B^-(r) \cap X \neq \emptyset$ and removing negative body literals from remaining rules. $X$ is an answer set of $\mathcal{P}$ if $X$ is an answer set of $\text{Ground}(\mathcal{P})^X$ .
Knowl 2 — Objective Function and Optimal Answer Sets for Leveled Weak Constraints
definition
For a ground disjunctive logic program $\mathcal{P}$ containing a set of rules $\text{Rules}(\mathcal{P})$ and a set of weak constraints $WC(\mathcal{P})$ , the semantics selects those answer sets of $\text{Rules}(\mathcal{P})$ that minimize the weighted sum of violated weak constraints according to their priority levels.

Let $w_{max}^{\mathcal{P}}$ and $l_{max}^{\mathcal{P}}$ denote the maximum weight and maximum priority level occurring in $WC(\mathcal{P})$ , respectively. For an answer set $A$ of $\text{Rules}(\mathcal{P})$ , let $N_i^{\mathcal{P}}(A)$ be the set of weak constraints in priority level $i$ whose bodies are satisfied by $A$ (i.e., violated constraints at level $i$ ).

The leveled weights are mapped to single scalar values by the auxiliary multiplier function $f_{\mathcal{P}}$ : $f_{\mathcal{P}}(1) = 1$ $f_{\mathcal{P}}(n) = f_{\mathcal{P}}(n - 1) \cdot |WC(\mathcal{P})| \cdot w_{max}^{\mathcal{P}} + 1 \quad \text{for } n > 1$

The objective function $H^{\mathcal{P}}(A)$ is defined as: $H^{\mathcal{P}}(A) = \sum_{i=1}^{l_{max}^{\mathcal{P}}} \left( f_{\mathcal{P}}(i) \cdot \sum_{w \in N_i^{\mathcal{P}}(A)} \text{weight}(w) \right)$

A consistent interpretation $A \subseteq B_{\mathcal{P}}$ is an optimal answer set of $\mathcal{P}$ if and only if:
1. $A$ is an answer set of $\text{Rules}(\mathcal{P})$ , and
2. $H^{\mathcal{P}}(A)$ is minimal over all answer sets of $\text{Rules}(\mathcal{P})$ .
This objective function enforces a strict lexicographic priority ordering: the penalty for violating a single weak constraint at priority level $i$ strictly exceeds the penalty for violating all weak constraints at all lower priority levels $j < i$ combined.
Knowl 3 — The Guess/Check/Optimize (GCO) Declarative Programming Methodology
model/method
The Guess/Check/Optimize (GCO) methodology is a declarative programming design pattern for encoding combinatorial search, decision, and optimization problems into disjunctive logic programs with weak constraints. Given instance facts $\mathcal{F}_I$ , a program $\mathcal{P}$ is structured into three functional components:
1. Guessing Part ( $\mathcal{G} \subseteq \mathcal{P}$ ): A set of disjunctive rules (or unstratified choice rules) that defines the solution candidate space, such that the answer sets of $\mathcal{G} \cup \mathcal{F}_I$ represent candidate solutions.
2. Checking Part ( $\mathcal{C} \subseteq \mathcal{P}$ ): A set of integrity constraints (and optionally auxiliary stratified definitions) that eliminates candidate solutions failing problem-specific admissibility criteria, ensuring the answer sets of $\mathcal{G} \cup \mathcal{C} \cup \mathcal{F}_I$ are precisely the valid solutions.
3. Optimization Part ( $\mathcal{O} \subseteq \mathcal{P}$ ): A set of weighted weak constraints partitioned across priority levels, implicitly defining an objective function $f: \text{AS}(\mathcal{G} \cup \mathcal{C} \cup \mathcal{F}_I) \to \mathbb{N}$ whose global minima are computed by filtering optimal answer sets.
For problems in $\text{NP}$ and $\Delta_2^P$ , the program admits a modular, strictly stratified architecture where $\mathcal{G}$ is head-cycle free, $\mathcal{C}$ contains only integrity constraints with no feedback on $\mathcal{G}$ , and $\mathcal{O}$ contains weak constraints. For problems at the second level of the Polynomial Hierarchy (such as $\Sigma_2^P$ -complete problems like 2QBF and Strategic Companies, and $\Delta_3^P$ -complete problems), the checking part $\mathcal{C}$ must either contain disjunctive rules, create head cycles that interfere with $\mathcal{G}$ , or employ saturation techniques, reflecting the complexity barrier $\Sigma_2^P \not\subseteq \Delta_2^P$ .

Knowl 4 — Computational Complexity Classification of Brave and Cautious Reasoning across DLV Language Fragments

theoretical result

The computational complexity of brave reasoning (deciding whether a ground atom is true in at least one answer set) and cautious reasoning (deciding whether a ground atom is true in all answer sets) for propositional DLV program fragments is fully determined by the combinations of disjunction allowed ( $\emptyset$ for normal programs, $\{\lor_h\}$ for head-cycle free programs, and $\{\lor\}$ for unrestricted disjunction), negation allowed ( $\emptyset$ , $\{\text{not}_s\}$ for stratified negation, and $\{\text{not}\}$ for unrestricted negation), and weak constraints ( $\{w\}$ ).

Brave	$\emptyset$	$\{w\}$	$\{\text{not}_s\}$	$\{\text{not}_s, w\}$	$\{\text{not}\}$	$\{\text{not}, w\}$
$\emptyset$	P	P	P	P	NP	$\Delta_2^P$
$\{\lor_h\}$	NP	$\Delta_2^P$	NP	$\Delta_2^P$	NP	$\Delta_2^P$
$\{\lor\}$	$\Sigma_2^P$	$\Delta_3^P$	$\Sigma_2^P$	$\Delta_3^P$	$\Sigma_2^P$	$\Delta_3^P$

Cautious	$\emptyset$	$\{w\}$	$\{\text{not}_s\}$	$\{\text{not}_s, w\}$	$\{\text{not}\}$	$\{\text{not}, w\}$
$\emptyset$	P	P	P	P	co-NP	$\Delta_2^P$
$\{\lor_h\}$	co-NP	$\Delta_2^P$	co-NP	$\Delta_2^P$	co-NP	$\Delta_2^P$
$\{\lor\}$	co-NP	$\Delta_3^P$	$\Pi_2^P$	$\Delta_3^P$	$\Pi_2^P$	$\Delta_3^P$

All entries represent completeness under polynomial-time (and LOGSPACE) reductions. A notable asymmetry occurs in cautious reasoning for $\text{DLV}[\lor]$ without default negation: while brave reasoning jumps to $\Sigma_2^P$ -completeness, cautious reasoning remains in $\text{co-NP}$ . Disproving that an atom $A$ is a cautious consequence requires finding any classical model $M$ not containing $A$ ; for positive programs, the existence of such a model guarantees the existence of an answer set $M' \subseteq M$ where $A \notin M'$ .

Knowl 5 — Computational Complexity of Answer Set Checking across DLV Language Fragments

theoretical result

The computational complexity of Answer Set Checking (given a ground DLV program $\mathcal{P}$ and an interpretation $M$ , deciding whether $M$ is an optimal answer set of $\mathcal{P}$ ) is characterized across syntactic fragments based on disjunction types (none $\emptyset$ , head-cycle free $\{\lor_h\}$ , unrestricted $\{\lor\}$ ), negation, and weak constraints ( $\{w\}$ ).

Checking	$\emptyset$	$\{w\}$	$\{\text{not}_s\}$	$\{\text{not}_s, w\}$	$\{\text{not}\}$	$\{\text{not}, w\}$
$\emptyset$	P	P	P	P	P	co-NP
$\{\lor_h\}$	P	co-NP	P	co-NP	P	co-NP
$\{\lor\}$	co-NP	$\Pi_2^P$	co-NP	$\Pi_2^P$	co-NP	$\Pi_2^P$

All results denote completeness under polynomial-time reductions. The complexity of reasoning in DLV is driven by three distinct sources of hardness:

Generating exponentially many candidate answer sets ( $s_1$ ), present whenever unrestricted negation or disjunction is allowed;
Verifying subset-minimality ( $s_2$ ), which is $\text{co-NP}$ -complete and occurs only when unrestricted disjunction is present;
Verifying optimality with respect to weak constraints ( $s_3$ ), which requires testing that no other answer set has strictly lower violation cost.

When all three sources ( $s_1, s_2, s_3$ ) are present, reasoning complexity reaches $\Delta_3^P$ and checking complexity reaches $\Pi_2^P$ .

Knowl 6 — Completeness Results for Cautious Reasoning and Model Checking with Weak Constraints
theoretical result
Let $\mathcal{P}$ be a ground DLV program, $A$ a ground atom, and $M \subseteq B_{\mathcal{P}}$ a candidate interpretation.
1. Cautious reasoning on $\text{DLV}[\lor, \text{not}, w]$ is $\Delta_3^P$ -complete. Hardness holds even for positive disjunctive programs with weak constraints ( $\text{DLV}[\lor, w]$ ).
2. Cautious reasoning on $\text{DLV}[\lor_h, \text{not}, w]$ is $\Delta_2^P$ -complete. Hardness holds even for $\text{DLV}[\lor_h, w]$ and for normal programs with weak constraints ( $\text{DLV}[\text{not}, w]$ ).
3. Cautious reasoning on $\text{DLV}[\text{not}_s, w]$ is $\text{P}$ -complete, with hardness holding even for positive normal programs ( $\text{DLV}[]$ ).
4. Checking whether $M$ is an optimal answer set of a $\text{DLV}[\lor, \text{not}, w]$ program is $\Pi_2^P$ -complete. Hardness holds even if $\mathcal{P}$ is a positive disjunctive program with weak constraints ( $\text{DLV}[\lor, w]$ ).
5. Checking whether $M$ is an optimal answer set of a $\text{DLV}[\lor_h, \text{not}, w]$ program is $\text{co-NP}$ -complete. Hardness holds even if $\mathcal{P}$ is positive or non-disjunctive.
6. Checking whether $M$ is an optimal answer set of a $\text{DLV}[\text{not}_s, w]$ program is $\text{P}$ -complete, with hardness holding even for positive normal programs.
Knowl 7 — Complexity-Driven Multi-Tier Architecture of the DLV Engine
model/method
The DLV engine organizes logic program evaluation into five disjoint, syntactically identified complexity classes ( $L_1$ to $L_5$ ) to avoid running higher-complexity algorithms on lower-complexity problems:
- Class $L_1$ ( $\langle \emptyset, \{w, \text{not}_s\} \rangle$ , polynomial complexity): Evaluated entirely by the Intelligent Grounding (IG) module using deductive database techniques without generating full program instantiations.
- Class $L_2$ ( $\langle \{\lor_h\}, \{\text{not}\} \rangle \setminus L_1$ , $\text{NP}$ complexity): Evaluated by the Model Generator (MG) via flat backtracking combined with a linear-time polynomial check in the Model Checker (MC).
- Class $L_3$ ( $\langle \{\lor_h\}, \{\text{not}, w\} \rangle \setminus (L_1 \cup L_2)$ , $\Delta_2^P$ complexity): Evaluated by the Weak Constraints Handler (WCH), which iteratively invokes the MG and linear-time MC.
- Class $L_4$ ( $\langle \{\lor\}, \{\text{not}\} \rangle \setminus (L_1 \cup L_2 \cup L_3)$ , $\Sigma_2^P$ complexity): Evaluated by the MG with nested invocations to the full $\text{co-NP}$ Model Checker (MC). The engine limits exponential checks strictly to the non-head-cycle-free components of the program.
- Class $L_5$ (Full language $\langle \{\lor\}, \{\text{not}, w\} \rangle \setminus (L_1 \cup L_2 \cup L_3 \cup L_4)$ , $\Delta_3^P$ complexity): Evaluated under the coordination of the WCH, driving the MG and full $\text{co-NP}$ MC.
Knowl 8 — Answer Set Generation and Optimization Procedure in DLV
algorithm
The DLV evaluation engine computes optimal answer sets by pipelining Intelligent Grounding, Model Generation, Model Checking, and Weak Constraint Handling.
Input: Safe DLV program $\mathcal{P}$
Output: All optimal answer sets of $\mathcal{P}$
GroundRules, GroundWC := IntelligentGrounding(\mathcal{P})
if $\mathcal{P}$ is stratified normal then
    return { ground atoms derived during grounding }
procedure SolveRules(GroundRules)
    Initialize partial interpretation $I := W_{\mathcal{P}}^\infty(\emptyset)$
    if $I$ is contradictory then return failure
    if $I$ is a total model of GroundRules then
        if ModelChecker(I, GroundRules) = true then return {I}
        else return failure

    Select a branching literal $l$ using lookahead heuristic
    for value $\in \{true, false\}$ do
         $I' := I \cup \{l = value\}$
        Apply deterministic pruning operators and $W_{\mathcal{P}}$ fixpoint
        if $I'$ is consistent then
            Search recursively from $I'$
    return collected valid answer sets
if GroundWC is empty then
    return SolveRules(GroundRules)
else
    // Phase 1: Determine optimal cost $s^*$
    Compute upper bound $u$ on violation cost
    Perform binary search on $[0..u]$ using ModelGenerator to find minimum cost $s^*$
    // Phase 2: Compute all witnessing answer sets with cost $s^*$
    return { $A \in \text{AS}(\text{GroundRules}) \mid H^{\mathcal{P}}(A) = s^*$ }
Model generation relies on the monotonic operator $W_{\mathcal{P}}$ , which generalizes the well-founded operator by computing greatest unfounded sets for disjunctive logic programs. Model checking verifies subset-minimality in polynomial time for head-cycle free components and invokes exponential checking only on non-HCF subprograms.
Knowl 9 — Domain-Specific Knowledge Representation Front-Ends in DLV
model/method
The DLV system provides multiple specialized front-ends that compile domain-specific knowledge representation formalisms into core DLV programs, invoke the kernel, and post-process the resulting answer sets:
1. Inheritance Front-End ( $DLP^<$ ): Supports object hierarchies ordered by a specificity partial order $<$ . Conflicting rules between more general and more specific objects are resolved via overriding, where an inherited rule is overridden if its complementary head literal is supported by a more specific object.
2. Diagnosis Front-End: Implements model-based diagnosis supporting both abductive diagnosis (over logic programming background theories) and consistency-based diagnosis (under classical semantics), with options for computing general, subset-minimal (irredundant), and single-failure diagnoses.
3. Planning Front-End ( $DLV^{\mathcal{K}}$ ): Implements the action language $\mathcal{K}$ for declarative planning under incomplete knowledge, supporting non-deterministic action effects, concurrent actions, and optimal plans minimizing cumulative action costs via weak constraints.
4. SQL3 Front-End: Compiles recursive SQL3 database queries (including hierarchical bill-of-materials queries) directly into stratified Datalog programs.
5. Meta-Interpreter and Preference Front-Ends: Supports preferred answer sets through fixed meta-interpreters, update logic programs representing sequences of program updates $P = (P_0, \dots, P_n)$ with causal rejection, and nested logic programs.
Knowl 10 — Comparative Performance of DLV across Deductive Databases, NP, and Second-Level PH Problems
empirical result
Extensive benchmarking comparing DLV against the disjunctive logic programming system GnT and the non-disjunctive ASP systems Smodels and ASSAT establishes the following performance characteristics:
1. Deductive Database Problems (Reachability, Same Generation): DLV scales to graphs with $10,000$ nodes on Reachability and $9,025$ nodes on Same Generation, whereas Lparse-based systems (GnT, Smodels, ASSAT) exceed memory limits at $700$ nodes on Reachability and $676$ nodes on Same Generation. This occurs because DLV computes dynamic variable domains during grounding, whereas Lparse requires static domain predicates and instantiates Cartesian products.
2. Second-Level PH Problems (2QBF, Strategic Companies): On $\Sigma_2^P$ -complete 2QBF instances, DLV solves all formulas up to 1,200 variables, whereas GnT (which implements disjunction via non-disjunctive rewriting) halts at 40 variables. On Strategic Companies, DLV solves instances up to 170 companies versus 160 for GnT. Smodels and ASSAT cannot express these $\Sigma_2^P$ -complete problems uniformly.
3. NP Search and Optimization (Hamiltonian Path, TSP, Ramsey Numbers, Sokoban):
  - On Hamiltonian Path, DLV solves instances up to 105 nodes, whereas Smodels stops at 50 nodes and GnT and ASSAT stop at 45 nodes.
  - On Sokoban with native grounders, DLV solves 95.0% of benchmark instances, whereas GnT solves 16.7%, ASSAT solves 41.7%, and Smodels solves 46.7%, due to Lparse generating millions of ground rules (e.g., 2,130,705 rules using 125MB for problem #48 compared to 3,236 rules using 6MB in DLV).
  - On Ramsey Numbers, SAT-based ASSAT outperforms DLV on very large search spaces where lookahead heuristics in DLV incur computational overhead.

Coverage note — No substantial contributed material was omitted. The full DLV language definition, semantics of leveled weak constraints, GCO methodology, complete complexity tables for brave/cautious reasoning and model checking, system architecture, core algorithms, domain-specific front-ends, and empirical benchmarking comparisons have all been captured.

References

1.A\textsc{nger}, C., K\textsc{onczak}, K., \textsc{and} L\textsc{inke}, T. 2001. \textsc{NoMoRe}: A System for Non-Monotonic Reasoning. In Proc. 6th International Conf. Logic Programming and Nonmonotonic Reasoning (LPNMR’01), Vienna, Austria, T. Eiter, W. Faber, and M. Truszczyński, Eds. LNCS / LNAI, 2173. Springer, 406–410.
2.A\textsc{pt}, K. \textsc{and} B\textsc{ol}, N. 1994. Logic Programming and Negation: A Survey. J. Logic Programming 19/20, 9–71.
3.A\textsc{pt}, K. R., B\textsc{lair}, H. A., \textsc{and} W\textsc{alker}, A. 1988. Towards a theory of declarative knowledge. In Foundations of Deductive Databases and Logic Programming, J. Minker, Ed. Morgan Kaufmann Pub., 89–148.
4.A\textsc{ravindan}, C., D\textsc{ix}, J., \textsc{and} N\textsc{iemela}, I. 1997. Dislop: A research project on disjunctive logic programming. AI Communications – The European Journal on Artificial Intelligence 10, 3/4, 151–165.
5.B\textsc{abovich}, Y. 2002. Cmodels homepage. http://www.cs.utexas.edu/users/tag/cmodels.html.
6.B\textsc{aral}, C. 2003. Knowledge Representation, Reasoning and Declarative Problem Solving. Camb. Univ. Press.
7.B\textsc{aral}, C. \textsc{and} G\textsc{elfond}, M. 1994. Logic programming and knowledge representation. Journal of Logic Programming 19/20, 73–148.
8.B\textsc{en}-E\textsc{liyahu}, R. \textsc{and} D\textsc{echter}, R. 1994. Propositional semantics for disjunctive logic programs. Annals of Mathematics and Artificial Intelligence 12, 53–87.
9.B\textsc{en}-E\textsc{liyahu}, R. \textsc{and} P\textsc{alopoli}, L. 1994. Reasoning with minimal models: Efficient algorithms and applications. In Proc. Fourth Int’l Conf. Principles of Knowledge Representation and Reasoning (KR-94). 39–50.
10.B\textsc{rass}, S. \textsc{and} D\textsc{ix}, J. 1995. Disjunctive semantics based upon partial and bottom-up evaluation. In Proc. 12th International Conf. Logic Programming, Tokyo, Japan, L. Sterling, Ed. MIT Press, 199–213.
11.B\textsc{rewka}, G. \textsc{and} E\textsc{iter}, T. 1999. Preferred answer sets for extended logic programs. Artificial Intelligence 109, 1-2, 297–356.
12.B\textsc{rewka}, G., N\textsc{iemela}, I., S\textsc{chaub}, T., \textsc{and} T\textsc{ruszczyński}, M. (organizers) 2002. Dagstuhl Seminar Nr. 0238, Nonmonotonic Reasoning, Answer Set Programming and Constraints, September 15-20, 2002. System Competition. http://www.cs.uni-potsdam.de/~canger/dagstuhl.html.
13.B\textsc{uccafurri}, F., F\textsc{aber}, W., \textsc{and} L\textsc{eone}, N. 2002. Disjunctive logic programs with inheritance. Theory and Practice of Logic Programming 2, 3.
14.B\textsc{uccafurri}, F., L\textsc{eone}, N., \textsc{and} R\textsc{ullo}, P. 2000. Enhancing disjunctive datalog by constraints. IEEE Transactions on Knowledge and Data Engineering 12, 5, 845–860.
15.C\textsc{adoli}, M., E\textsc{iter}, T., \textsc{and} G\textsc{ottlob}, G. 1997. Default logic as a query language. IEEE Transactions on Knowledge and Data Engineering 9, 3 (May/June), 448–463.
16.C\textsc{adoli}, M., G\textsc{iovanardi}, A., \textsc{and} S\textsc{chaerf}, M. 1997. Experimental Analysis of the Computational Cost of Evaluating Quantified Boolean Formulae. In Proc. 5th Congress of the Italian Association for Artificial Intelligence (AIIA 97), Rome, Italy*. LNCS 1321, Springer, 207–218.
17.C\textsc{ali}, A., C\textsc{alvanese}, D., G\textsc{iacomo}, G. D., \textsc{and} L\textsc{enzerini}, M. 2002. Data integration under integrity constraints. In Advanced Information Systems Engineering, 14th International Conf., CAiSE 2002, Toronto, Canada. LNCS, Springer, 262–279.
18.C\textsc{alimeri}, F., F\textsc{aber}, W., L\textsc{eone}, N., \textsc{and} P\textsc{feifer}, G. 2002. Pruning operators for answer set programming systems. In Proc. 9th International Workshop on Non-Monotonic Reasoning (NMR’2002). 200–209.
19.C\textsc{hen}, W. \textsc{and} W\textsc{arren}, D. S. 1996. Computation of stable models and its integration with logical query processing. IEEE Transactions on Knowledge and Data Engineering 8, 5, 742–757.
20.C\textsc{holewiński}, P., M\textsc{arek}, V. W., M\textsc{ikitiuk}, A., \textsc{and} T\textsc{ruszczyński}, M. 1999. Computing with default logic. Artificial Intelligence 112, 2–3, 105–147.
21.C\textsc{holewiński}, P., M\textsc{arek}, V. W., \textsc{and} T\textsc{ruszczyński}, M. 1996. Default reasoning system D\textsc{e}R\textsc{e}S. In Proc. Fifth International Conf. Principles of Knowledge Representation and Reasoning (KR ’96), Cambridge, MA. Morgan Kaufmann Pub.,518–528.
22.C\textsc{lark}, K. 1978. Negation as failure. In Logic and Data Bases, H. Gallaire and J. Minker, Eds. Plenum Press, New York, 293–322.
23.D\textsc{antsin}, E., E\textsc{iter}, T., G\textsc{ottlob}, G., \textsc{and} V\textsc{oronkov}, A. 2001. Complexity and expressive power of logic programming. ACM Computing Surveys 33, 3, 374–425.
24.D\textsc{elgrande}, J., S\textsc{chaub}, T., \textsc{and} T\textsc{ompits}, H. 2001. plp: A generic compiler for ordered logic programs. In Proc. 6th International Conf. Logic Programming and Nonmonotonic Reasoning (LPNMR-01), T. Eiter, W. Faber, and M. Truszczyński, Eds. LNCS 2173, Springer, 411–415.
25.D\textsc{ell}’A\textsc{rmi}, T., F\textsc{aber}, W., I\textsc{elpa}, G., L\textsc{eone}, N., \textsc{and} P\textsc{feifer}, G. 2003. Aggregate Functions in Disjunctive Logic Programming: Semantics, Complexity, and Implementation in DLV. In Proc. 18th International Joint Conf. Artificial Intelligence (IJCAI) 2003, Acapulco, Mexico. Morgan Kaufmann Pub.,
26.D\textsc{ix}, J. 1995. Semantics of logic programs: Their intuitions and formal properties. An overview. In Logic, Action and Information. Proc. Konstanz Colloquium in Logic and Information (LogIn’92). DeGruyter, 241–329.
27.D\textsc{ix}, J. \textsc{and} F\textsc{urbach}, U. 1996. The DFG project D\textsc{is}L\textsc{o}P on disjunctive logic programming. Computational Logic 2, 2, 89–90.
28.D\textsc{ix}, J., G\textsc{ottlob}, G., \textsc{and} M\textsc{arek}, V. W. 1996. Reducing disjunctive to non-disjunctive semantics by shift-operations. Fundamenta Informaticae 28, 87–100.
29.D\textsc{ix}, J., K\textsc{uter}, U., \textsc{and} N\textsc{au}, D. 2002. Planning in Answer Set Programming using Ordered Task Decomposition. Theory and Practice of Logic Programming. Revised paper, submitted.
30.E\textsc{ast}, D. \textsc{and} T\textsc{ruszczyński}, M. 2000. dcs: An implementation of DATALOG with constraints. In Proc. 8th International Workshop on Non-Monotonic Reasoning (NMR’2000), Breckenridge, Colorado, USA, C. Baral and M. Truszczyński, Eds.
31.E\textsc{ast}, D. \textsc{and} T\textsc{ruszczyński}, M. 2001a. System description: aspps – An implementation of answer-set programming with propositional schemata. In Proc. 6th International Conf. Logic Programming and Nonmonotonic Reasoning (LPNMR’01), Vienna, Austria, T. Eiter, W. Faber, and M. Truszczyński, Eds. LNCS / LNAI, 2173. Springer, 402–405.
32.E\textsc{ast}, D. \textsc{and} T\textsc{ruszczyński}, M. 2001b. Propositional satisfiability in answer-set programming. In Proc. Joint German/Austrian Conf. Artificial Intelligence, KI’2001. Springer Verlag, LNAI 2174, 138–153.
33.E\textsc{gly}, U., E\textsc{iter}, T., T\textsc{ompits}, H., \textsc{and} W\textsc{oltran}, S. 2000. Solving advanced reasoning tasks using quantified boolean formulas. In Proc. 17th National Conf. Artificial Intelligence (AAAI’00), July 30 – August 3, 2000, Austin, Texas USA. AAAI Press / MIT Press, 417–422.
34.E\textsc{iter}, T., F\textsc{aber}, W., G\textsc{ottlob}, G., K\textsc{och}, C., L\textsc{eone}, N., M\textsc{ateis}, C., P\textsc{feifer}, G., \textsc{and} S\textsc{carcello}, F. 1999. The DLV system. In Workshop on Logic-Based Artificial Intelligence, Washington, DC, J. Minker, Ed. Computer Science Department, University of Maryland, College Park, Maryland. Workshop Notes.
35.E\textsc{iter}, T., F\textsc{aber}, W., L\textsc{eone}, N., \textsc{and} P\textsc{feifer}, G. 2000a. Declarative problem-solving using the DLV system. In Logic-Based Artificial Intelligence, J. Minker, Ed. Kluwer Academic Pub., 79–103.
36.E\textsc{iter}, T., F\textsc{aber}, W., L\textsc{eone}, N., \textsc{and} P\textsc{feifer}, G. 2001a. Computing preferred and weakly preferred answer sets by meta-interpretation in answer set programming. In Proc. AAAI 2001 Spring Symposium on Answer Set Programming: Towards Efficient and Scalable Knowledge Representation and Reasoning, A. Provetti and S. T. Cao, Eds. AAAI Press, Stanford, CA, 45–52.
37.E\textsc{iter}, T., F\textsc{aber}, W., L\textsc{eone}, N., \textsc{and} P\textsc{feifer}, G. 2003. Computing Preferred Answer Sets by Meta-Interpretation in Answer Set Programming. Theory and Practice of Logic Programming 3, 463–498.
38.E\textsc{iter}, T., F\textsc{aber}, W., L\textsc{eone}, N., P\textsc{feifer}, G., \textsc{and} P\textsc{olleres}, A. 2000b. Planning under incomplete knowledge. In , Proc. First International Conf. Computational Logic (CL 2000), London, UK, J. Lloyd et al. LNCS / LNAI 1861. Springer, 807–821.
39.E\textsc{iter}, T., F\textsc{aber}, W., L\textsc{eone}, N., P\textsc{feifer}, G., \textsc{and} P\textsc{olleres}, A. 2001b. A logic programming approach to knowledge-state planning: Semantics and complexity. Tech. Rep. INFSYS RR-1843-01-11, Institut fur Informationssysteme, Technische Universitat Wien. To appear in ACM Transactions on Computational Logic.
40.E\textsc{iter}, T., F\textsc{aber}, W., L\textsc{eone}, N., P\textsc{feifer}, G., \textsc{and} P\textsc{olleres}, A. 2003a. A Logic Programming Approach to Knowledge-State Planning, II: the DLV $^K$ System. Artificial Intelligence 144, 1–2, 157–211.
41.E\textsc{iter}, T., F\textsc{aber}, W., L\textsc{eone}, N., P\textsc{feifer}, G., \textsc{and} P\textsc{olleres}, A. 2002b. Answer set planning under action costs. In Proc. 8th European Conf. Artificial Intelligence (JELIA), S. Flesca, S. Greco, G. Ianni, and N. Leone, Eds. LNCS 2424, Springer, 186–197.
42.E\textsc{iter}, T., F\textsc{ink}, M., S\textsc{abbatini}, G., \textsc{and} T\textsc{ompits}, H. 2001d. A framework for declarative update specifications in logic programs. In Proc. 17th International Joint Conf. Artificial Intelligence (IJCAI-01), B. Nebel, Ed. Morgan Kaufmann, 649–654. See also Tech. Rep. INFSYS RR-1843-02-07, TU Wien, 2002.
43.E\textsc{iter}, T., F\textsc{ink}, M., S\textsc{abbatini}, G., \textsc{and} T\textsc{ompits}, H. 2001e. An update front-end for extended logic programs. In Proc. 6th International Conf. Logic Programming and Nonmonotonic Reasoning (LPNMR-01), T. Eiter, W. Faber, and M. Truszczyński, Eds. LNCS 2173. Springer, 397–401.
44.E\textsc{iter}, T., F\textsc{ink}, M., S\textsc{abbatini}, G., \textsc{and} T\textsc{ompits}, H. 2002c. On properties of update sequences based on causal rejection. Theory and Practice of Logic Programming 2, 6, 721–777.
45.E\textsc{iter}, T. \textsc{and} G\textsc{ottlob}, G. 1995. On the computational cost of disjunctive logic programming: Propositional case. Annals of Mathematics and Artificial Intelligence 15, 3/4, 289–323.
46.E\textsc{iter}, T., G\textsc{ottlob}, G., \textsc{and} L\textsc{eone}, N. 1997a. Abduction from logic programs: Semantics and complexity. Theoretical Computer Science 189, 1–2 (December), 129–177.
47.E\textsc{iter}, T., G\textsc{ottlob}, G., \textsc{and} M\textsc{annila}, H. 1997b. Disjunctive datalog. ACM Transactions on Database Systems 22, 3 (September), 364–418.
48.E\textsc{iter}, T., L\textsc{eone}, N., M\textsc{ateis}, C., P\textsc{feifer}, G., \textsc{and} S\textsc{carcello}, F. 1998a. The KR System dlv: Progress report, comparisons and benchmarks. In Proc. Sixth Int’l Conf. Principles of Knowledge Representation and Reasoning (KR’98), A. G. Cohn, L. Schubert, and S. C. Shapiro, Eds. Morgan Kaufmann Pub., 406–417.
49.E\textsc{iter}, T., L\textsc{eone}, N., \textsc{and} S\textsc{acca}, D. 1997c. On the partial semantics for disjunctive deductive databases. Annals of Mathematics and Artificial Intelligence 19, 1–2 (April), 59–96.
50.E\textsc{iter}, T., L\textsc{eone}, N., \textsc{and} S\textsc{acca}, D. 1998b. Expressive power and complexity of partial models for disjunctive deductive databases. Theoretical Computer Science 206, 1–2 (October), 181–218.
51.F\textsc{aber}, W., L\textsc{eone}, N., M\textsc{ateis}, C., \textsc{and} P\textsc{feifer}, G. 1999. Using database optimization techniques for nonmonotonic reasoning. In Proc. 7th International Workshop on Deductive Databases and Logic Programming (DDLP’99), I. O. Committee, Ed. Prolog Association of Japan, 135–139.
52.F\textsc{aber}, W., L\textsc{eone}, N., \textsc{and} P\textsc{feifer}, G. 2001. Experimenting with heuristics for answer set programming. In Proc. 17th Int’l Joint Conf. Artificial Intelligence (IJCAI) 2001, Seattle, WA, USA. Morgan Kaufmann Pub., 635–640.
53.F\textsc{aber}, W. \textsc{and} P\textsc{feifer}, G. since 1996. DLV homepage. http://www.dlvsystem.com/.
54.F\textsc{ernandez}, J. \textsc{and} M\textsc{inker}, J. 1992. Semantics of disjunctive deductive databases. In Proc. 4th Intl. Conf. Database Theory (ICDT-92). Berlin, 21–50.
55.G\textsc{elfond}, M. \textsc{and} L\textsc{ifschitz}, V. 1988. The stable model semantics for logic programming. In Logic Programming: Proc. Fifth Intl Conference and Symposium. MIT Press, Cambridge, MA, 1070–1080.
56.G\textsc{elfond}, M. \textsc{and} L\textsc{ifschitz}, V. 1991. Classical negation in logic programs and disjunctive databases. New Generation Computing 9, 365–385.
57.G\textsc{elfond}, M. \textsc{and} L\textsc{ifschitz}, V. 1998. Action languages. Electronic Transactions on Artificial Intelligence 2, 3-4, 193–210.
58.G\textsc{ent}, I. \textsc{and} W\textsc{alsh}, T. 1999. Beyond NP: the QSAT phase transition. In Proc. 16th National Conf. Artificial Intelligence (AAAI/IAAI 1999), Orlando, Florida, USA. AAAI Press / MIT Press, 648–653.
59.G\textsc{iunchiglia}, E. \textsc{and} L\textsc{ifschitz}, V. 1998. An Action Language Based on Causal Explanation: Preliminary Report. In Proc. 15th National Conf. Artificial Intelligence (AAAI ’98). 623–630.
60.G\textsc{ottlob}, G. 1994. Complexity and expressive power of disjunctive logic programming. In Proc. International Logic Programming Symposium (ILPS ’94), Ithaca, NY, M. Bruynooghe, Ed. MIT Press, 23–42.
61.G\textsc{ottlob}, G., L\textsc{eone}, N., \textsc{and} V\textsc{eith}, H. 1999. Succinctness as a source of expression complexity. Annals of Pure and Applied Logic 97, 1–3, 231–260.
62.G\textsc{reco}, S. 1999. Optimization of disjunction queries. In Proc. 16th International Conf. Logic Programming (ICLP’99), Las Cruces, New Mexico, USA, D. D. Schreye, Ed. The MIT Press, 441–455.
63.J\textsc{anhunen}, T., N\textsc{iemela}, I., S\textsc{imons}, P., \textsc{and} Y\textsc{ou}, J.-H. 2000. Partiality and disjunctions in stable model semantics. In Proc. Seventh International Conf. Principles of Knowledge Representation and Reasoning (KR 2000), Breckenridge, Colorado, USA, A. G. Cohn, F. Giunchiglia, and B. Selman, Eds. Morgan Kaufmann Pub., 411–419.
64.J\textsc{anhunen}, T., N\textsc{iemela}, I., S\textsc{eipel}, D., S\textsc{imons}, P., \textsc{and} Y\textsc{ou}, J.-H. 2003. Unfolding Partiality and Disjunctions in Stable Model Semantics. Tech. Rep. cs.AI/0303009, arXiv.org.
65.J\textsc{ohnson}, D. S. 1990. A Catalog of Complexity Classes. In Handbook of Theoretical Computer Science, J. van Leeuwen, Ed. Vol. A. Elsevier Science Pub., Chapter 2.
66.K\textsc{nuth}, D. E. 1994. The Stanford GraphBase: A Platform for Combinatorial Computing. ACM Press, NY.
67.K\textsc{och}, C. \textsc{and} L\textsc{eone}, N. 1999. Stable model checking made easy. In Proc. 16th International Joint Conf. Artificial Intelligence (IJCAI’99), Stockholm, Sweden, T. Dean, Ed. Morgan Kaufmann Pub., 70–75.
68.L\textsc{embo}, D., L\textsc{enzerini}, M., \textsc{and} R\textsc{osati}, R. 2002a. Integrating inconsistent and incomplete data sources. In Proc. SEBD 2002. 299–308, Portoferraio, Isola d’Elba.
69.L\textsc{embo}, D., L\textsc{enzerini}, M., \textsc{and} R\textsc{osati}, R. 2002b. Source inconsistency and incompleteness in data integration. In Proc. Knowledge Representation meets Databases International Workshop (KRDB-02), Toulouse, France, April 2002. CEUR Electronic Workshop Proceedings http://sunsite.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-54/.
70.L\textsc{eone}, N., P\textsc{erri}, S., \textsc{and} S\textsc{carcello}, F. 2001. Improving ASP instantiators by join-ordering methods. In Proc. 6th International Conf. Logic Programming and Nonmonotonic Reasoning (LPNMR’01), Vienna, Austria, September 2001, T. Eiter, W. Faber, and M. aw Truszczyński, Eds. LNCS/LNAI 2173. Springer.
71.L\textsc{eone}, N., R\textsc{ullo}, P., \textsc{and} S\textsc{carcello}, F. 1997. Disjunctive stable models: Unfounded sets, fixpoint semantics and computation. Information and Computation 135, 2 (June), 69–112.
72.L\textsc{ifschitz}, V. 1996. Foundations of logic programming. In Principles of Knowledge Representation, G. Brewka, Ed. CSLI Publications, Stanford, 69–127.
73.L\textsc{ifschitz}, V. 2002. Answer Set Programming and Plan Generation. Artificial Intelligence 138, 39–54.
74.L\textsc{ifschitz}, V., P\textsc{earce}, D., \textsc{and} V\textsc{alverde}, A. 2001. Strongly Equivalent Logic Programs. ACM Transactions on Computational Logic 2, 4, 526–541.
75.L\textsc{ifschitz}, V. \textsc{and} T\textsc{urner}, H. 1994. Splitting a logic program. In Proc. 11th International Conf. Logic Programming (ICLP’94), Santa Margherita Ligure, Italy, P. Van Hentenryck, Ed. MIT Press, 23–37.
76.L\textsc{in}, F. \textsc{and} Z\textsc{hao}, Y. 2002. ASSAT: Computing answer sets of a logic program by SAT solvers. In Proc. 18th National Conf. Artificial Intelligence (AAAI-2002), Edmonton, Alberta, Canada. AAAI / MIT Press.
77.L\textsc{obo}, J., M\textsc{inker}, J., \textsc{and} R\textsc{ajasekar}, A. 1992. Foundations of Disjunctive Logic Programming. The MIT Press, Cambridge, MA.
78.M\textsc{arek}, W. \textsc{and} T\textsc{ruszczyński}, M. 1991. Autoepistemic logic. Journal of the ACM 38, 3, 588–619.
79.M\textsc{c}C\textsc{ain}, N. \textsc{and} T\textsc{urner}, H. 1998. Satisfiability planning with causal theories. In Proc. Sixth International Conf. Principles of Knowledge Representation and Reasoning (KR’98), A. G. Cohn, L. Schubert, and S. C. Shapiro, Eds. Morgan Kaufmann Pub., 212–223.
80.M\textsc{inker}, J. 1982. On indefinite data bases and the closed world assumption. In Proc. 6th Conf. Automated Deduction (CADE ’82), D. Loveland, LNCS 138, Springer, New York, 292–308.
81.M\textsc{inker}, J. 1994. Overview of disjunctive logic programming. Annals of Mathematics and Artificial Intelligence 12, 1–24.
82.M\textsc{inker}, J. 1996. Logic and databases: a 20 year retrospective. In Proc. International Workshop on Logic in Databases (LID ’96). LNCS 1154. Springer, 3–57.
83.N\textsc{icolas}, P., S\textsc{aubion}, F., \textsc{and} S\textsc{tephan}, I. 2002. Answer Set Programming by Ant Colony Optimization. In Proc. 8th European Conf. Artificial Intelligence (JELIA), S. Flesca, S. Greco, G. Ianni, and N. Leone, Eds. LNCS 2424, Springer, 186–197.
84.N\textsc{iemela}, I. \textsc{and} S\textsc{imons}, P. 1997. Smodels – an implementation of the stable model and well-founded semantics for normal logic programs. In Proc. 4th International Conf. Logic Programming and Nonmonotonic Reasoning (LPNMR’97), J. Dix, U. Furbach, and A. Nerode, Eds. LNCS / LNAI, vol. 1265. Springer, 420–429.
85.N\textsc{iemela}, I., S\textsc{imons}, P., \textsc{and} S\textsc{yrjanen}, T. 2000. Smodels: A system for answer set programming. In Proc. 8th International Workshop on Non-Monotonic Reasoning (NMR’2000), Breckenridge, Colorado, USA, C. Baral and M. Truszczyński, Eds.
86.P\textsc{apadimitriou}, C. H. 1984. The complexity of unique solutions. Journal of the ACM 31, 492–500.
87.P\textsc{apadimitriou}, C. H. 1994. Computational Complexity. Addison-Wesley.
88.P\textsc{earce}, D., S\textsc{arsakov}, V., S\textsc{chaub}, T., T\textsc{ompits}, H., \textsc{and} W\textsc{oltran}, S. 2002. A polynomial translation of logic programs with nested expressions into disjunctive logic programs: Preliminary report. In Proc. 9th International Workshop on Non-Monotonic Reasoning (NMR’2002), Toulouse, France.
89.P\textsc{oole}, D. 1989. Explanation and prediction: An architecture for default and abductive reasoning. Computational Intelligence 5, 1, 97–110.
90.P\textsc{rzymusinski}, T. 1990. Stationary semantics for disjunctive logic programs and deductive databases. In Proc. North American Conf. Logic Programming. 40–62.
91.P\textsc{rzymusinski}, T. 1995. Static semantics for normal and disjunctive logic programs. Annals of Mathematics and Artificial Intelligence 14, 323–357.
92.P\textsc{rzymusinski}, T. C. 1988. On the declarative semantics of deductive databases and logic programs. In Foundations of Deductive Databases and Logic Programming, J. Minker, Ed. Morgan Kaufmann, 193–216.
93.P\textsc{rzymusinski}, T. C. 1991. Stable semantics for disjunctive programs. New Generation Comp. 9, 401–424.
94.R\textsc{adziszowski}, S. P. 1994. Small ramsey numbers. The Electronic Journal of Combinatorics 1. Revision 9: July 15, 2002.
95.R\textsc{ao}, P., S\textsc{agonas}, K. F., S\textsc{wift}, T., W\textsc{arren}, D. S., \textsc{and} F\textsc{reire}, J. 1997. XSB: A system for efficiently computing well-founded semantics. In Proc. 4th International Conf. Logic Programming and Non-Monotonic Reasoning (LPNMR’97), J. Dix, U. Furbach, and A. Nerode, Eds. LNCS / LNAI 1265. Springer, 2–17.
96.R\textsc{eiter}, R. 1987. A theory of diagnosis from first principles. Artificial Intelligence 32, 57–95.
97.R\textsc{oss}, K. 1990. The well-founded semantics for disjunctive logic programs. In Deductive and Object-Oriented Databases, W. Kim, J.-M. Nicolas, and S. Nishio, Eds. Elsevier Science Pub. B. V., 385–402.
98.S\textsc{akama}, C. 1989. Possible model semantics for disjunctive databases. In Proc. First Intl. Conf. on Deductive and Object-Oriented Databases (DOOD-89). North-Holland, Kyoto, Japan, 369–383.
99.S\textsc{chaub}, T. \textsc{and} W\textsc{ang}, K. 2001. A comparative study of logic programs with preference. In Proc. 17th International Joint Conf. Artificial Intelligence (IJCAI) 2001. Morgan Kaufmann Pub., 597–602.
100.S\textsc{eipel}, D. \textsc{and} T\textsc{hone}, H. 1994. DisLog – A system for reasoning in disjunctive deductive databases. In Proc. International Workshop on the Deductive Approach to Information Systems and Databases (DAISD’94), A. Olive, Ed. Universitat Politecnica de Catalunya (UPC), 325–343.
101.S\textsc{imons}, P. 2000. Extending and Implementing the Stable Model Semantics. Ph.D. thesis, Helsinki University of Technology, Finland.
102.S\textsc{imons}, P., N\textsc{iemela}, I., \textsc{and} S\textsc{oininen}, T. 2002. Extending and implementing the stable model semantics. Artificial Intelligence 138.
103.S\textsc{yrjanen}, T. 2002. Lparse 1.0 user’s manual. URL:`http://www.tcs.hut.fi/Software/smodels/lparse.ps.gz`.
104.V\textsc{an} G\textsc{elder}, A., R\textsc{oss}, K., \textsc{and} S\textsc{chlipf}, J. 1991. The well-founded semantics for general logic programs. Journal of the ACM 38, 3, 620–650.
105.W\textsc{olfinger}, B., Ed. 1994. Workshop: Disjunctive Logic Programming and Disjunctive Databases, 13th IFIP World Computer Congress, Hamburg, Germany. German Society for Computer Science (GI), Springer, Berlin.
106.Z\textsc{hao}, Y. 2002. ASSAT homepage. http://assat.cs.ust.hk/.

Citation

MLA

Leone, N., et al. “The DLV System for Knowledge Representation and Reasoning”. ACM Transactions on Computational Logic, vol. 7, no. 3, 2006, pp. 499–562, https://doi.org/10.1145/1149114.1149117.

APA

Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S., & Scarcello, F. (2006). The DLV system for knowledge representation and reasoning. ACM Transactions on Computational Logic, 7(3), 499–562. https://doi.org/10.1145/1149114.1149117

Chicago

Leone, N., G. Pfeifer, W. Faber, et al. 2006. “The DLV System for Knowledge Representation and Reasoning”. ACM Transactions on Computational Logic 7 (3): 499–562. https://doi.org/10.1145/1149114.1149117.

Harvard

Leone, N. et al. (2006) “The DLV system for knowledge representation and reasoning”, ACM Transactions on Computational Logic, 7(3), pp. 499–562. Available at: https://doi.org/10.1145/1149114.1149117.

Vancouver

1. Leone N, Pfeifer G, Faber W, Eiter T, Gottlob G, Perri S, Scarcello F (2006) The DLV system for knowledge representation and reasoning. ACM Transactions on Computational Logic 7:499–562

BibTeX

@article{Leone_2006, title={The DLV system for knowledge representation and reasoning}, volume={7}, ISSN={1557-945X}, url={http://dx.doi.org/10.1145/1149114.1149117}, DOI={10.1145/1149114.1149117}, number={3}, journal={ACM Transactions on Computational Logic}, publisher={Association for Computing Machinery (ACM)}, author={Leone, Nicola and Pfeifer, Gerald and Faber, Wolfgang and Eiter, Thomas and Gottlob, Georg and Perri, Simona and Scarcello, Francesco}, year={2006}, month=July, pages={499–562} }

Metadata:Crossref

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

The DLV system for knowledge representation and reasoning

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Syntax and Ground Semantics of Disjunctive Datalog with Leveled and Weighted Weak Constraints

Knowl 2 — Objective Function and Optimal Answer Sets for Leveled Weak Constraints

Knowl 3 — The Guess/Check/Optimize (GCO) Declarative Programming Methodology

Knowl 4 — Computational Complexity Classification of Brave and Cautious Reasoning across DLV Language Fragments

Knowl 5 — Computational Complexity of Answer Set Checking across DLV Language Fragments

Knowl 6 — Completeness Results for Cautious Reasoning and Model Checking with Weak Constraints

Knowl 7 — Complexity-Driven Multi-Tier Architecture of the DLV Engine

Knowl 8 — Answer Set Generation and Optimization Procedure in DLV

Knowl 9 — Domain-Specific Knowledge Representation Front-Ends in DLV

Knowl 10 — Comparative Performance of DLV across Deductive Databases, NP, and Second-Level PH Problems

References

Citation

BibTeX

Source Code

Access the Paper