Mixed Integer Programming Methods for Computing Nonmonotonic Deductive Databases

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

Research output: Contribution to journalArticlepeer-review

52 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)1178-1215
Number of pages38
JournalJournal of the ACM (JACM)
Volume41
Issue number6
DOIs
StatePublished - Jan 11 1994
Externally publishedYes

Keywords

  • deductive databases
  • logic programming
  • nonmonotonic reasoning
  • operations research

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Mixed Integer Programming Methods for Computing Nonmonotonic Deductive Databases'. Together they form a unique fingerprint.

Cite this