Reasoning with Sets of Defaults in Default Logic

We present a general approach for representing and reasoning with sets of defaults in default logic, focusing on reasoning about preferences among sets of defaults. First, we consider how to control the application of a set of defaults so that either all apply (if possible) or none do (if not). From this, an approach to dealing with preferences among sets of default rules is developed. We begin with an ordered default theory , consisting of a standard default theory, but with possible preferences on sets of rules. This theory is transformed into a second, standard default theory wherein the preferences are respected. The approach differs from other work, in that we obtain standard default theories and do not rely on prioritized versions of default logic. In practical terms this means we can immediately use existing default logic theorem provers for an implementation. Also, we directly generate just those extensions containing the most preferred applied rules; in contrast, most previous approaches generate all extensions, then select the most preferred. In a major application of the approach, we show how semimonotonic default theories can be encoded so that reasoning can be carried out at the object level. With this, we can reason about default extensions from within the framework of a standard default logic. Hence one can encode notions such as skeptical and credulous conclusions, and can reason about such conclusions within a single extension.     

Priorities on defaults with prerequisites,and their application in treating specificity in terminological default logic

In a recent paper we have proposed terminological default logic as a formalism that combines means both for structured representation of classes and objects and for default inheritance of properties. The major drawback that terminological default logic inherits from general default logic is that it does not take precedence of more specific defaults over more general ones into account. This behavior has already been criticized in the general context of default logic, but it is all the more problematic in the terminological case where the emphasis lies on the hierarchical organization of concepts.The present paper addresses the problem of modifying terminological default logic such that more specific defaults are preferred. We assume that the specificity ordering is induced by the hierarchical organization of concepts, which means that default information is not taken into account when computing priorities. It turns out that the existing approaches for expressing priorities between defaults do not seem to be appropriate for defaults with prerequisites. Therefore we shall consider an alternative approach for dealing with prioritization in the framework of Reiter's default logic. The formalism is presented in the general setting of default logic where priorities are given by an arbitrary partial ordering on the defaults. We shall exhibit some interesting properties of the new formalism, compare it with existing approaches, and describe an algorithm for computing extensions. In the terminological case, we thus obtain an automated default reasoning procedure that takes specificity into account.This is an extended version of a paper presented at the13th International Joint Conference on Artificial Intelligence, August 1993, Chambery, France.     

Speculative Computation Through Consequence-Finding in Multi-Agent Environments

This paper is concerned with a multi-agent system which performs speculative computation under incomplete communication environments. In a master–slave style multi-agent system with speculative computation, a master agent asks queries to slave agents in problem solving, and proceeds computation with default answers when answers from slave agents are delayed. In this paper, we first provide a semantics for speculative computation using default logic. Speculative computation is considered in which reply messages from slave agents to a master are tentative and may change from time to time. In this system, default values used in speculative computation are only partially determined in advance. Next, we propose a procedure to compute speculative computation using a first-order consequence-finding procedure SOL with the answer literal method. The use of a consequence-finding procedure is convenient for updating agents' beliefs according to situation changes in the world. Then, we further refine the SOL calculus using conditional answer computation and skip-preference in SOL. The conditional answer format has a great advantage of explicitly representing how a conclusion depends on tentative replies and defaults. This dependency representation is important to avoid unnecessary recomputation of tentative conclusions. On the other hand, the skip-preference method has the great ability of preventing irrational/redundant derivations. Finally, we implemented a mechanism of process maintenance to avoid duplicate computation when slave agents change their answers. As long as new answers from slave agents do not conflict with any previously encountered situation, the obtained conclusions are never recomputed. We applied the proposed system to the meeting-room reservation problem to see the usefulness of the framework.     

Using default and causal reasoning in diagnosis

We present a theory of default reasoning that is specifically targeted to causal domains. These domains encompass a wide variety of current applications of default reasoning, but here we concentrate on model-based diagnosis. The theory is unique in that it integrates a formal notion of causality with nonmonotonic reasoning techniques based on default logic and abduction. The main structure of the theory is a default causal net (DCN) representing the causal connections among propositions in the domain. The causal net provides a framework for the two nonmonotonic reasoning techniques of assuming defaults and generating explanations for observations, allowing them to be combined in a principled way.     

