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

Fingerprint

Well-founded Semantics
Logic Programs
Fertilization
Fixpoint
Bottom-up
Modularity
Monotonic
Semantics
Uniqueness
Intersection

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

Cite this

@article{eb36356daca744d2937cf9e78620b298,
title = "Default theory for well founded semantics with explicit negation",
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.",
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",
author = "Pereira, {Lu{\'i}s Manuel Sancho Moniz} and Alferes, {Jos{\'e} J{\'u}lio Alves}",
year = "1992",
month = "1",
day = "1",
doi = "10.1007/BFb0023437",
language = "English",
volume = "633",
pages = "339--356",
journal = "LOGICS IN AI",
number = "NA",

}

Default theory for well founded semantics with explicit negation. / Pereira, Luís Manuel Sancho Moniz; Alferes, José Júlio Alves.

In: LOGICS IN AI, Vol. 633, No. NA, 01.01.1992, p. 339-356.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Default theory for well founded semantics with explicit negation

AU - Pereira, Luís Manuel Sancho Moniz

AU - Alferes, José Júlio Alves

PY - 1992/1/1

Y1 - 1992/1/1

N2 - 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.

AB - 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.

KW - Well founded semantics

KW - Well-founded semantics with explicit negation

KW - Computational properties

KW - Default theory

KW - Extended logic

KW - Logic program semantics

KW - Logic programs

KW - Program semantics

KW - Computer circuits

KW - Semantics

KW - Logic programming

KW - Computation theory

UR - http://www.scopus.com/record/display.uri?eid=2-s2.0-84990617292&origin=resultslist&sort=plf-f&src=s&st1

U2 - 10.1007/BFb0023437

DO - 10.1007/BFb0023437

M3 - Article

VL - 633

SP - 339

EP - 356

JO - LOGICS IN AI

JF - LOGICS IN AI

IS - NA

ER -