Talks and Poster Presentations (with Proceedings-Entry):
"Solving Hard Disjunctive Logic Programs Faster";
Poster: 2003 Joint Conference on Declarative Programming,
Reggio Calabria, Italien;
- 2003-09-05; in: "Proceedings of the 2003 Joint Conference on Declarative Programming",
Disjunctive logic Programming (DLP) under the consistent answer set semantics is an advanced formalism for knowledge representation and reasoning. It is, under widely believed assumptions, strictly more expressive than normal (disjunction-free) logic programming, whose expressiveness is limited to properties decidables in NP.
However, this higher expressiveness comes at a computational cost, and while there are now several efficient systems for normal logic programming under the answer set semantics, we are only aware of two serious implementations for the full, disjunctive case.
In this paper we investigate a novel technique to couple two main modules usually employed for the implementation of a DLP system more tightly.; a model generator (which generates model candidates using a backtracking procedure) and a model checker (which verifies whether such a candidate indeed is an answer set). Instead of using the model checker only as a boolean oracle, in our approach, ffor every failed check, the model checker also returns a so-called unfound set. Intuitively, this set provides a diagnosis why the model candidate is not an answer set, and the generator employs this knowledge to backtrack until the set is no longer unfound, which is vastly more efficient than employing full-fledged model check to control backtracking.
WE implemented this approach in DLP, the leading implementation of DLP according to recent comparisons, and experiments on hard benchmark instances indeed show a significant speedup.
Online library catalogue of the TU Vienna:
Created from the Publication Database of the Vienna University of Technology.