Theory revision with queries: DNF formulas

Judy Goldsmith, Robert H. Sloan, György Turán

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


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 three classes of disjunctive normal form expressions: monotone k-DNF, monotone m-term DNF and unate two-term DNF. A negative result shows that some monotone DNF formulas are hard to revise.

Original languageEnglish
Pages (from-to)257-295
Number of pages39
JournalMachine Learning
Issue number2-3
StatePublished - May 2002

Bibliographical note

Funding Information:
∗Partially supported by NSF grant CCR-9610348; work done while visiting the Dept. of EECS at the University of Illinois at Chicago and the Dept. of Computer Science at Boston University. †Partially supported by NSF grant CCR-9800070. ∗∗Partially supported by NSF grant CCR-9800070, and OTKA T-25721.


  • Boolean function learning
  • Computational learning theory
  • Disjunctive normal form
  • Knowledge revision
  • Query learning
  • Theory revision

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence


Dive into the research topics of 'Theory revision with queries: DNF formulas'. Together they form a unique fingerprint.

Cite this