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 }_3^P$-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.

56 pages, 9 figures, 6 tables

References in corpus (8)

• A Logic Programming Approach to Knowledge-State Planning: Semantics and Complexity
• Smodels: A System for Answer Set Programming
• DLV - A System for Declarative Problem Solving
• Extending and Implementing the Stable Model Semantics
• Proceedings of the 8th International Workshop on Non-Monotonic Reasoning, NMR'2000
• Computing Preferred Answer Sets by Meta-Interpretation in Answer Set Programming
• dcs: An Implementation of DATALOG with Constraints
• Disjunctive Logic Programs with Inheritance

Cited by in corpus (128)

• Complexity of Judgment Aggregation
• The third open Answer Set Programming competition
• Acyclicity Notions for Existential Rules and Their Application to Query Answering in Ontologies
• A Model-driven Approach for Continuous Performance Engineering in Microservice-based Systems
• Predicate Logic as a Modelling Language: The IDP System
• Discovering Classes of Strongly Equivalent Logic Programs
• Predicate Logic as a Modeling Language: Modeling and Solving some Machine Learning and Data Mining Problems with IDP3
• Making Use of Advances in Answer-Set Programming for Abstract Argumentation Systems
• A Multi-Engine Approach to Answer Set Programming
• The Seventh Answer Set Programming Competition: Design and Results
• Vicious Circle Principle and Logic Programs with Aggregates
• Automata for Infinite Argumentation Structures
• The Vadalog System: Datalog-based Reasoning for Knowledge Graphs
• (Re)configuration based on model generation
• Data Conflict Resolution Using Trust Mappings
• Computing Stable Models of Normal Logic Programs Without Grounding
• Optimizing Answer Set Computation via Heuristic-Based Decomposition
• URSA: A System for Uniform Reduction to SAT
• Beyond NP: Quantifying over Answer Sets
• Generalizing Boolean Satisfiability I: Background and Survey of Existing Work
• Combining Relational Algebra, SQL, Constraint Modelling, and Local Search
• A Framework for Easing the Development of Applications Embedding Answer Set Programming
• Modular Action Language ALM
• ASPeRiX, a First Order Forward Chaining Approach for Answer Set Computing
• Anytime Computation of Cautious Consequences in Answer Set Programming
• Conflict-driven ASP Solving with External Sources
• Partial Compilation of ASP Programs
• Efficiently Coupling the I-DLV Grounder with ASP Solvers
• Computing Preferred Extensions in Abstract Argumentation: a SAT-based Approach
• Characterising equilibrium logic and nested logic programs: Reductions and complexity
• Utilizing ASP for Generating and Visualizing Argumentation Frameworks
• Model-Based Safety and Security Engineering
• The Design of the Fifth Answer Set Programming Competition
• Consistency and Trust in Peer Data Exchange Systems
• Lifted Unit Propagation for Effective Grounding
• SPARC - Sorted ASP with Consistency Restoring Rules
• Security Engineering for ISO 21434
• Random Logic Programs: Linear Model
• The Window Validity Problem in Rule-Based Stream Reasoning
• Semantically Correct Query Answers in the Presence of Null Values
• Testing and Debugging Techniques for Answer Set Solver Development
• Specifying and Exploiting Non-Monotonic Domain-Specific Declarative Heuristics in Answer Set Programming
• Solving Advanced Argumentation Problems with Answer Set Programming
• Grounding Recursive Aggregates: Preliminary Report
• Extended ASP tableaux and rule redundancy in normal logic programs
• Logic Programming Applications: What Are the Abstractions and Implementations?
• Using Answer Set Programming in an Inference-Based approach to Natural Language Semantics
• Dynamic Magic Sets for Super-Consistent Answer Set Programs
• anthem: Transforming gringo Programs into First-Order Theories (Preliminary Report)
• Encoding Selection for Solving Hamiltonian Cycle Problems with ASP
• A general approach to belief change in answer set programming
• Origins of Answer-Set Programming - Some Background And Two Personal Accounts
• Consistent Query Answering via ASP from Different Perspectives: Theory and Practice
• Disjunctive Answer Set Solvers via Templates
• Magic Sets for Disjunctive Datalog Programs
• Degrees of Laziness in Grounding: Effects of Lazy-Grounding Strategies on ASP Solving
• Complexity of super-coherence problems in ASP
• Approximating Constraint Propagation in Datalog
• Symmetry-breaking Answer Set Solving
• Reducing Fuzzy Answer Set Programming to Model Finding in Fuzzy Logics
• Probabilistic reasoning with answer sets
• The DLVHEX System for Knowledge Representation: Recent Advances (System Description)
• Craig Interpolation with Clausal First-Order Tableaux
• Abstract Solvers for Computing Cautious Consequences of ASP programs
• The Causality/Repair Connection in Databases: Causality-Programs
• Improving the Deductive System DES with Persistence by Using SQL DBMS's
• Logic programs with monotone abstract constraint atoms
• Functional Answer Set Programming
• The informal semantics of Answer Set Programming: A Tarskian perspective
• Exploiting Partial Knowledge in Declarative Domain-Specific Heuristics for ASP
• Eliminating Unfounded Set Checking for HEX-Programs
• Repair-Based Degrees of Database Inconsistency: Computation and Complexity
• Consistent Answers of Aggregation Queries using SAT Solvers
• Team-building with Answer Set Programming in the Gioia-Tauro Seaport
• Implementing Default and Autoepistemic Logics via the Logic of GK
• Experiences with Some Benchmarks for Deductive Databases and Implementations of Bottom-Up Evaluation
• LP2PB: Translating Answer Set Programs into Pseudo-Boolean Theories
• iWarded: A System for Benchmarking Datalog+/- Reasoning (technical report)
• Combining Event Calculus and Description Logic Reasoning via Logic Programming
• Automated Hybrid Grounding Using Structural and Data-Driven Heuristics
• The Temporal Vadalog System: Temporal Datalog-based Reasoning
• Handling irresolvable conflicts in the Semantic Web: an RDF-based conflict-tolerant version of the Deontic Traditional Scheme
• Better Paracoherent Answer Sets with Less Resources
• Reasoning with Justifiable Exceptions in Contextual Hierarchies (Appendix)
• The SeaLion has Landed: An IDE for Answer-Set Programming---Preliminary Report
• NP Datalog: a Logic Language for Expressing NP Search and Optimization Problems
• A Paraconsistent ASP-like Language with Tractable Model Generation
• Semantical Characterizations and Complexity of Equivalences in Answer Set Programming
• Achievements in Answer Set Programming
• Unit Testing in ASP Revisited: Language and Test-Driven Development Environment
• ASP-based Multi-shot Reasoning via DLV2 with Incremental Grounding
• Query Stability in Monotonic Data-Aware Business Processes [Extended Version]
• Application Placement with Constraint Relaxation
• Exchange-Repairs: Managing Inconsistency in Data Exchange
• Second-Order Specifications and Quantifier Elimination for Consistent Query Answering in Databases
• FOLASP: FO(.) as Input Language for Answer Ser Solvers
• Reasoning about Counterfactuals and Explanations: Problems, Results and Directions
• Less Manual Work for Safety Engineers: Towards an Automated Safety Reasoning with Safety Patterns
• Efficiency Analysis of ASP Encodings for Sequential Pattern Mining Tasks
• Stable-Unstable Semantics: Beyond NP with Normal Logic Programs
• Datalog Rewritability of Disjunctive Datalog Programs and its Applications to Ontology Reasoning
• The Multi-engine ASP Solver ME-ASP: Progress Report
• Efficient Approximation of Well-Founded Justification and Well-Founded Domination (Corrected and Extended Version)
• D-FLAT: Declarative Problem Solving Using Tree Decompositions and Answer-Set Programming
• The Partner Units Configuration Problem: Completing the Picture
• Translating NP-SPEC into ASP
• Index sets for Finite Normal Predicate Logic Programs
• A General Framework for Equivalences in Answer-Set Programming by Countermodels in the Logic of Here-and-There
• Reasoning Support for Risk Prediction and Prevention in Independent Living
• A Program-Level Approach to Revising Logic Programs under the Answer Set Semantics
• Outlier Detection by Logic Programming
• Symmetry Breaking for Answer Set Programming
• Using ASP with recent extensions for causal explanations
• Unit Testing in ASPIDE
• Querying Biomedical Ontologies in Natural Language using Answer Set
• A Knowledge-Based Approach for Selecting Information Sources
• Logic programming with social features
• Achieving Data Privacy through Secrecy Views and Null-Based Virtual Updates
• Improving DPLL Solver Performance with Domain-Specific Heuristics: the ASP Case
• On the complexity of identifying Head Elementary Set Free programs
• The CIFF Proof Procedure for Abductive Logic Programming with Constraints: Theory, Implementation and Experiments
• A formalism for causal explanations with an Answer Set Programming translation
• Experimenting with recursive queries in database and logic programming systems
• Planning with Preferences using Logic Programming
• Design and Implementation of Aggregate Functions in the DLV System
• Abductive Logic Programs with Penalization: Semantics, Complexity and Implementation
• SmartPM: Automatic Adaptation of Dynamic Processes at Run-Time
• Scaling-Up Reasoning and Advanced Analytics on BigData