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.     

The dynamics of default reasoning

In this paper we study default reasoning from a dynamic, agent-oriented, semantics-based point of view. In a formal framework used to specify and to reason about rational agents, we introduce actions that model the (attempted) jumping to conclusions that is a fundamental part of reasoning by default. Application of such an action consists of three parts. First it is checked whether the formula that the agent tries to jump to is a default, thereafter it is checked whether the default formula can consistently be incorporated by the agent, and if this is the case the formula is included in the agent's beliefs. As for all actions in our framework, we define the ability and opportunity of agents to apply these actions, and the states of affairs following application. To formalise formulae being defaults, we introduce the modality of common possibility. This modality is related to, but not reducible to, the notions of common knowledge and ‘everybody knows’-knowledge. To model the qualitative difference that exists between hard, factual knowledge and beliefs derived by default, we employ different modalities to represent these concepts, thus combining knowledge, beliefs, and defaults in one framework. Based on the concepts used to model the default reasoning of agents, we look into the dynamics of the supernormal fragment of default logic. We show in particular that by sequences of jumps to conclusions agents can end up with extensions in the sense of default logic of their belief.     

Yet some more complexity results for default logic

We identify several new tractable subsets and several new intractable simple cases for reasoning in the propositional version of Reiter's default logic. The majority of our findings are related to brave reasoning. By making some intuitive observations, most classes that we identify can be derived quite easily from some subsets of default logic already known in the literature. Some of the subsets we discuss are subclasses of the so-called “extended logic programs”. All the tractable subsets presented in this paper can be recognized in linear time.     

On the complexity of extension checking in default logic

The complexity of deciding equivalence of a formula to an extension of a default theory is investigated for the Reiter, justified, constrained, and rational semantics.     

缺省理论与相信理论的关系

本文在相信逻辑中引入相信解释与相信模的概念，从语义上把相信逻辑改造成非单调逻辑。一个缺省理论可以直接转换成一个相信逻辑理论，本文中证明了一个缺省理论外延的模集就是对应相信理论的模，从而为缺省理论提供了一种简便的语义。     

Abstract argumentation systems

In this paper, we develop a theory of abstract argumentation systems. An abstract argumentation system is a collection of “defeasible proofs”, called arguments, that is partially ordered by a relation expressing the difference in conclusive force. The prefix “abstract” indicates that the theory is concerned neither with a specification of the underlying language, nor with the development of a subtheory that explains the partial order. An unstructured language, without logical connectives such as negation, makes arguments not (pairwise) inconsistent, but (groupwise) incompatible. Incompatibility and difference in conclusive force cause defeat among arguments. The aim of the theory is to find out which arguments eventually emerge undefeated. These arguments are considered to be in force. Several results are established. The main result is that arguments that are in force are precisely those that are in the limit of a so-called complete argumentation sequence.     

RFuzzy: Syntax, semantics and implementation details of a simple and expressive fuzzy tool over Prolog

