[Zurück]


Zeitschriftenartikel:

T. Eiter, M. Fink, T. Krennwallner, C. Redl:
"Conflict-driven ASP solving with external sources";
Theory and Practice of Logic Programming, 12 (2012), 4-5; S. 659 - 679.



Kurzfassung englisch:
Answer Set Programming (ASP) is a well-known problem solving approach based on nonmonotonic logic programs and efficient solvers. To enable access to external information, HEX-programs extend programs with external atoms, which allow for a bidirectional communication between the logic program and external sources of computation (e.g., description logic reasoners and Web resources). Current solvers evaluate HEX-programs by a translation to ASP itself, in which values of external atoms are guessed and verified after the ordinary answer set computation. This elegant approach does not scale with the number of external accesses in general, in particular in presence of nondeterminism (which is instrumental for ASP). In this paper, we present a novel, native algorithm for evaluating HEX-programs which uses learning techniques. In particular, we extend conflict-driven ASP solving techniques, which prevent the solver from running into the same conflict again, from ordinary to HEX-programs. We show how to gain additional knowledge from external source evaluations and how to use it in a conflict-driven algorithm. We first target the uninformed case, i.e., when we have no extra information on external sources, and then extend our approach to the case where additional meta-information is available. Experiments show that learning from external sources can significantly decrease both the runtime and the number of considered candidate compatible sets.

Schlagworte:
Answer Set Programming, Nonmonotonic Reasoning, Conflict-Driven Clause Learning


"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1017/S1471068412000233



Zugeordnete Projekte:
Projektleitung Thomas Eiter:
Evaluierung von ASP Programming mit Externen Zugriffen

Projektleitung Thomas Eiter:
Modulare HEX-Programme

Projektleitung Thomas Eiter:
Schließen in hybriden Wissensbasen

Projektleitung Michael Fink:
Inconsistency Management for Knowledge-Integration Systems


Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.