A theory, in this context, is a Boolean formula; it is
used to classify instances, or truth assignments. Theories
can model real-world phenomena, and can do so more or less
correctly.
The theory revision, or concept revision, problem is to
correct a given, roughly correct concept.
This problem is considered here in the model of learning
with equivalence and membership queries.
A revision algorithm is considered efficient if the number of queries
it makes is
polynomial in the revision distance between
the initial theory and the target theory,
and polylogarithmic in the number of variables and the size of the
initial theory.
The revision distance is the minimal number
of syntactic revision operations, such as the
deletion or addition of literals, needed
to obtain the target theory from the initial theory.
Efficient revision algorithms are given
for Horn formulas and read-once formulas, where revision
operators are restricted to deletions of variables or clauses,
and for parity formulas, where revision operators include
both deletions and additions of variables.
We also show that the query complexity of the read-once revision
algorithm is near-optimal.