Exact learning of read-twice DNF formulas

Howard Aizenstein, Leonard B Pitt

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

Abstract

A polynomial-time algorithm is presented for exactly learning the class of read-twice DNF formulas, i.e., Boolean formulas in disjunctive normal form where each variable appears at most twice. 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.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherPubl by IEEE
Pages170-179
Number of pages10
ISBN (Print)0818624450
StatePublished - Dec 1 1991
EventProceedings of the 32nd Annual Symposium on Foundations of Computer Science - San Juan, PR, USA
Duration: Oct 1 1991Oct 4 1991

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

Other

OtherProceedings of the 32nd Annual Symposium on Foundations of Computer Science
CitySan Juan, PR, USA
Period10/1/9110/4/91

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Exact learning of read-twice DNF formulas'. Together they form a unique fingerprint.

  • Cite this

    Aizenstein, H., & Pitt, L. B. (1991). Exact learning of read-twice DNF formulas. In Annual Symposium on Foundations of Computer Science (Proceedings) (pp. 170-179). (Annual Symposium on Foundations of Computer Science (Proceedings)). Publ by IEEE.