Skeptical reason maintenance and belief revision (Q685347)

The ability to maintain a coherent and consistent set of beliefs and to revise them when contradictions occur, is a major characteristic of intelligent reasoning systems. One of the contexts in which the maintenance and revision of beliefs has been studied extensively, is the field of Reason Maintenance Systems. We discuss a 3-valued skeptical semantics for reason maintenance based on an extension of the well-knwon 2 valued grounded or stable model semantics. Unlike the latter, however, the skeptical semantics has a computationally attractive feature: the skeptical model can be computed in \(O(n^ 2)\) time. The skeptical semantics can also be used to give a better account of the belief revision problem in reason maintenance. A recent logical reconstruction of Dependency-Directed Backtracking (DDB) offers the possibility to represent different DDB-strategies by different extensions of a reason maintenance system. Given a reason maintenance system \(D\), we can distinguish a class of extensions, representing all possible DDB strategies for \(D\). We will prove that within this class there exists a unique extension whose skeptical model can be used as a canonical, information minimal belief revision model. This skeptical belief revision model has some important advantages: 1. the arbitrariness of solutions found by classical dependency directed backtracking methods can be avoided. 2. the semantics guarantees a (tractable) incremental updating method, and this method satisfies - contrary to standard belief revision techniques - a weak rationality postulate ensuring the minimality of performed changes. 3. skeptical belief revision is a complete belief revision strategy and is easy to computer having a worst case complexity \(O(n^ 3)\).