Reasoning about reasoning in a meta-level architecture

In this paper we discuss reasoning about reasoning in a multiple agent scenario. We consider agents that are perfect reasoners, loyal, and that can take advantage of both the knowledge and ignorance of other agents. The knowledge representation formalism we use is (full) first order predicate calculus, where different agents are represented by different theories, and reasoning about reasoning is realized via a meta-level representation of knowledge and reasoning. The framework we provide is pretty general: we illustrate it by showing a machine checked solution to the three wisemen puzzle. The agents' knowledge is organized into units: the agent's own knowledge about the world and its knowledge about other agents are units containing object-level knowledge; a unit containing meta-level knowledge embodies the reasoning about reasoning and realizes the link among units. In the paper we illustrate the meta-level architecture we propose for problem solving in a multi-agent scenario; we discuss our approach in relation to the modal one and we compare it with other meta-level architectures based on logic. Finally, we look at a class of applications that can be effectively modeled by exploiting the meta-level approach to reasoning about knowledge and reasoning.     

Default reasoning and belief revision: A syntax-independent approach

As an important variant of Reiter‘s default logic.Poole(1988) developed a nonmonotonic reasoning framework in the classical first-order language,Brewka and Nebel extended Poole‘s approach in order to enable a representation of priorities between defaults.In this paper a general framework for default reasoning is presented,which can be viewed as a generalization of the three approaches above.It is proved that the syntax-independent default reasoning in this framework is identical to the general belief revision operation introduced by Zhang et al.(1997).This esult provides a solution to the problem whether there is a correspondence between belief revision and default logic for the infinite case .As a by-product,an answer to the the question,raised by Mankinson and Gaerdenfors(1991),is also given about whether there is a counterpart contraciton in nonmonotonic logic.     

Multi-Agent Dynamic Logics with Informational Test

This paper investigates a family of logics for reasoning about the dynamic activities and informational attitudes of agents, namely the agents' beliefs and knowledge. The logics are based on a new formalisation and semantics of the test operator of propositional dynamic logic and a representation of actions which distinguishes abstract actions from concrete actions. The new test operator, called informational test, can be used to formalise the beliefs and knowledge of particular agents as dynamic modalities. This approach is consistent with the formalisation of the agents' beliefs and knowledge as K(D)45 and S5 modalities. Properties concerning informativeness, truthfulness and preservation of beliefs are proved for a derivative of the informational test operator. It is shown that common belief and common knowledge can be expressed in the considered logics. This means, the logics are more expressive than propositional dynamic logic with an extra modality for belief or knowledge. The logics remain decidable and belong to 2EXPTIME. Versions of the considered logics express natural additional properties of beliefs or knowledge and interaction of beliefs or knowledge with actions. It is shown that a simulation of PDL can be constructed in one of these extensions.     

Formalizing Default Reasoning

Fuzzy set systems can be used to solve the problem with uncertain knowledge,and default logic can be used to solve the problem with incomplete knowledge,in some sense.In this paper,based on interval-valued fuzzy sets we introduce a method of inference which combines approximate reasoning an default ogic,and give the procedure of transforming monotonic reasoning into default reasoning.     

Seeing Is Believing

In this paper a formal framework is proposed in which variousinformative actions are combined, corresponding to the different ways in whichrational agents can acquire information. In order to solve the variousconflicts that could possibly occur when acquiring information fromdifferent sources, we propose a classification of the informationthat an agent possesses according to credibility. Based on this classification, we formalize what itmeans for agents to have seen or heard something, or to believesomething by default. We present a formalization of observations,communication actions, and the attempted jumps to conclusions thatconstitutes default reasoning. To implement these informative actionswe use a general belief revision action which satisfies theAGM postulates; dependent on the credibility of the incominginformation this revision action acts on one or more parts ofthe classified belief sets of the agents. The abilities of agents formalizeboth the limited capacities of agents to acquire information, and the preference of one kind of information acquisition to another. A very important feature of our approach is that it shows how to integratevarious aspects of agency, in particular the (informational) attitudesof dealing with information from observation, communication and defaultreasoning into one coherent framework, both model-theoretically andsyntactically.     

