Exact learning of read-k disjoint DNF and not-so-disjoint DNF

Howard Aizenstein, Leonard Pitt

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A polynomial-time algorithm is presented for exactly learning the class of read-k disjoint DNF formulas - boolean formulas in disjunctive normal form where each variable appears at most k times (for an arbitrary positive integer k) and every assignment to the variables satisfies at most one term of F. The (standard) protocol used allows the learning algorithm to query whether a given assignment of boolean variables satisfies the DNF formula to be learned (membership queries), as well as to obtain counterexamples to the correctness of its current hypothesis which can be any arbitrary DNF formula (equivalence queries). The formula output by the learning algorithm is logically equivalent to the formula to be learned. We show that this result also applies for a generalization of read-k disjoint DNF which we call read-k sat-j DNF; these are DNF formulas in which every variable appears at most k times and every assignment satisfies at most j terms.

Original languageEnglish (US)
Title of host publicationProceedings of the Fifth Annual ACM Workshop on Computational Learning Theory
PublisherPubl by ACM
Pages71-76
Number of pages6
ISBN (Print)089791497X, 9780897914970
DOIs
StatePublished - 1992
EventProceedings of the Fifth Annual ACM Workshop on Computational Learning Theory - Pittsburgh, PA, USA
Duration: Jul 27 1992Jul 29 1992

Publication series

NameProceedings of the Fifth Annual ACM Workshop on Computational Learning Theory

Other

OtherProceedings of the Fifth Annual ACM Workshop on Computational Learning Theory
CityPittsburgh, PA, USA
Period7/27/927/29/92

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Exact learning of read-k disjoint DNF and not-so-disjoint DNF'. Together they form a unique fingerprint.

Cite this