Abstract

Circumscription is a form of non-monotonic reasoning, introduced by McCarthy as a way of characterizing common-sense defaults. It characterizes the non-monotonic consequences of a theory, as the formulas true in the minimal models of that theory under a partial-order. However, there are partial orders with no minimal models. In this case circumscription maps a satisfiable theory to falsity.

This would be of purely academic interest, but for the fact that many natural defaults have this character of lacking minimal models. The set of intuitive consequences of these defaults is not all sentences.

We propose an alternative to minimal semantics. We propose that reasonable beliefs are those whose models contain a dense ideal of the partial-order. We then look at some properties of this choice, for example, does it preserve the structural properties of circumscription?

We then look at how we can use this insight to modify circumscription, so that it maps satisfiable theories to satisfiable theories.

Abstract

Circumscription is a form of non-monotonic reasoning, introduced by McCarthy as a way of characterizing defaults using second order logic. The consequences of circumscription are those formulas true in the minimal models under a pre-order on models. In the case of domain circumscription the pre-order was the sub-model relation. Formula circumscription is characterized by minimizing a set of formulas---one model is preferred to another model when the extensions of the minimized formulas in the first are subsets of the extensions in the second.

We show that the propositional version of formula circumscription can capture all pre-orders on valuations of finite languages. We consider the question of infinite languages, and give the corresponding representation theorems. Infinitary propositional logics are of interest as they correspond closely to first order logics with fixed domains. We show that even logics with countable connectives cannot describe all pre-orders on models of countable infinite languages. We further show that there are natural defaults, captured by inductive definitions, that cannot be captured by circumscription in the first order case. Formulas of this sort have been suggested as an extension of circumscription by Lifschitz.

Finally, contrary to previous claims, we show that propositional formula circumscription can capture all preferential consequence relations over finite propositional languages, as defined by Kraus et al. Thus, in the finite propositional case, there is no restriction on the kinds of preferential defaults that circumscription can describe.

Abstract

Circumscription is a form of non-monotonic reasoning. The first version of circumscription, domain circumscription, is analogous to mathematical induction. Given a theory, it chooses the models of that theory whose domains are minimal with respect to inclusion. It captures the assumption that as few objects exist as possible.

Predicate and formula circumscription, introduced later, are characterized by a set of predicates or formulas to minimize. They choose the models that have as few objects true of the minimized predicates/formulas as possible. However, they do not compare models of different cardinality. Thus they are not an extension of domain circumscription, they are incomparable in expressive power.

We introduce a new form of circumscription that allows models that differ on domains to be compared. It extends both domain and formula circumscription, hence its name. It removes the artificial constraint that predicate and formula circumscription impose, and thus gives more intuitive semantics.

Quantifiers over Contexts (with Anna Patterson) to appear in KR&R '98, a preliminary version appeared in Commonsense '98

Abstract

We can reason about theories, as well as in them. Many natural phenomena can be captured by theories, often by introducing a modality, true just of the theory. Rather than treat these phenomena as the sentences true in this modality, we can treat the entire theory or modality as an object. This point of view was proposed by McCarthy, who proposed calling these reified modalities contexts.

Contexts, viewed as theories or modalities, have structural properties, and associated natural structural operations, such as union and intersection. These structural properties are most naturally captured by an algebra, reminiscent of relation or dynamic algebra , a set of operations that can be applied to contexts to form new contexts.

Thus we can have a larger space of modalities than just those that are explicitly named. We add quantifiers that range over modalities, so that we can state propositions like, ``no context with the property P exists'', or ``all contexts obey Q''. We give an axiomatization of these quantifiers which we show is complete with respect to a natural semantics.

Abstract

Counterfactual conditional sentences can be useful in artificial intelligence. In particular, they allow reasoners to learn from experiences that they did not quite have. The truth of a counterfactual and the conclusions that can be drawn from a counterfactual are theory dependent, and different theories are useful in different circumstances.

A simple class of useful counterfactuals involves a change of one component of a point in a space provided with a Cartesian product structure. We call these Cartesian counterfactuals. Cartesian counterfactuals can be modeled by assignment and contents functions as in program semantics.

Abstract

A theory is elaboration tolerant to the extent that new information can be incorporated with only simple changes. The simplest change is conjoining new information, and only conjunctive changes are considered in this paper. In general adding information to a theory should often change, rather than just enlarge, its consequences, and this requires that some of the reasoning be non-monotonic.

