Enhancing efficiency and expressiveness in answer set programming systems

Abstract

In recent years, Answer Set Programming (ASP) has been recognized as an effective method for declarative knowledge representation and reasoning. The ASP paradigm can be seen as a fusion between logic programming and database technology, which allows for a purely declarative way of specifying and solving problems up to a particular complexity class on the second level of the polynomial hierarchy. This thesis consists of two parts: In the first part, the system DLV and its architecture is presented, after a brief introduction to Answer Set Programming. Two modules which are critical for efficiency are analyzed in detail, new methods for the implementation of these components are described, the utility of which is assessed by experiments. In the second part, the kernel system, which is the focus of the first part, is extended in various ways. On the one hand extensions of the basic formalism are presented, which either allow for representing a larger set of problems, or which ease the formulation of certain relationships. On the other hand, we show how to extend the basic system to solve problems specified in various formalisms by using an ASP system.

Answer Set Programming (ASP) hat sich in den letzten Jahren zu einer anerkannt effektiven Methode zur deklarativen Wissensrepraesentation und automatisierten Schlussfolgerung entwickelt. Der ASP Formalismus kann als Fusion von Logischer Programmierung und Datenbanken betrachtet werden, mithilfe dessen alle Problemstellungen einer gewissen Komplexitaetsklasse der zweiten Stufe der polynomiellen Hierarchie ausdrueckbar und loesbar sind. Die vorliegende Arbeit gliedert sich in zwei Teile: Im ersten Teil wird, nach einer kurzen Einfuehrung in Answer Set Programming, das System DLV und dessen Architektur vorgestellt. Zwei besonders effizienzrelevante Komponenten dieses Systems werden genau analysiert und im Zuge dessen werden neuartige Verfahren fuer die Implementierung dieser Komponenten praesentiert, deren Nuetzlichkeit experimentell belegt wird. Im zweiten Teil wird das im ersten Teil behandelte Kernsystem auf verschiedene Weise erweitert. Einerseits werden Erweiterungen des Basissystems vorgestellt, die entweder die Ausdrueckbarkeit einer groesseren Menge von Problemstellungen ermoeglichen, oder aber die Formulierung bestimmter Zusammenhaenge erleichtern. Andererseits wird gezeigt, wie man auf einfache, aber effektive Weise das Basissystem erweitern kann, um in unterschiedlichen Formalismen repraesentierte Problemstellungen mittels eines ASP Systems loesen zu koennen.