Well-founded semantics

Well-founded semantics

The well-founded semantics is a three-valued version of the stable semantics. That is, instead of only assigning propositions "true" or "false", it also allows for a value representing ignorance. For example, if we know that

Specimen A is a moth if specimen A does not fly during daylight.

but we do not know whether or not specimen "A" flies during the day, the well-founded semantics would assign the proposition ``specimen A is a moth`` the value "bottom" which is neither "true" nor "false".

The well-founded semantics is also a way of making safe inferences in the presence of contradictory data such as noisy data, or data acquired from different experts who may posit differing opinions. Many two-valued semantics simply won't consider such a problem state workable. The well-founded semantics, however, has a built-in mechanism to circumvent the presence of the contradictions and proceeds in the best way that it can. The fastest known algorithm to compute the WF-Semantics in general, is of quadratic complexity.

References

* A. Van Gelder, K.A. Ross and J.S. Schlipf. "The Well-Founded Semantics for General Logic Programs". Journal of the ACM 38(3) pp. 620--650, 1991


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Non-well-founded set theory — Non well founded set theories are variants of axiomatic set theory which allow sets to contain themselves and otherwise violate the rule of well foundedness. In non well founded set theories, the foundation axiom of ZFC is replaced by axioms… …   Wikipedia

  • Stable model semantics — The concept of a stable model, or answer set, is used to define a declarative semantics for logic programs with negation as failure. This is one of several standard approaches to the meaning of negation in logic programming, along with program… …   Wikipedia

  • Kripke semantics — (also known as relational semantics or frame semantics, and often confused with possible world semantics) is a formal semantics for non classical logic systems created in the late 1950s and early 1960s by Saul Kripke. It was first made for modal… …   Wikipedia

  • Situation semantics — is an alternative to possible world semantics developed by Jon Barwise and John Perry in the early eighties. Situations, unlike worlds, are not complete in the sense that every proposition or its negation holds in a world. According to situation… …   Wikipedia

  • Abductive logic programming — is a high level knowledge representation framework that can be used to solve problems declaratively based on abductive reasoning. It extends normal Logic Programming by allowing some predicates to be incompletely defined, declared as abducible… …   Wikipedia

  • Datalog — is a query and rule language for deductive databases that syntactically is a subset of Prolog. Its origins date back to the beginning of logic programming, but it became prominent as a separate area around 1977 when Hervé Gallaire and Jack Minker …   Wikipedia

  • WFS — The acronym WFS can stand for: *Wavefield synthesis *Web Feature Service *Well founded semantics *Wilmington Friends School *Windows Fax and Scan *Women For Sobriety *World Future Society …   Wikipedia

  • Mereology — In philosophy and mathematical logic, mereology (from the Greek μέρος, root: μερε(σ) , part and the suffix logy study, discussion, science ) treats parts and the wholes they form. Whereas set theory is founded on the membership relation between a …   Wikipedia

  • Philosophy — For other uses, see Philosophy (disambiguation) …   Wikipedia

  • Philosophy of mathematics — The philosophy of mathematics is the branch of philosophy that studies the philosophical assumptions, foundations, and implications of mathematics. The aim of the philosophy of mathematics is to provide an account of the nature and methodology of …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”