Title: The hypothetical semantics of logic programs
Abstract: Logic programming and deductive databases are important tools for building practical knowledge-based systems. Much of the expressive power of these systems stems from a simple nonmonotonic device, negation as failure.
Negation as failure allows a deductive system to conclude the negation of a fact if it cannot find a proof for it. Even though this procedural intuition is rather simple, a satisfactory declarative semantics for logic programs with negation as failure has not been completely established.
Many proposals for defining the meaning of logic programs with negation have been introduced in the literature. Some of these approaches successfully capture different patterns of reasoning associated with negation as failure. While these semantics are strongly related, they lack a unified framework and have often been found unintuitive.
In this work, we introduce a unified and intuitive view of logic programming semantics using hypothetical reasoning. This framework brings together the main approaches to logic programming semantics and allows us to discover interesting new semantical classes.
In this framework, negated literals are seen as assumptions. Every reasoner can then assume a set of assumptions. We call such sets hypotheses. Obviously, not all hypotheses are equally reasonable for a given program. The main contribution of this dissertation is the establishment of criteria to pick such reasonable hypotheses.
We establish two main criteria for choosing preferred hypotheses. These criteria differ in simplicity and expressive power. We use each of these criteria in two distinct ways to capture skeptical and credulous/nondeterministic reasoning. Finally, for each of the four basic classes, we study subclasses of hypotheses that can be constructed incrementally. While these classes are restricted in expressiveness, they often offer computational benefits.
We also introduce a graph-theoretic representation of logic programs based on the hypothetical metaphor. We show that many of our semantical classes correspond to specific structures in the graph. We use known results about these combinatorial structures to get insights into many important problems in logic programming, such as the existence, uniqueness and totality of certain semantics.
Publication Year: 1994
Publication Date: 1994-01-01
Language: en
Type: article
Access and Citation
Cited By Count: 3
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot