Default theory for well founded semantics with explicit negation

Research output: Contribution to journalArticle

10 Citations (Scopus)

Abstract

One aim of this paper is to define a default theory for Well Founded Semantics of logic programs which have been extended with explicit negation, such that the models of a program correspond exactly to the extensions of the default theory corresponding to the program. To do so we must introduce a new default theory semantics that satisfies principles of modularity, enforcedness, and uniqueness of minimal extension (if it has an extension), which have a natural counterpart in the program semantics. Other default theories, with which we compare our own, do not satisfy all these principles, namely Reiter’s default theory, Baral and Subrahmanian’s well founded extensions, and Przymusinski’s stationary extensions. The relationship between logic programs and defaults theories opens the way for a mutual fertilization, which we have enhanced: On the one hand, we widen the class of programs which can be given a semantics by a suitable default theory, show that explicit negation can be translated into classical negation in such a default theory, and that it clarifies the use of rules in extended logic programs. On the other hand, since our logic program semantics is definable by a monotonic fixpoint operator, it has desirable computational properties, including top-down and bottom-up procedures. As our semantics is sound with respect to Reiter’s default semantics, whenever an extension exists, we thus provide sound methods for computing the intersection of all extensions for an important subset of Reiter’s default theories.
Original languageEnglish
Pages (from-to)339-356
Number of pages18
JournalLOGICS IN AI
Volume633
Issue numberNA
DOIs
Publication statusPublished - 1 Jan 1992

Keywords

  • Well founded semantics
  • Well-founded semantics with explicit negation
  • Computational properties
  • Default theory
  • Extended logic
  • Logic program semantics
  • Logic programs
  • Program semantics
  • Computer circuits
  • Semantics
  • Logic programming
  • Computation theory

Fingerprint Dive into the research topics of 'Default theory for well founded semantics with explicit negation'. Together they form a unique fingerprint.

  • Cite this