Vol. 15 No. 5, © The Author, 2005. Published by Oxford University Press. All rights reserved.
Original Articles |
Expressing Default Logic Variants in Default Logic
1 School of Computing Science, Simon Fraser University, Burnaby, B.C., V5A 1S6, Canada. Email: jim{at}cs.sfu.ca, 2 Institut für Informatik, Universität Potsdam, D-14415 Potsdam, Germany, and affiliated with the School of Computing Science at Simon Fraser University, Burnaby, Canada. Email: torsten{at}cs.uni-potsdam.de
Reiter's default logic is one of the best known and most studied of the approaches to nonmonotonic reasoning. Several variants of default logic have subsequently been proposed to give systems with properties differing from the original. In this paper, we examine the relationship between default logic and its major variants. We accomplish this by translating a default theory under a variant interpretation into a second default theory, under the original Reiter semantics, wherein the variant interpretation is respected. That is, in each case we show that, given an extension of a translated theory, one may extract an extension of the original variant default logic theory. We show how constrained, rational, justified, and cumulative default logic can be expressed in Reiter's default logic. As well, we show how Reiter's default logic can be expressed in rational default logic. From this, we suggest that any such variant can be similarly treated. Consequently, we provide a unification of default logics, showing how the original formulation of default logic may express its variants. Moreover, the translations clearly express the relationships between alternative approaches to default logic. The translations themselves are shown to generally have good properties. Thus, in at least a theoretical sense, we show that these variants are in a sense superfluous, in that for any of these variants of default logic, we can exactly mimic the behaviour of a variant in standard default logic. As well, the translations lend insight into means of classifying the expressive power of default logic variants; specifically we suggest that the property of semi-monotonicity represents a division with respect to expressibility, whereas regularity and cumulativity do not.
Keywords: Knowledge representation, nonmonotonic reasoning, default logic
Received 4 February 2004.