# The well-founded semantics for general logic programs

@article{Gelder1991TheWS, title={The well-founded semantics for general logic programs}, author={Allen Van Gelder and Kenneth A. Ross and John S. Schlipf}, journal={J. ACM}, year={1991}, volume={38}, pages={620-650} }

A general logic program (abbreviated to "program" hereafter) is a set of roles that have both positive and negative subgoals. It is common to view a deductive database as a general logic program consisting of rules (IDB) slttmg above elementary relations (EDB, facts). It is desirable to associate one Herbrand model with a program and think of that model as the "meaning of the program, " or Its "declarative semantics. " Ideally, queries directed to the program would be answered in accordance… Expand

#### 1,923 Citations

QUASI-STABLE SEMANTICS OF LOGIC PROGRAMS

- 1998

1. Introduction The semantics of logic programming and deductive databases has been extensively studied in the past two decades. Many semantic theories have been proposed (see 3] for a survey). In… Expand

Computing the Well-Founded Model of Deductive Databases

- Mathematics, Computer Science
- Int. J. Uncertain. Fuzziness Knowl. Based Syst.
- 1996

This work presents a method for constructing the well-founded model for general deductive databases, which are logic programs without any function symbols, which adopts paraconsistent relations as the semantic objects associated with the predicate symbols of the database. Expand

Logical Foundations of Well-Founded Semantics

- Computer Science
- KR
- 2006

This work identifies the HT2 frames previously proposed by Cabalar to capture WFS as structures of a kind used by Dosen to characterise a family of logics weaker than intuitionistic and minimal logic, and proposes the resulting partial equilibrium logic as a logical foundation for well-founded semantics. Expand

Safe computation of the well-founded semantics of Datalog queries

- Computer Science
- Inf. Syst.
- 1992

A method for the evaluation of the well-founded semantics of Datalog queries that allows us to construct answers without having to compute the whole greatest unfounded set, the Greatest Useful Unfounded Set (GUUS), from which the choice of the name GUUS method is chosen. Expand

Reconciling Well-Founded Semantics of DL-Programs and Aggregate Programs

- Computer Science
- ICLP
- 2012

The main result is that, under a satisfaction-preserving mapping from dl-atoms to aggregates, the well-founded semantics ofdl-programs by Eiter et al., coincides with the well the founded semantics of aggregate programs, defined by Pelov et al. as the least fixpoint of a 3-valued immediate consequence operator under the ultimate approximating aggregate. Expand

Towards Constraint Satisfaction through Logic Programs and the Stable Model Semantics

- Mathematics
- 1997

Logic programs with the stable model semantics can be thought of as a new paradigm for constraint satisfaction, where the rules of a program are seen as constraints on the stable models. In this work… Expand

Unfounded Sets and Well-Founded Semantics of Answer Set Programs with Aggregates

- Mathematics, Computer Science
- J. Artif. Intell. Res.
- 2011

A formal proof of tractable computation of the well-founded model for LPm,aA programs is given, and it is proved that for general LPA programs, which may contain aggregates that are neither monotone nor antimonotone, deciding satisfaction of aggregate expressions with respect to partial interpretations is coNP-complete. Expand

Computation of Stable Models and Its Integration with Logical Query Processing

- Computer Science
- IEEE Trans. Knowl. Data Eng.
- 1996

An efficient implementation of goal-oriented effective query evaluation under the well-founded semantics that produces a residual program for subgoals that are relevant to a query, which contains facts for true instances and clauses with body literals for undefined instances. Expand

A logic programming system for nonmonotonic reasoning

- Mathematics, Computer Science
- Journal of Automated Reasoning
- 2004

This paper presents and exploits a SLDNF-like derivation procedure, SLX, for programs with explicit negation under well-founded semantics (WFSX) and proves its soundness and completeness and introduces a paraconsistent version of WFSX that allows contradictions and for which the SLX top-down procedure is proven correct as well. Expand

Simplifying A Logic Program Using Its Consequences

- Computer Science
- IJCAI
- 2015

This paper provides two main notions, strong reliability set and weak reliable set, and shows that a DLP is strongly equivalent to the simplified program if and only if the consequence is a strong reliable set. Expand

#### References

SHOWING 1-10 OF 68 REFERENCES

Unfounded sets and well-founded semantics for general logic programs

- Mathematics, Computer Science
- PODS '88
- 1988

It is shown that a program has a unique stable model if it has a well-founded model, in which case they are the same, and the converse is not true. Expand

On the Declarative Semantics of Logic Programs with Negation

- Computer Science, Mathematics
- Foundations of Deductive Databases and Logic Programming.
- 1988

The concept of circumscription is extended to extend the minimal model approach to stratified programs and show that it leads to the same semantics as the fixed point approach. Expand

A Kripke-Kleene Semantics for Logic Programs

- Computer Science, Mathematics
- J. Log. Program.
- 1985

The use of conventional classical logic is misleading for characterizing the behavior of logic programs because a logic program, when queried, will do one of three things: succeed with the query,… Expand

Negation as failure using tight derivations for general logic programs

- Mathematics
- 1989

A general logic program is a set of rules that have both positive and negative subgoals. We define negation in general logic programs as finite failure, but we limit proof attempts to tight… Expand

Towards a Theory of Declarative Knowledge

- Computer Science, Mathematics
- Foundations of Deductive Databases and Logic Programming.
- 1988

This work proves the consistency of Clark's completion for stratified programs and attempts to clarify the sources of some previously reported difficulties with negation in logic programming. Expand

On the Declarative Semantics of Deductive Databases and Logic Programs

- Mathematics, Computer Science
- Foundations of Deductive Databases and Logic Programming.
- 1988

The class of perfect models of a deductive database is introduced and it is argued that this class of models provides a correct intended semantics for such databases, incorporating a natural form of the closed-world assumption. Expand

Making Prolog more Expressive

- Computer Science
- J. Log. Program.
- 1984

It is shown how the increased expressibility of extended programs and goals can be easily implemented in any PROLOG system which has a sound implementation of the negation as failure rule and SLDNF-resolution. Expand

The alternating fixpoint of logic programs with negation

- Mathematics, Computer Science
- PODS '89
- 1989

It is shown that a system is fixpoint Logic, which permits rule bodies to be first order formulas but requires inductive relations to be positive within them, can be transformed straightforwardly into a normal logic program whose alternating fixpoint partial model corresponds to the least fixpoint of the fixpoint logic system. Expand

Modeling Simultaneous Events with Default Reasoning and Tight Derivations

- Mathematics, Computer Science
- J. Log. Program.
- 1990

Abstract This report describes how an arbitrator for the game of Diplomacy was implemented in PROLOG, and discusses the advantages of logic programming for this type of problem. The design of the… Expand

A procedural semantics for well founded negation in logic programs

- Computer Science
- PODS '89
- 1989

It is proved that global SLS-resolution is sound with respect to the well-founded semantics, and complete for non-floundering queries. Expand