Modeling generalized implicatures using non-monotonic logics

This paper reports on an approach to model generalized implicatures using nonmonotonic logics. The approach, called compositional, is based on the idea of compositional semantics, where the implicatures carried by a sentence are constructed from the implicatures carried by its constituents, but it also includes some aspects nonmonotonic logics in order to model the defeasibility of generalized implicatures.     

Studying properties of classes of default logics

The study of different variants of default logic reveals not only differences but also properties they share. For example, there seems to be a close relationship between semi-monotonicity and the guaranteed existence of extensions. Likewise, formula-manipulating default logics tend to violate the property of cumulativity. The problem is that currently such properties must be established separately for each approach. This paper describes some steps towards the study of properties of classes of default logics by giving a rather general definition of what a default logic is. Essentially our approach is operational and restricts attention to purely formula-manipulating logics. We motivate our definition and demonstrate that it includes a variety of well-known default logics. Furthermore, we derive general results regarding the concepts of semi-monotonicity and cumulativity. As a benefit of the discussion we uncover that some design decisions of concrete default logics were not accidental as they may seem, but rather they were due to objective necessities.     

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.     

Uniform semantic treatment of default and autoepistemic logics

We revisit the issue of epistemological and semantic foundations for autoepistemic and default logics, two leading formalisms in nonmonotonic reasoning. We develop a general semantic approach to autoepistemic and default logics that is based on the notion of a belief pair and that exploits the lattice structure of the collection of all belief pairs. For each logic, we introduce a monotone operator on the lattice of belief pairs. We then show that a whole family of semantics can be defined in a systematic and principled way in terms of fixpoints of this operator (or as fixpoints of certain closely related operators). Our approach elucidates fundamental constructive principles in which agents form their belief sets, and leads to approximation semantics for autoepistemic and default logics. It also allows us to establish a precise one-to-one correspondence between the family of semantics for default logic and the family of semantics for autoepistemic logic. The correspondence exploits the modal interpretation of a default proposed by Konolige. Our results establish conclusively that default logic can be viewed as a fragment of autoepistemic logic, a result that has been long anticipated. At the same time, they explain the source of the difficulty to formally relate the semantics of default extensions by Reiter and autoepistemic expansions by Moore. These two semantics occupy different locations in the corresponding families of semantics for default and autoepistemic logics.     

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.     

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.     

A proof procedure for normal default theories

Recent research by Delgrande [6] and Geffner and Pearl [10] suggests two different semantic interpretations for normal defaults with one single representation as conditional sentences. However, they both need additional formal mechanisms for handling irrelevant information when their approaches are applied to formalising default reasoning. Delgrande in [5, 6] suggests two meta-strategies which he considers to be adequately strong to handle the orderings of defaults, and he claims they are equivalent. Furthermore, each of Delgrande's strategies is defined in terms of all sentences of the object language. In this paper, we shall prove that Delgrande's claim that his meta-strategies are equivalent is incorrect and that one of his meta-strategies can be reformulated within the framework of First Order Predicate Calculus (FOPC) and without having to consider every sentence of the object language. One advantage of such a reformalisation is its computational simplicity: to give an extension of a default theory there is only a need to consider those sentences which occur in the default theory under consideration rather than every sentence in the object language; furthermore, to provide a proof procedure for Delgrande's system as based on the meta-strategy we have formalised, one need only employ a FOPC proof procedure, rather than a conditional one.     

Graph theoretical structures in logic programs and default theories

In this paper we present a graph representation of logic programs and default theories. We show that many of the semantics proposed for logic programs with negation can be expressed in terms of notions emerging from graph theory, establishing in this way a link between the fields. Namely the stable models, the partial stable models, and the well-founded semantics correspond respectively to the kernels, semikernels and the initial acyclic part of an associated graph. This link allows us to consider both theoretical (existence, uniqueness) and computational problems (tractability, algorithms, approximations) from a more abstract and rather combinatorial point of view. It also provides a clear and intuitive understanding about how conflicts between rules are resolved within the different semantics. Furthermore, we extend the basic framework developed for logic programs to the case of Default Logic by introducing the notions of partial, deterministic and well-founded extensions for default theories. These semantics capture different ways of reasoning with a default theory.     

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.     

A new methodology for query answering in default logics via structure-oriented theorem proving