Our theories are narratives---accounts of sets of events, not necessarily given as sequences. A narrative is elaboration tolerant if new events, or more detail about existing events, can be added by just adding more sentences.

We propose a new version of the situation calculus which allows information to be added easily. In particular, events concurrent with already described events can be introduced without modifying the existing descriptions, and more detail of events can be added.

Abstract

The frame problem---representing the default that the only effects of actions are those mentioned---is a central problem in knowledge representation. This default can be captured, using circumscription, by minimizing the set of change formulas that are true, where a change formula is a formula that states that, under certain circumstances, an event causes a fluent to change its value. This approach handles domain constraints and arbitrary disjunctions correctly, unlike previous proposals. It applies a single circumscription policy to the entire theory, rather than use ad-hoc methods that depend on applying several circumscriptions or splitting up the theory before circumscription is applied.

Abstract

We introduce a new methodology for comparing non-monotonic treatments of change. We consider the elaboration tolerance of various proposals. The elaboration tolerance of a non-monotonic approach is defined as the elaborations, or changes, that can be made to the non-monotonic consequences, by conjoining on new information. The standard problem, the frame assumption, is capturing the tendency of properties to persist over time. We show that almost all approaches allow new effects to be added, and preconditions to be dropped. There are other ways of describing the world, and we investigate one in particular, assuming there are as few preconditions for an action as possible. This is equivalent to assuming that actions change properties as often as possible, if they ever change that property. We show that this assumption is in conflict with the usual frame assumption. We show that this methodology allows new effects to be added, and preconditions to be added. We show that this precondition assumption is naturally opposite to the frame assumption. We then show that this assumption can be naturally captured in a similar way to the frame problem, using circumscription.

Abstract

We consider the frame problem, that is, characterizing the assumption that properties tend to persist over time. We show that there are at least three distinct assumptions that can be made. We show the first assumption, which have been widely studied, is not naturally captured by circumscription. The first assumption is, ``there is as little change as possible between one situation and the next''. This is closely related to temporal projection. The second assumption is that actions have as few effects as possible. This has arisen in causal approaches. We show this assumption cannot be captured by any circumscription policy, as it compares models with different domains. We consider a third assumption---there are as many frame axioms true as possible---which can be captured by circumscription. All three assumptions differ, which we show by giving examples. All agree on a small class of theories, those axiomatized by effect axioms and a class of sentences we call compatible binary domain constraints. Further, for a similar class of theories a deduction theorem holds, allowing observations, or facts about particular situations, to be brought through the non-monotonic consequence relation. This justifies approaches based on separating ``observations'' from ``effects'', and applying projection to the effects, to solve problems based on causality reasoning.

Abstract

Non-monotonic reasoning is reasoning that will deny conclusions in the light of new evidence. This kind of reasoning is important for many common sense phenomena. In particular it is useful in reasoning about change. Circumscription is a common methodology for capturing non-monotonic inferences. I characterize its expressive power, and show how it can be extended, to be more tolerant of new defaults, and so that it can capture defaults that current versions cannot express. Examples from reasoning about action are used as the primary motivating tool.

Abstract

We can represent how to change our beliefs in the light of new information by using a conditional ``if A is the case, then we should accept B''. We propose that this belief change conditional should be defined as material implication when A is consistent with our current beliefs, and as a suitable counterfactual in the other case. We show that the resulting belief change system obeys the rationality postulates suggested by Alchourron, Gardenfors, and Makinson. To get an exact correspondence between systems of belief change thus defined in terms of counterfactuals, and systems based on rationality postulates, it is more intuitive to modify the usual ``closest possible world'' models of counterfactuals, so that different similarity measures centered at the same world are cotenable, and all worlds are ranked. Once this is done we can achieve a correspondence between finite sequences of belief changes using rationality postulates and models of a counterfactual. The valid counterfactual sentences do not constitute a possible state of belief. They do not decide enough sentences. However, we can specify a state of belief, by adding the additional sentences, that describe the fact that we believe no counterfactuals, save those that we have explicitly been told. This characterizes a ``tabula rasa'' or blank slate, upon which we can impose any belief change system, by revising it with the sentences that characterize the defaults of that belief change system.