VALUE MINIMIZATION IN CIRCUMSCRIPTION

Minimization in circumscription has focussed on minimizing the extent of a set of predicates (with or without priorities among them), or of a formula. Although functions and other constants may be left varying during circumscription, no earlier formalism to the best of our knowle dge minimized functions. In this paper we introduce and motivate the n otion of value minimizing a function in circumscription. Intuitively, value minimizing a function consists in choosing those models where th e value of the function is minimal relative to an ordering on its rang e. We first give the formulation of value minimization of a single fun ction based on a syntactic transformation and then give a formulation in model-theoretic terms. We then discuss value minimization of a set of functions with and without priorities. We show how Lifschitz's Nest ed Abnormality Theories can be used to express value minimization, and discuss the prospect of its use for knowledge representation, particu larly in formalizing reasoning about actions. (C) 1998 Published by El sevier B.V. All rights reserved.