### 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 language | English (US) |
---|---|

Title of host publication | Annual Symposium on Foundations of Computer Science (Proceedings) |

Publisher | Publ by IEEE |

Pages | 170-179 |

Number of pages | 10 |

ISBN (Print) | 0818624450 |

State | Published - Dec 1 1991 |

Event | Proceedings of the 32nd Annual Symposium on Foundations of Computer Science - San Juan, PR, USA Duration: Oct 1 1991 → Oct 4 1991 |

### Publication series

Name | Annual Symposium on Foundations of Computer Science (Proceedings) |
---|---|

ISSN (Print) | 0272-5428 |

### Other

Other | Proceedings of the 32nd Annual Symposium on Foundations of Computer Science |
---|---|

City | San Juan, PR, USA |

Period | 10/1/91 → 10/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.