WFS + branch and bound = stable models

Author

Subrahmanian, V.S. ; Nau, Dana ; Vago, Carlo

Author_Institution

Dept. of Comput. Sci., Maryland Univ., College Park, MD, USA

Volume

7

Issue

3

fYear

1995

fDate

6/1/1995 12:00:00 AM

Firstpage

362

Lastpage

377

Abstract

Though the semantics of nonmonotonic logic programming has been studied extensively, relatively little work has been done on operational aspects of these semantics. In this paper, we develop techniques to compute the well-founded model of a logic program. We describe a prototype implementation and show, based on experimental results, that our technique is more efficient than the standard alternating fixpoint computation. Subsequently, we develop techniques to compute the set of all stable models of a deductive database. These techniques first compute the well-founded semantics and then use an intelligent branch and bound strategy to compute the stable models. We report on our implementation, as well as on experiments that we have conducted on the efficiency of our approach

Keywords

deductive databases; logic programming; nonmonotonic reasoning; deductive database; fixpoint computation; intelligent branch and bound strategy; logic program; nonmonotonic logic programming semantics; operational aspects; prototype implementation; Algorithm design and analysis; Compaction; Computational modeling; Computer science; Deductive databases; Logic design; Logic programming; Prototypes;

fLanguage

English

Journal_Title

Knowledge and Data Engineering, IEEE Transactions on

Publisher

ieee

ISSN

1041-4347

Type

jour

DOI

10.1109/69.390244

Filename

390244