Goal-directed answer set programming.

摘要

Answer Set Programming (ASP) provides an attractive means for integrating non-monotonic reasoning into logic programming. However, current ASP solvers are implemented using bottom-up execution algorithms. That is, none of the current approaches to implementation are goal-directed. This results in a number of issues which prevent ASP from being adopted on a larger scale, including the need to compute an entire answer set for any query and the ability of minor inconsistencies to invalidate solutions in unrelated areas of a knowledgebase. This dissertation presents a goal-directed method for executing answer set programs in the style of Selective Linear Definite clause resolution (SLD resolution), and discusses its advantages and how it addresses the first of the problems listed above. The implementation of the algorithm in the Galliwasp system is also presented and its performance is compared to that of other popular ASP solvers. Next, optimization techniques developed to improve performance are discussed and their advantages and disadvantages compared, along with the performance of various combinations of the techniques. Finally, Dynamic Consistency Checking (DCC), a technique for querying inconsistent databases which addresses the second problem listed above, is covered.