Skeptical reason maintenance and belief revision
type: Item
instance of: scholarly article
title: Skeptical reason maintenance and belief revision
zbMATH Open document ID: 0779.68081
DOI: 10.1016/0004-3702(93)90090-X
author: Gerhard Brewka
author: Cees Witteveen
published in: Artificial Intelligence
publication date: 1994-01-19T00:00:00Z
review text: 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)\).
Mathematics Subject Classification ID: 68T27
Mathematics Subject Classification ID: 68T15
zbMATH DE Number: 417267
zbMATH Keywords: theory-revision
zbMATH Keywords: complexity
zbMATH Keywords: three-valued logic
reviewed by: Cees Witteveen
MaRDI profile type: Publication
cites work: On the logic of theory change: Partial meet contraction and revision functions
cites work: Q4342079
cites work: Q4028789
cites work: Linear-time algorithms for testing the satisfiability of propositional horn formulae
cites work: Q3975143
cites work: Q3107917
cites work: Q5812175
cites work: Q3339245
cites work: Semantical considerations on nonmonotonic logic
cites work: Q3493313
cites work: Q3484349
cites work: Q3486858
cites work: The well-founded semantics for general logic programs
cites work: Q4395144
full work available at URL: 0004-3702(93)90090-x
OpenAlex ID: W2057095065
Recommended article: Reasoning About Belief Revision
Recommended article: Q4225125
Recommended article: Belief revision and epistemology
Recommended article: Belief revision: A critique
Recommended article: Belief revision and verisimilitude
Recommended article: Rational evaluation in belief revision
Recommended article: Q4023583
Recommended article: Q5271420
Recommended article: Q4028789
Recommended article: Frontiers in belief revision
description: scientific article; zbMATH DE number 417267