Affiliations: CRIL-CNRS, université d'Artois, rue Jean Souvraz,
62307 Lens Cedex, France | IRIT, université Paul Sabatier, 118 route de
Narbonne, 31062 Toulouse, France | PRAXITEC, 115, rue St Jacques, 13006 Marseille,
France | SIS, université de Toulon et du Var, av. de
l'université BP 132, 83957 La Garde, Cedex, France
Abstract: This paper deals with iterated belief change and proposes a drastic
revision rule that modifies a plausibility ordering of interpretations in such
a way that any world where the input observation holds is more plausible that
any world where it does not. This change rule makes sense in a dynamic context
where observations are received, and the newer observations are considered more
plausible than older ones. It is shown how to encode an epistemic state using
polynomials equipped with the lexicographic ordering. This encoding makes it
very easy to implement and iterate the revision rule using simple operations on
these polynomials. Moreover, polynomials allow to keep track of the sequence of
observations. Lastly, it is shown how to efficiently compute the revision rule
at the syntactical level, when the epistemic state is concisely represented by
a prioritized belief base. Our revision rule is the most drastic one can think
of, in accordance with Darwiche and Pearl's principles, and thus contrasts with
the minimal change rule called natural belief revision. The paper also shows
how to obtain the reversibility of Boutilier's natural belief revision and
possibilistic revision using polynomials.