Modeling default reasoning using defaults

User modeling research can benefit from formal automated reasoning tools. However existing formal tools may need to be modified to suit the needs of user modeling. Theorist is a simple framework for default reasoning. It can be used as a tool for building and maintaining a user model, and as a model of a user's default reasoning. To apply Theorist to both tasks, we develop Nested Theorist (NT), a simple tool based on Theorist that allows default reasoning on arbitrarily-many levels. We extend NT in two ways: we allow prioritized defaults, and we allow reasoning about agents with limited reasoning capabilities. This paper focusses on applications, and uses wide-ranging examples from user-modeling literature to illustrate the usefulness of the tools presented.     

Belief,awareness, and limited reasoning

Several new logics for belief and knowledge are introduced and studied, all of which have the property that agents are not logically omniscient. In particular, in these logics, the set of beliefs of an agent does not necessarily contain all valid formulas. Thus, these logics are more suitable than traditional logics for modelling beliefs of humans (or machines) with limited reasoning capabilities. Our first logic is essentially an extension of Levesque's logic of implicit and explicit belief, where we extend to allow multiple agents and higher-level belief (i.e., beliefs about beliefs). Our second logic deals explicitly with “awareness,” where, roughly speaking, it is necessary to be aware of a concept before one can have beliefs about it. Our third logic gives a model of “local reasoning,” where an agent is viewed as a “society of minds,” each with its own cluster of beliefs, which may contradict each other.     

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.     

Autoepistemic logic of first order and its expressive power

We study the expressive power of first-order autoepistemic logic. We argue that full introspection of rational agents should be carried out by minimizing positive introspection and maximizing negative introspection. Based on full introspection, we propose the maximal well-founded semantics that characterizes autoepistemic reasoning processes of rational agents, and show that breadth of the semantics covers all theories in autoepistemic logic of first order, Moore's AE logic, and Reiter's default logic. Our study demonstrates that the autoepistemic logic of first order is a very powerful framework for nonmonotonic reasoning, logic programming, deductive databases, and knowledge representation.This research is partially supported by NSERC grant OGP42193.     

Counterfactual reasoning by (means of) defaults

We show how defaults can be used for counterfactual reasoning. We use a framework of modal logic to reason about both defaults and counterfactuals, in which one can express certainties, possibilities, actualities and (preferred or practical) beliefs in a distinct manner. Firstly, we discuss some properties of our approach in relation to other approaches in the literature.     

Multiagent reasoning with probability,time, and beliefs

Any agent interacting with the real world must be able to reason about uncertainty in the world, about the actions that may occur in the world (either due to the agent or those initiated by other agents), about the (probabilistic) beliefs of other agents, and how these (probabilistic) beliefs are changing over time. In this article, we develop a family of logics that a reasoning agent may use to perform successively more sophisticated types of reasoning in such environments. We also characterize different types of agents. Furthermore, we provide a logic that enables a systems designer (who may have populated an environment with a collection of such autonomous agents) to reason about the system of agents as a whole. © 1995 John Wiley & Sons, Inc.     

Nonmonotonic consequences in default domain theory

Default domain theory is a framework for representing and reasoning about commonsense knowledge. Although this theory is motivated by ideas in Reiter’s work on default logic, it is in some sense a dual framework. We make Reiter’s default extension operator into a constructive method of building models, not theories. Domain theory, which is a well established tool for representing partial information in the semantics of programming languages, is adopted as the basis for constructing partial models. This paper considers some of the laws of nonmonotonic consequence, due to Gabbay and to Kraus, Lehmann, and Magidor, in the light of default domain theory. We remark that in some cases Gabbay’s law of cautious monotony is open to question. We consider an axiomatization of the nonmonotonic consequence relation on prime open sets in the Scott topology – the natural logic – of a domain, which omits this law. We prove a representation theorem showing that such relations are in one to one correspondence with the consequence relations determined by extensions in Scott domains augmented with default sets. This means that defaults are very expressive: they can, in a sense, represent any reasonable nonmonotonic entailment. Results about what kind of defaults determine cautious monotony are also discussed. In particular, we show that the property of unique extensions guarantees cautious monotony, and we give several classes of default structures which determine unique extensions. This revised version was published online in June 2006 with corrections to the Cover Date.     

