We consider the connections between belief revision, conditional logic and nonmonotonic reasoning, using as a foundation the approach to theory change developed by Alchourrón, Gärdenfors and Makinson (the AGM approach). This is first generalized to allow the iteration of theory change operations to capture the dynamics of epistemic states according to a principle of minimal change of entrenchment. The iterative operations of expansion, contraction and revision are characterized both by a set of postulates and by Grove's construction based on total (...) pre-orders on the set of complete theories of the belief logic. We present a sound and complete conditional logic whose semantics is based on our iterative revision operation, but which avoids Gärdenfors's triviality result because of a severely restricted language of beliefs and hence the weakened scope of our extended postulates. In the second part of the paper, we develop a computational approach to theory dynamics using Rott's E-bases as a representation for epistemic states. Under this approach, a ranked E-base is interpreted as standing for the most conservative entrenchment compatible with the base, reflecting a kind of foundationalism in the acceptance of evidence for a belief. Algorithms for the computation of our iterative versions of expansion, contraction and revision are presented. Finally, we consider the relationship between nonmonotonic reasoning and both conditional logic and belief revision. Adapting the approach of Delgrande, we show that the unique extension of a default theory expressed in our conditional logic of belief revision corresponds to the most conservative belief state which respects the theory: however, this correspondence is limited to propositional default theories. Considering first order default theories, we present a belief revision algorithm which incorporates the assumption of independence of default instances and propose the use of a base logic for default reasoning which incorporates uniqueness of names. We conclude with an examination of the behavior of an implemented system on some of Lifschitz's benchmark problems in nonmonotonic reasoning. (shrink)

We present an approach to combining three areas of research which we claim are all based on information theory: knowledge representation in Artificial Intelligence and Cognitive Science using prototypes, plans, or schemata; formal semantics in natural language, especially the semantics of the `if-then' conditional construct; and the logic of subjunctive conditionals first developed using a possible worlds semantics by Stalnaker and Lewis. The basic premise of the paper is that both schema-based inference and the semantics of conditionals are based on (...) Dretske's notion of information flow and Barwise and Perry's notion of a constraint in situation semantics. That is, the connection between antecedent and consequent of a conditional `if were the case then would be the case' is an informational relation holding with respect to a pragmatically determined utterance situation. The bridge between AI and conditional logic is that a prototype or planning schema represents a situation type, and the background assumptions underlying the application of a schema in a situation correspond to channel conditions on the flow of information. Adapting the work of Stalnaker and Lewis, the semantics of conditionals is modeled by a refinement ordering on situations: a conditional `if then ' holds with respect to a situation if all the minimal refinements of the situation that support also support . We present new logics of situations, information flow, and subjunctive conditionals based on three-valued partial logic that formalizes our approach, and conclude with a discussion of the resulting theory of conditionals, including the "paradoxes" of conditional implication, the difference between truth conditions and assertability conditions for subjunctive conditionals, and the relationship between subjunctive and indicative conditionals. (shrink)