Author name cluster
Tom Costello
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
Possible papers
4AIJ Journal 1998 Journal Article
The expressive power of circumscription
- Tom Costello
Circumscription is a form of nonmonotonic reasoning, introduced by McCarthy (1997) 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 (McCarthy, 1980, 1986) 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. We further show that there are natural defaults (inertia in temporal projection), captured by inductive definitions, that cannot be captured by circumscription in the first order case. 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. (1990). Thus, in the finite propositional case, there is no restriction on the kinds of preferential defaults that circumscription can describe.