Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries

Carlos Domingo, Nina Mishra, Leonard Pitt

Research output: Contribution to journalArticlepeer-review


We consider exact learning monotone CNF formulas in which each variable appears at most some constant k times (`read-k' monotone CNF). Let f: {0,1}n→{0,1} be expressible as a read-k monotone CNF formula for some natural number k. We give an incremental output polynomial time algorithm for exact learning both the read-k CNF and (not necessarily read restricted) DNF descriptions of f. The algorithm's only method of obtaining information about f is through membership queries, i.e., by inquiring about the value f(x) for points x∈{0,1}N. The algorithm yields an incremental polynomial output time solution to the (read-k) monotone CNF/DNF dualization problem. The unrestricted versions remain open problems of importance.

Original languageEnglish (US)
Pages (from-to)89-110
Number of pages22
JournalMachine Learning
Issue number1
StatePublished - 1999
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence


Dive into the research topics of 'Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries'. Together they form a unique fingerprint.

Cite this