An extended review of what is known about the formal behaviour of nonmonotonic inference operations, including those generated by the principal systems in the artificial intelligence literature. Directed towards computer scientists and others with some background in logic.

It is natural and important to have a formal representation of plain belief, according to which propositions are held true, or held false, or neither. (In the paper this is called a deterministic representation of epistemic states). And it is of great philosophical importance to have a dynamic account of plain belief. AGM belief revision theory seems to provide such an account, but it founders at the problem of iterated belief revision, since it can generally account only for one step (...) of revision. The paper discusses and rejects two solutions within the confines of AGM theory. It then introduces ranking functions (as I prefer to call them now; in the paper they are still called ordinal conditional functions) as the proper (and, I find, still the best) solution of the problem, proves that conditional independence w.r.t. ranking functions satisfies the so-called graphoid axioms, and proposes general rules of belief change (in close analogy to Jeffrey's generalized probabilistic conditionalization) that encompass revision and contraction as conceived in AGM theory. Indeed, the parallel to probability theory is amazing. Probability theory can profit from ranking theory as well since it is also plagued by the problem of iterated belief revision even if probability measures are conceived as Popper measures (see No. 11). Finally, the theory is compared with predecessors which are numerous and impressive, but somehow failed to explain the all-important conditional ranks in the appropriate way. (shrink)

The book can also be used as an excellent text for graduate-level courses in AI, operations research, or applied probability.

Examines the link between nonmonotonic inference relations and theory revision operations, focusing on the correspondence between abstract properties which each may satisfy.

This paper investigates the formal relationship between two prominent approaches to the logic of belief change. The first one uses the idea of "relational partial meet contractions" as developed by Alchourrón, Gärdenfors and Makinson (Journal of Symbolic Logic 1985), the second one uses the concept of "epistemic entrenchment" as elaborated by Gärdenfors and Makinson (in Theoretical Aspects of Reasoning about Knowledge, M. Y. Vardi, Los Altos 1988). The two approaches are shown to be strictly equivalent via direct links between the (...) underlying formal relations. The paper closes with observations about the application of epistemic entrenchment to simple and iterated revisions. (shrink)