T. Wijaya:
"Top-Down Evaluation Techniques for Modular Nonmonotonic Logic Programs";
Supervisor: T. Eiter, T. Krennwallner, M. Dao-Tran; Institut für Informationssysteme, 2011; final examination: 2011-08-22.

Answer Set Programming (ASP) is a very useful tool for knowledge representation and declarative problem solving. Recently, enabling modularity aspects in ASP has gained increasing interest to help composing (sub-)programs to a combined logic program. Modularity not only allows for problem decomposition, but also facilitates high (code) reusability and provides better support for large-scale projects. Among the contemporary approaches, Modular Nonmonotonic Logic Programs (MLPs) have distinguished strengths, e.g., they allow for mutual recursive calls and utilize predicate symbols as module inputs, resulting in more dynamic problem encodings. MLPs are very expressive and have high computational complexity, thus creating practicable implementations for this formalism is a very challenging task. In this thesis, we develop TD-MLP, a concrete algorithm for computing answer sets for MLPs. TD-MLP is based on a top-down evaluation technique which considers only relevant module calls. In addition, we have devised an optimization technique that splits module instantiations to avoid redundant recomputation. We have incorporated the optimization technique into the original approach and experiments on a benchmark suite show promising results. Furthermore, we also evaluate the performance of different encodings for different problems, involving modular and ordinary encodings. Experiments show in some cases our modular encoding can outperforms the ordinary ones.

Knowledge Representation, Nonmonotonic Reasoning, Modular Logic Programming, Answer Set Programming

Project Head Thomas Eiter:
Modulare HEX-Programme