We present the RFuzzy framework, a Prolog-based tool for representing and reasoning with fuzzy information. The advantages of our framework in comparison to previous tools along this line of research are its easy, user-friendly syntax, and its expressivity through the availability of default values and types.In this approach we describe the formal syntax, the operational semantics and the declarative semantics of RFuzzy (based on a lattice). A least model semantics, a least fixpoint semantics and an operational semantics are introduced and their equivalence is proven. We provide a real implementation that is free and available. (It can be downloaded from http://babel.ls.fi.upm.es/software/rfuzzy/.) Besides implementation details, we also discuss some actual applications using RFuzzy.     

利用格论研究缺省推理

本文提出了一组转换规则,使用这组转换规则可以把缺省规则转换成扩展规则,然后使用这些扩展规则去扩展缺省理论的初始逻辑公式集合,在这些扩展规则的基础上,我们提出了缺省格(default lattice)的概念,证明了缺省理论的外延刚好对应于它的缺省格的相容性集合的D-极大值,因此可以使用缺省格求出缺省理论的所有外延.     

非单调推理的研究现状

一、引言 早在1959年,McCart~[1]就发现常识和常识推理很难处理,因为在常识推理中当前得出的结论,可能会由于以后新事实的加入而被取消.这就是所谓的“非单调性”。     

A Note on the Refinement of Nonmonotonic Knowledge Bases

Refinement of logical theories plays an important role in various application domains, notably in software engineering. This note introduces and studies refinement notions for nonmonotonic knowledge bases in default logic. The paper motivates and proposes refinement concepts, discusses their relationship, and establishes sufficient conditions for refinement. Received 27 July 1999 / Revised 3 November 1999 / Accepted 24 May 2000     

Semantic forgetting in answer set programming

The notion of forgetting, also known as variable elimination, has been investigated extensively in the context of classical logic, but less so in (nonmonotonic) logic programming and nonmonotonic reasoning. The few approaches that exist are based on syntactic modifications of a program at hand. In this paper, we establish a declarative theory of forgetting for disjunctive logic programs under answer set semantics that is fully based on semantic grounds. The suitability of this theory is justified by a number of desirable properties. In particular, one of our results shows that our notion of forgetting can be entirely captured by classical forgetting. We present several algorithms for computing a representation of the result of forgetting, and provide a characterization of the computational complexity of reasoning from a logic program under forgetting. As applications of our approach, we present a fairly general framework for resolving conflicts in inconsistent knowledge bases that are represented by disjunctive logic programs, and we show how the semantics of inheritance logic programs and update logic programs from the literature can be characterized through forgetting. The basic idea of the conflict resolution framework is to weaken the preferences of each agent by forgetting certain knowledge that causes inconsistency. In particular, we show how to use the notion of forgetting to provide an elegant solution for preference elicitation in disjunctive logic programming.     

Choosing reference classes and building provisional models

A well-known problem in default logic is the ability of naive reasoners to explain bothg and ¬g from a set of observations. This problem is treated in at least two different ways within that camp.One approach is examination of the various explanations and choosing among them on the basis of various explanation comparators. A typical comparator is choosing the explanation that depends on the most specific observation, similar to the notion of narrowest reference class.Others examine default extensions of the observations and choose whatever is true in any extension, or what is true in all extensions or what is true in preferred extensions. Default extensions are sometimes thought of as acceptable models of the world that are discarded as more knowledge becomes available.We argue that the notions of specificity and extension lack clear semantics. Furthermore, we show that the problems these ideas were supposed to solve can be handled easily within a probabilistic framework.     

An Interpretation of Default Logic in Minimal Temporal Epistemic Logic

When reasoning about complex domains, where information available is usually only partial, nonmonotonic reasoning can be an important tool. One of the formalisms introduced in this area is Reiter's Default Logic (1980). A characteristic of this formalism is that the applicability of default (inference) rules can only be verified in the future of the reasoning process. We describe an interpretation of default logic in temporal epistemic logic which makes this characteristic explicit. It is shown that this interpretation yields a semantics for default logic based on temporal epistemic models. A comparison between the various semantics for default logic will show the differences and similarities of these approaches and ours.     

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.     

Time-evolving rule-based knowledge bases

Human knowledge in any expertise area changes with respect to time. Two types of such knowledge can be identified, time independent and time dependent. It is shown that the maintenance effort of the latter is harder than that of the former. The present paper applies research results in the area of temporal databases, in order to maintain a rule-based knowledge base whose content changes with respect to the real world time. It is shown that the approach simplifies the maintenance of time dependent knowledge. It also enables the study of the evolution of knowledge with respect to time, which is knowledge on its own. Three distinct solutions are actually proposed and evaluated. Their common characteristic is that knowledge is stored in a database; therefore, all the advantages of databases are inherited by knowledge bases. Implementations are also reported.