We present a new approach to query answering in default logics. The basic idea is to treat default rules as classical implications along with some qualifying conditions restricting the use of such rules while query answering. We accomplish this by taking advantage of the conception of structure-oriented theorem proving provided by Bibel's connection method. We show that the structure-sensitive nature of the connection method allows for an elegant characterization of proofs in default logic. After introducing our basic method for query answering in default logics, we present a corresponding algorithm and describe its implementation. Both the algorithm and its implementation are obtained by slightly modifying an existing algorithm and an existing implementation of the standard connection method. In turn, we give a couple of refinements of the basic method that lead to conceptually different algorithms. The approach turns out to be extraordinarily qualified for implementations by means of existing automated theorem proving techniques. We substantiate this claim by presenting implementations of the various algorithms along with some experimental analysis.Even though our method has a general nature, we introduce it in the first part of this paper with the example of constrained default logic. This default logic is tantamount to a variant due to Brewka, and it coincides with Reiter's default logic and a variant due to ukaszewicz on a large fragment of default logic. Accordingly, our exposition applies to these instances of default logic without any modifications.     

Sequent calculi for skeptical reasoning in predicate default logic and other nonmonotonic logics

Sequent calculi for skeptical consequence in predicate default logic, predicate stable model logic programming, and infinite autoepistemic theories are presented and proved sound and complete. While skeptical consequence is decidable in the finite propositional case of all three formalisms, the move to predicate or infinite theories increases the complexity of skeptical reasoning to being ₁¹-complete. This implies the need for sequent rules with countably many premises, and such rules are employed. AMS subject classification 03B42, 68N17, 68T27This paper grew directly out of the authors dissertation, written under the direction of Anil Nerode.     

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.     

A survey of non-monotonic reasoning

Classical logic is purely deductive by nature. This has a certain monotonicity as consequence: If a proposition is deducible from a set of premises, this statement is still deducible if we enlarge this set of premises. So new information can never invalidate old information. On the other hand, common-sense reasoning must be inductive in some way: Since we seldom know all the relevant information, we have to make assumptions which seem plausible at that moment, yet which may turn out to be wrong in the light of new information. Therefore, common-sense reasoning is non-monotonic. However, traditional logic is insufficient to handle such a reasoning pattern. If you increase your set of premises with new information, this set may become inconsistent, so the reasoning based on classical logic alone will simply reduce to triviality, and consequently anything will be deducible.Non-monotonic reasoning originated in the field of artificial intelligence, and has become a rapidly growing area in the last decade. This paper discusses two of the most prominent formalizations of common-sense reasoning. No prior knowledge of formal logic is required.     

Verification of non-monotonic knowledge bases

Non-monotonic Knowledge-Based Systems (KBSs) must undergo quality assurance procedures for the following two reasons: (i) belief revision (if such is provided) cannot always guarantee the structural correctness of the knowledge base, and in certain cases may introduce new semantic errors in the revised theory; (ii) non-monotonic theories may have multiple extensions, and some types of functional errors which do not violate structural properties of a given extension are hard to detect without testing the overall performance of the KBS. This paper presents an extension of the distributed verification method, which is meant to reveal structural and functional anomalies in non-monotonic KBSs. Two classes of anomalies are considered: (i) structural anomalies which manifest themselves within a given extension (such as logical inconsistencies, structural incompleteness, and intractabilities caused by circular rule chains), and (ii) functional anomalies related to the overall performance of the KBS (such as the existence of complementary rules and some types of rule subsumptions). The corresponding verification tests are presented and illustrated on an extended example.     

Justification logics, logics of knowledge, and conservativity

Several justification logics have been created, starting with the logic LP, (Artemov, Bull Symbolic Logic 7(1):1–36, 2001). These can be thought of as explicit versions of modal logics, or of logics of knowledge or belief, in which the unanalyzed necessity (knowledge, belief) operator has been replaced with a family of explicit justification terms. We begin by sketching the basics of justification logics and their relations with modal logics. Then we move to new material. Modal logics come in various strengths. For their corresponding justification logics, differing strength is reflected in different vocabularies. What we show here is that for justification logics corresponding to modal logics extending T, various familiar extensions are actually conservative with respect to each other. Our method of proof is very simple, and general enough to handle several justification logics not directly corresponding to distinct modal logics. Our methods do not, however, allow us to prove comparable results for justification logics corresponding to modal logics that do not extend T. That is, we are able to handle explicit logics of knowledge, but not explicit logics of belief. This remains open.     

Combining and automating classical and non-classical logics in classical higher-order logics

Numerous classical and non-classical logics can be elegantly embedded in Church??s simple type theory, also known as classical higher-order logic. Examples include propositional and quantified multimodal logics, intuitionistic logics, logics for security, and logics for spatial reasoning. Furthermore, simple type theory is sufficiently expressive to model combinations of embedded logics and it has a well understood semantics. Off-the-shelf reasoning systems for simple type theory exist that can be uniformly employed for reasoning within and about embedded logics and logics combinations. In this article we focus on combinations of (quantified) epistemic and doxastic logics and study their application for modeling and automating the reasoning of rational agents. We present illustrating example problems and report on experiments with off-the-shelf higher-order automated theorem provers.