T. Eiter, M. Fink, T. Krennwallner, C. Redl, P. Schüller:
"Improving HEX-Program Evaluation based on Unfounded Sets";
Report for Institut für Informationssysteme; Report No. RR-1843-12-08, 2012; 47 pages.

HEX programs extend logic programs with external computations through external atoms. As already reasoning from Horn programs with nonmonotonic external atoms of polynomial complexity is on the second level of the polynomial hierarchy, minimality checking of answer set candidates needs special attention. To this end, we present an approach based on unfounded sets as a generalization of related techniques for ordinary ASP programs. The unfounded set detection is efficiently expressed as a propositional SAT problem, for which we provide two different encodings and optimizations to them. We then integrate our approach into a previously developed evaluation framework for HEX-programs, which is enriched by additional learning techniques that aim at avoiding the reconstruction of the same or related unfounded sets. Furthermore, we provide a syntactic criterion that allows one to skip the minimality check in practically relevant cases. It benignly carries over to the components of an appropriate program decomposition, which can be exploited to restrict unfounded set search to relevant parts of the program. An experimental evaluation shows that the new approach significantly decreases runtime.

Project Head Thomas Eiter:
Evaluierung von ASP Programming mit Externen Zugriffen