Skeptical reason maintenance and belief revision

摘要

The skeptical semantics is a three-valued semantics for reason maintenance based on an extension of the well-known two-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(n2) 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.(1) The arbitrariness of solutions found by classical dependency-directed backtracking methods can be avoided.2.(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.(3) Skeptical belief revision is a complete belief revision strategy and is easy to compute, having a worst-case complexity O(n3).