## Abstract

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

Pages (from-to) | 89-110 |

Number of pages | 22 |

Journal | Machine Learning |

Volume | 37 |

Issue number | 1 |

DOIs | |

State | Published - 1999 |

Externally published | Yes |

## ASJC Scopus subject areas

- Software
- Artificial Intelligence