Making default inferences from logic programs

The relationship between Reiter's default logic and general logic programs, which may contain negative subgoals in rule bodies, has been discussed in the literature by translating logic programs to default logic theories. Here, we present a method to translate some default logic theories to general logic programs, and study the extensions of default logic theories with the stable model semantics of logic programming. Based on the translation method, we show that another semantics of logic programming, the well-founded semantics, can be used to define a new version of default logic, which is more cautious than the original one. This enables the existing proof procedures for the well-founded semantics to perform default inference. We also study the property of cumulative monotonicity for both default logic theories and general logic programs under the two different semantics. As a direct application of the translation method, logic programs can be used to make default inference for semantic networks with exceptions. La relation entre la logique par défaut de Reiter et les programmes logiques généraux, qui peuvent comporter des sous-buts négatifs dans les ensembles de règies, a déjàété discutée en traduisant les programmes logiques en théories de la logique par défaut. Dans cet article, les auteurs proposent une méthode pour traduire certaines théories de la logique par defaut en programmes logiques généraux et étudient les extensions des theories de la logique par defaut avec la sémantique de modéle stable de la programmation logique. En se basant sur la méthode de traduction, les auteurs démontrent qu'une autre sémantique de la programmation logique, la sémantique bien fondée, peut ětre utilisée pour définir une nouvelle version de la logique par défaut, qui est plus prudente que la première. Cela permet aux procédures de preuve existantes de la sémantique bien fondée d' effectuer l' inférence par défaut. Les auteurs examinent également les caracteristiques de la monotonicité cumulative pour les theories de la logique par défaut et les programmes logiques généraux selon les deux différentes sémantiques. Une application directe de la méthode de traduction est la possibilityé d' utiliser les programmes logiques pour effectuer de l' inférence par défaut pour les réseaux sémantiques avec exceptions.     

Specifying causality in action theories: a default logic approach

Recent research on reasoning about action has shown that the traditional logic form of domain constraints is problematic to represent ramifications of actions that are related to causality of domains. To handle this problem properly, as proposed by some researchers, it is necessary to describe causal relations of domains explicitly in action theories. In this paper, we address this problem from a new point of view. Specifically, unlike other researchers viewing causal relations as some kind of inference rules, we distinguish causal relations between defeasible and non-defeasible cases. It turns out that a causal theory in our formalism can be specified by using Reiter's default logic. Based on this idea, we propose a causality-based minimal change approach for representing effects of actions, and argue that our approach provides more plausible solutions for the ramification and qualification problems compared with other related work. We also describe a logic programming approximation to compute causal theories of actions which provides an implementational basis for our approach.     

Stable and extension class theory for logic programs and default logics

The stable model semantics (cf. Gelfond and Lifschitz [1]) for logic programs suffers from the problem that programs may not always have stable models. Likewise, default theories suffer from the problem that they do not always have extensions. In such cases, both these formalisms for non-monotonic reasoning have an inadequate semantics. In this paper, we propose a novel idea-that of extension classes for default logics, and of stable classes for logic programs. It is shown that the extension class and stable class semantics extend the extension and stable model semantics respectively. This allows us to reason about inconsistent default theories, and about logic programs with inconsistent completions. Our work extends the results of Marek and Truszczynski [2] relating logic programming and default logics.     

General default logic

In this paper, we propose a new nonmonotonic logic called general default logic. On the one hand, it generalizes Reiter’s default logic by adding to it rule-like operators used in logic programming. On the other hand, it extends logic programming by allowing arbitrary propositional formulas. We show that with this new logic, one can formalize naturally rule constraints, generalized closed world assumptions, and conditional defaults. We show that under a notion of strong equivalence, sentences of this new logic can be converted to a normal form. We also investigate the computational complexity of various reasoning tasks in the logic, and relate it to some other nonmonotonic formalisms such as Lin and Shoham’s logic of GK and Moore’s autoepistemic logic.     

Similarity preservation in default logic

The paper identifies a problem in default reasoning in Reiter’s Default Logic and related systems: elements which are similar given the axioms only, become distinguishable in extensions. We explain why, sometimes, this is considered undesirable. Two approaches are presented for guaranteeing similarity preservation: One approach formalizes a way of uniformly applying the defaults to all similar elements by introducing generic extensions, which depend only on similarity types of objects. According to the second approach, for a restricted class of default theories, a default theory is viewed as a “shorthand notation” to what is “really meant” by its formulation. In this approach we propose a rewriting of defaults in a form that guarantees similarity preservation of the modified theory. It turns out that the above two approaches yield the same result. This revised version was published online in June 2006 with corrections to the Cover Date.     

Regular disjunction-free default theories

