Computing Stable Models with Quantified Boolean Formulas: Some Experimental Results

Answer Set Programming: Towards Efficient and Scalable Knowledge Representation and Reasoning

Volume

Papers from the 2001 AAAI Spring Symposium

Contents

Quantified Boolean formulas (QBFs) are extensions of ordinary propositional formulas which admit efficient representations of many important reasoning tasks. The existence of sophisticated QBF-solvers makes it possible to realize prototype systems for quite different knowledge-representation formalisms in a uniform manner. The system QUIP follows this idea and implements inference tasks from the area of nonmonotonic reasoning by using suitable encodings to QBFs. In this paper, we report experimental results evaluating the performance of QUIP. In particular, we deal here with the disjunctive logic programming module of QUIP, which will be the subject of two kinds of performance tests: First, we compare QUIP with the state-of-the-art logic programming systems dlv and smodels, and second, we examine the performance of different QBF-solvers on the considered problem classes. As benchmark philosophy we employ classes of disjunctive logic programs which are responsible for the hardness of the given decision problems. The results show reasonable performance of the QBF approach and indicate possible improvements of QUIP by exploiting different QBF solvers as underlying inference engines.