Embedding defaults into terminological knowledge representation formalisms

We consider the problem of integrating Reiter's default logic into terminological representation systems. It turns out that such an integration is less straightforward than we expected, considering the fact that the terminological language is a decidable sublanguage of first-order logic. Semantically, one has the unpleasant effect that the consequences of a terminological default theory may be rather unintuitive, and may even vary with the syntactic structure of equivalent concept expressions. This is due to the unsatisfactory treatment of open defaults via Skolemization in Reiter's semantics. On the algorithmic side, we show that this treatment may lead to an undecidable default consequence relation, even though our base language is decidable, and we have only finitely many (open) defaults. Because of these problems, we then consider a restricted semantics for open defaults in our terminological default theories: default rules are applied only to individuals that are explicitly present in the knowledge base. In this semantics it is possible to compute all extensions of a finite terminological default theory, which means that this type of default reasoning is decidable. We describe an algorithm for computing extensions and show how the inference procedures of terminological systems can be modified to give optimal support to this algorithm.This is a revised and extended version of a paper presented at the3rd International Conference on Principles of Knowledge Representation and Reasoning, October 1992, Cambridge, MA.     

A Comparative Study of Default Reasoning and Epistemic Processes

A comparative study between the theories of default reasoning and open logic is given.Some concepts of open logic,such as new premises,rejections by facts,reconstructions ,epistemic processes,and its limit are introduced to describe th evolution of hypotheses.An improved version of the limit theorem is given and proved.A model-theoretic interpretation of the closed normal defaults is given using the above concepts and the corresponding completeness is proved.Any extension of a closed normal default theory is proved to be the linit of a δ-partial increasing epistemic process of that theory,and vice versa.It is proved that there exist two distinct extensions of a closed normal default theory iff there is an δ-non-monotonic epistemic process of that theory.The completeness of Reiter‘s proof is also given and proved,in terms of the epistemic processes.Finally,the work is compared with Gaerdenfors‘s theory of knowledge in flux.     

Nonmonotonic reasoning as prioritized argumentation

This paper proposes a formalism for nonmonotonic reasoning based on prioritized argumentation. We argue that nonmonotonic reasoning in general can be viewed as selecting monotonic inferences by a simple notion of priority among inference rules. More importantly, these types of constrained inferences can be specified in a knowledge representation language where a theory consists of a collection of rules of first order formulas and a priority among these rules. We recast default reasoning as a form of prioritized argumentation and illustrate how the parameterized formulation of priority may be used to allow various extensions and modifications to default reasoning. We also show that it is possible, but more difficult, to express prioritized argumentation by default logic: Even some particular forms of prioritized argumentation cannot be represented modularly by defaults under the same language     

A Computational Framework for Practical Social Reasoning

This article describes a framework for practical social reasoning designed to be used for analysis, specification, and implementation of the social layer of agent reasoning in multiagent systems. Our framework, called the expectation strategy behavior (ESB) framework, is based on (i) using sets of update rules for social beliefs tied to observations (so‐called expectations), (ii) bounding the amount of reasoning to be performed over these rules by defining a reasoning strategy, and (iii) influencing the agent's decision‐making logic by means of behaviors conditioned on the truth status of current and future social beliefs. We introduce the foundations of ESB conceptually and present a formal framework and an actual implementation of a reasoning engine, which is specifically combined with a general (belief–desire–intention‐based) practical reasoning programming system. We illustrate the generality of ESB through select case studies, which show that it is able to represent and implement different typical styles of social reasoning. The broad coverage of existing social reasoning methods, the modularity that derives from its declarative nature, and its focus on practical implementation make ESB a useful tool for building advanced socially reasoning agents.