Topic: GENERAL LOGIC
On the Complexity of Propositional Knowledge Base Revision, Updates, and Counterfactuals
By Thomas Eiter and Georg Gottlob
We study the complexity of several recently proposed methods for updating or revising propositional knowledge bases under the principle of minimal change. In particular, we derive complexity results for the following problem: given a knowledge base T, an update p, and a formula q, decide whether q is derivable from Tp, the updated (or revised) knowledge base. Note that this problem includes the evaluation of the counterfactual p > q over T, that is a conditional statement 'if p, then q' where p is known or expected to be false. We consider the general case where T is an arbitrary propositional formula (or theory) as well as restricted versions of this problem, in particular where T is a conjunction of Horn clauses, or where the size of the update p is bounded by a constant.
Download
Related post
Posted by Tony Marmo
at 00:01 GMT
Updated: Tuesday, 7 December 2004 23:02 GMT