In this paper, the class of regular disjunction-free default theories is introduced and investigated.A transformation from regular default theories to normal default theories is established. The initial theory andthe transformed theory have the same extensions when restricted to old variables. Hence, regular default theoriesenjoy some similar properties (e.g., existence of extensions, semi-monotonicity) as normal default theories. Then,a new algorithm for credulous reasoning of regular theories is developed. This algorithm runs in a time not morethan 0(1.45~n), where n is the number of defaults. In case of regular prerequisite-free or semi-2CNF defaulttheories, the credulous reasoning can be solved in polynomial time. However, credulous reasoning for semi-Horndefault theories is shown to be NP-complete although it is tractable for Horn default theories. Moreover, skepticalreasoning for regular unary default theories is co-NP-complete.     

Seminormal stratified default theories

In this paper we study seminormal default theories. The notions of stratification and strong stratification are introduced. The properties of stratified and strongly stratified default theories are investigated. We show how to determine if a given seminormal default theory is strongly stratified and how to find the finest partition into strata. We present algorithms for computing extensions for stratified seminormal default theories and analyze their complexity.     

New proofs in default logic theory

The proofs of theorems in default logic are often quite complicated and therefore error-prone. In this paper we introduce an operational interpretation of default logic and show its usefulness in providing technically simpler proofs for well-known results. We especially turn our attention to ordered, semi-normal default theories. We point out that Etherington's result and most of the citations and improvements in the literature are wrong, give the correct version and a totally new, technically clearer and more comprehensive proof.     

An argumentation framework in default logic

This article presents a formal theory about nontrivial reasoning with inconsistent information, applicable, among other things, to defeasible reasoning. The theory, which is inspired by a formal analysis of legal argument, is based on the idea that inconsistency tolerant reasoning is more than revising an unstructural set of premises; rather it should be regarded as constructing and comparing arguments for incompatible conclusions. This point of view gives rise to two important observations, both pointing at some flaws of other theories. The first is that arguments should be compared as they are constructed, viz. step-by-step, while the second observation is that a knowledge representation language is needed with a defeasible conditional, since the material implication gives rise to arguments which are not constructed in actual reasoning. Accordingly, a nonmonotonic logic, default logic, is chosen as the formalism underlying the argumentation framework. The general structure of the framework allows for any standard for comparing pairs of arguments; in this study two such standards are investigated, based on specificity and on orderings of the premises.     

On embedding default logic into Moore''s autoepistemic logic

Recently Gottlob proved [2] that there does not exist a faithful modular translation of default logic into autoepistemic logic, and presented a non-modular translation. Gottlob's translation, however, is indirect (it uses “nonmonotonic logic N” as an intermediate point), quite complex and exploits sophisticated encoding of proof theory in autoepistemic formulas. We provide a simpler and more intuitive (non-modular) direct translation. In addition, our argument is purely model-theoretic.     

Stratification for default logic variants

Default reasoning is computationally expensive. One of the most promising ways of easing this problem and developing powerful implementations is to split a default theory into smaller parts and compute extensions in a modular, “local” way. Up to now this idea was only followed for Reiter's default logic, yet it is also relevant to other variants of default logic which have found increasing recognition in the past years. This paper shows how it can be modified to work for several popular, alternative approaches of default reasoning: justified, constrained and rational default logic. This work defines the formal basis for a Web-based default reasoning system which is under development at our institution. © 1998 John Wiley & Sons, Inc.     

Alternative approaches to default logic

Reiter's default logic has proven to be an enduring and versatile approach to non-monotonic reasoning. Subsequent work in default logic has concentrated in two major areas. First, modifications have been developed to extend and augment the approach. Second, there has been ongoing interest in semantic foundations for default logic. In this paper, a number of variants of default logic are developed to address differing intuitions arising from the original and subsequent formulations. First, we modify the manner in which consistency is used in the definition of a default extension. The idea is that a global rather than local notion of consistency is employed in the formation of a default extension. Second, we argue that in some situations the requirement of proving the antecedent of a default is too strong. A second variant of default logic is developed where this requirement is dropped; subsequently these approaches are combined, leading to a final variant. These variants then lead to default systems which conform to alternative intuitions regarding default reasoning. For all of these approaches, a fixed-point and a pseudo-iterative definition are given; as well a semantic characterisation of these approaches is provided. In the combined approach we argue also that one can now reason about a set of defaults and can determine, for example, if a particular default in a set is redundant. We show the relation of this work to that of ukaszewicz and Brewka, and to the Theorist system.     

Representation theory for default logic

