Mixed integer programming methods for computing nonmonotonic deductive databases

Colin Bell; Anil Nerode; Raymond T. Ng; V. S. Subrahmanian

doi:10.1145/195613.195637

Back

Mixed integer programming methods for computing nonmonotonic deductive databases

Journal article

Peer reviewed

Mixed integer programming methods for computing nonmonotonic deductive databases

Colin Bell, Anil Nerode, Raymond T. Ng and V. S. Subrahmanian

Journal of the ACM, Vol.41(6), pp.1178-1215

11/01/1994

DOI: 10.1145/195613.195637

Files and links (1)

url

https://doi.org/10.1145/195613.195637View

Published (Version of record) Open Access

Abstract

Though the declarative semantics of both explicit and nonmonotonic negation in logic programs has been studied extensively, relatively little work has been done on computation and implementation of these semantics. In this paper, we study three different approaches to computing stable models of logic programs based on mixed integer linear programming methods for automated deduction introduced by R. Jeroslow. We subsequently discuss the relative efficiency of these algorithms. The results of experiments with a prototype compiler implemented by us tend to confirm our theoretical discussion. In contrast to resolution, the mixed integer programming methodology is both fully declarative and handles reuse of old computations gracefully. We also introduce, compare, implement, and experiment with linear constraints corresponding to four semantics for “explicit” negation in logic programs: the four-valued annotated semantics [Blair and Subrahmanian 1989], the Gelfond-Lifschitz semantics [1990], the over-determined models [Grant and Subrahmanian 1989], the Gelfond-Lifschitz semantics [1990], the over-determined models [Grant and Subrahmanian 1990], and the classical logic semantics. Gelfond and Lifschitz[1990] argue for simultaneous use of two modes of negation in logic programs, “classical” and “nonmonotonic,” so we give algorithms for computing “answer sets” for such logic programs too.

Details

Title: Subtitle: Mixed integer programming methods for computing nonmonotonic deductive databases
Creators: Colin Bell - University of Iowa
Anil Nerode - Cornell University
Raymond T. Ng - University of British Columbia
V. S. Subrahmanian - University of Maryland, College Park
Resource Type: Journal article
Publication Details: Journal of the ACM, Vol.41(6), pp.1178-1215
DOI: 10.1145/195613.195637
ISSN: 0004-5411
eISSN: 1557-735X
Number of pages: 38
Language: English
Date published: 11/01/1994
Academic Unit: Business Analytics
Record Identifier: 9984963042802771

Metrics

1 Record Views