Sequences of Revisions: On the Semantics of Nested Conditionals

ID
TR-92-23
Authors
Craig Boutilier
Publishing date
September 1992
Length
63 pages
Abstract
The truth conditions for conditional sentences have been well-studied, but few compelling attempts have been made to define means of evaluating iterated or nested conditionals. We start with a semantic account of subjunctive conditionals based on the AGM model of revision, and extend this model in a natural fashion to account for right-nesting of conditionals, describing a process called "natural revision''. These sentences capture sequences of propositional revisions of a knowledge base. We examine the properties of this model, demonstrating that the maximum amount of conditional information in a belief set is preserved after revision. Furthermore, we show how any sequence of revisions can be reduced to natural revision by a single sentence. This demonstrates that any arbitrarily nested sentence is equivalent to a sentence without nesting of the conditional connective. We show cases where revision models, even after the processing of an arbitrary sequence of revisions, can be described purely propositionally, and often in a manner that permits tractable inference. We also examine a form of revision known as "paranoid revision'' which appears to be the simplest form of belief revision that fits within the AGM framework, and captures semantically the notion of full meet revision.