TRACTABILITY OF THEORY PATCHING

In this paper we consider the problem of theory patching, in which we are given a domain theory, some of whose components are indicated to b e possibly flawed, and a set of labeled training examples for the doma in concept. The theory patching problem is to revise only the indicate d components of the theory, such that the resulting theory correctly c lassifies all the training examples. Theory patching is thus a type of theory revision in which revisions are made to individual components of the theory. Our concern in this paper is to determine for which cla sses of logical domain theories the theory patching problem is tractab le. We consider both propositional and first-order domain theories, an d show that the theory patching problem is equivalent to that of deter mining what information contained in a theory is stable regardless of what revisions might be performed to the theory. We show that determin ing stability is tractable if the input theory satisfies two condition s: that revisions to each theory component have monotonic effects on t he classification of examples, and that theory components act independ ently in the classification of examples in the theory. We also show ho w the concepts introduced can be used to determine the soundness and c ompleteness of particular theory patching algorithms.