On theory revision with queries
Robert H. Sloan, György Turán · 1999
The theory revision, or concept revision, problem is to correct a given, roughly correct concept. Given the representation of an initial concept, one would like to obtain a representation of the target concept by applying revisions, that is, syntactic modifications such as the deletion of a variable or a term. We give efficient revision algorithms using membership and equivalence queries for 2term monotone DNF, monotone k-DNF, and readonce formulas. An example is given showing that some monotone DNF formulas cannot be revised efficiently. These results all assume that the revisions allowed are the replacements of a variable occurrence with a constant, which, for DNFs, corresponds to deletions of variables and terms. We also discuss a more general error model where besides deletions, additions are also allowed. 1 INTRODUCTION What the computational learning theory community calls a concept is often referred to as a theory elsewhere in artificial intelligence and logic....