Default logic can be regarded as a mechanism to represent families of belief sets of a reasoning agent. As such, it is inherently second-order. In this paper, we study the problem of representability of a family of theories as the set of extensions of a default theory. We give a complete solution to the problem of representability by means of default theories with finite set of defaults, and by means of normal default theories. We obtain partial results on representability by arbitrary (infinite, non-normal) default theories. We construct examples of denumerable families of non-including theories that are not representable. We also study the concept of equivalence between default theories. This revised version was published online in June 2006 with corrections to the Cover Date.     

Modal logic for default reasoning

In the paper we introduce a variant of autoepistemic logic that is especially suitable for expressing default reasonings. It is based on the notion of iterative expansion. We show a new way of translating default theories into the language of modal logic under which default extensions correspond exactly to iterative expansions. Iterative expansions have some attractive properties. They are more restrictive than autoepistemic expansions, and, for some classes of theories, than moderately grounded expansions. At the same time iterative expansions avoid several undesirable properties of strongly grounded expansions, for example, they are grounded in the whole set of the agent's initial assumptions and do not depend on their syntactic representation.Iterative expansions are defined syntactically. We define a semantics which leads to yet another notion of expansion — weak iterative expansion — and we show that there is an important class of theories, that we call -programs, for which iterative and weak iterative expansions coincide. Thus, for -programs, iterative expansions can be equivalently defined by semantic means.This work was partially supported by Army Research Office under grant DAAL03-89-K-0124, and by National Science Foundation and the Commonwealth of Kentucky EPSCoR program under grant RII 8610671.     

Some Results on Default Logic

In the previous paper,some important properties of extensions of general default theories were given.In order to further explore default logic,a characterization of extensions is presented.And a class of defaults,so-called Auto-compatible Default Theory,is also introduced.All these essentially develop the theories of Reiter and his followers.     

Ordered seminormal default theories and their extensions

Abstract

The concept of extension plays an important role in default logic. The notion of an ordered seminormal default theory has been introduced (Etherington 1987) to characterize a class of seminormal default theories which have extensions. However, the original definition has a drawback because of its dependence on specific representations of the default theory. We introduce the ‘canonical representation’ of a default theory and redefine the orderedness of a default theory based on its canonical representation. We show that under the new definition, the orderedness of a default theory Δ = (W,D) is intrinsic to the theory itself, independent of the specific representations of W and D. We present a modification of the algorithm in Etherington (1987) for computing extensions of a default theory. More importantly, we prove the conjecture (Etherington 1987) that a modified version of the algorithm in Etherington (1987) converges for general ordered, finite seminormal default theories, while the original algorithm was proven (Etherington 1987) to converge for ordered, finite network default theories which form a proper subset of the theories considered in this paper.     

Parallelism in logic programs

There is a tension between the objectives of avoiding irrelevant computation and extracting parallelism, in that a computational step used to restrict another must precede the latter. Our thesis, following [3], is that evaluation methods can be viewed as implementing a choice ofsideways information propagation graphs, or sips, which determines the set of goals and facts that must be evaluated. Two evaluation methods that implement the same sips can then be compared to see which obtains a greater degree of parallelism, and we provide a formal measure of parallelism to make this comparison.Using this measure, we prove that transforming a program using the Magic Templates algorithm and then evaluating the fixpoint bottom-up provides a most parallel implementation for a given choice of sips, without taking resource constraints into account. This result, taken in conjunction with earlier results from [3,27], which show that bottom-up evaluation performs no irrelevant computation and is sound and complete, suggests that a bottom-up approach to parallel evaluation of logic programs is very promising. A more careful analysis of the relative overheads in the top-down and bottom-up evaluation paradigms is needed, however, and we discuss some of the issues.The abstract model allows us to establish several results comparing other proposed parallel evaluation methods in the logic programming and deductive database literature, thereby showing some natural, and sometimes surprising, connections. We consider the limitations of the abstract model and of the proposed bottom-up evaluation method, including the inability of sips to describe certain evaluation methods, and the effect of resource constraints. Our results shed light on the limits of the sip paradigm of computation, which we extend in the process.     

Outlier detection for simple default theories

It was noted recently that the framework of default logics can be exploited for detecting outliers. Outliers are observations expressed by sets of literals that feature unexpected properties. These observations are not explicitly provided in input (as it happens with abduction) but, rather, they are hidden in the given knowledge base. Unfortunately, in the two related formalisms for specifying defaults — Reiter's default logic and extended disjunctive logic programs — the most general outlier detection problems turn out to lie at the third level of the polynomial hierarchy. In this note, we analyze the complexity of outlier detection for two very simple classes of default theories, namely NU and DNU, for which the entailment problem is solvable in polynomial time. We show that, for these classes, checking for the existence of an outlier is anyway intractable. This result contributes to further showing the inherent intractability of outlier detection in default reasoning.