Reason maintenance and logic

Abstract

This thesis studies the theory and applications of recison maintenance from a logical perspective. First a series of exam ples introduces the concepts, structures and techniques of reason m aintenance. T he exam ples include the use of RMS techniques for enhancing the performance of the backtracking algorithm in discrete constraint satisfaction; reasoning about default properties - three different query-answering schemes are presented; and an exam ple of ‘model-bcLsed diagnosis’. N ext the thesis provides various logical perspectives on the tools and techniques of reason m aintenance including propositional logic, natural deduction system s, paraconsistent logic and relevance logic. It is shown that these logics have addressed issues which are closely related to the motivations of reason m aintenance systems: the need to m aintain a link between a derived assertion and its derivation; and the need to avoid the principle of tx contradictione quodlibet or the principle in ‘standard’ logic that a contradiction entails everything. The properties of propositional logic programs are next studied, using a two-fold approach of defining a “canonical m odel” that satisfies certain properties, and then of providing an iterative procedure for the computation of the-canonical m odel, called “fixpoint sem antics” . In the last chapter the m ethods of logic programming are used to study the properties of reason maintenance system s. Logical characterizations of reason m aintenance system s in terms of the m odel theory and fixpoint sem antics of logic programs are given. Applications of the characterizations to theoretical and com putational problems are given.