By Francesco Calimeri,
Università della Calabria
March 2006
Abstract
Disjunctive Logic Programming (DLP) is a declarative approach to programming, which has been recently proposed in the area of nonmonotonic reasoning and logic programming. It can be view also as a logic programming alternative to SAT-based programming, which is successfully and widely used in the area of Artificial Intelligence.
DLP is very expressive: it allows to express every property of finite structures that is decidable in the complexity class ΣP2 (NPNP). However, the high expressiveness of Disjunctive Logic Programming comes at the price of a high computational cost. For many years the research on DLP has been carried out only on the theoretical side, because the hardness of the evaluation of DLP programs has discouraged the implementation of DLP engines for quite some time.
Several efforts have been made in the direction of implementing efficient DLP systems. After some pioneering work on stable model computation, a number of modern DLP systems are now available. Among them, the DLV system allows to use DLP for solving real- world problems in a number of application areas, including planning, scheduling, automatic correction of census data, as well as for complex data manipulations.
However, practical applications in many emerging areas, such as Knowledge Management or Information Integration, require always higher performances, and therefore the design and the implementation of suitable optimization techniques are fundamental for the efficiency of systems like DLV. Moreover, despite the high expressive power of DLP, there are some kinds of problems that cannot be encoded in a natural way and then the resulting programs are often complex and tricky.
In this thesis we focus on the issues above: from the one hand we propose new techniques aiming at improving the efficiency of DLV; on the other hand, we propose new extensions of Disjunctive Logic Programming for enhancing its knowledge modelling abilities.
Briefly, the main contributions of the thesis are the following:
1. We study DLP, analyze its complexity and its exploitation for knowledge representation and reasoning.
2. WedescribethemainstepsofthecomputationalprocessperformedbyDLP systems with a focus on search space pruning, which is crucial for efficiency. We analyze the properties of the disjunctive extensions of two well-known pruning operators for logic programming. We design an intelligent strategy for combining the two pruning operators cited above, which exploits the advantages of both.
3. We implement our approach in the DLV system, taking care of efficiency issues and respecting the known complexity bounds, and reporting experimental results on a number of benchmark problems to assess the impact of our approach.
4. We introduce a formal framework, for accommodating external predicates in the context of Disjunctive Logic Programming. We show that the framework enhances the applicability of DLP to a variety of problems such as string and algebraic manipulation.
5. We discuss implementation issues, and show how we have integrated the support for external predicate in the DLV system, which is, this way, enabled with the possibility of using external sources of computation.
6. We introduce the template paradigm into DLP, providing syntax and giving a clear operational semantics. We discuss theoretical properties of the extension and its main advantages.
7. We extend the DLV system with the capability to support the template paradigm.