### Abstract

We study the learnability of Read-k-Satisfy-j (RkSj) DNF formulae. These are DNF formulae in which the maximal number of occurrences of a variable is bounded by k, and the number of terms satisfied by any assignment is at most j. We show that this class of functions is learnable in polynomial time, using Equivalence and Membership Queries, as long as k · j = O(log n/log log n)-Learnability was previously known only in case that both k and j are constants. We also present a family of boolean functions that have short (poly(n)) Read-2-Satisfy-1 DNF formulae but require CNF formulae of size 2^{φ(√n)}. Therefore, our result does not seem to follow from the recent learnability result of [Bsh93].

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 7th Annual Conference on Computational Learning Theory, COLT 1994 |

Publisher | Association for Computing Machinery |

Pages | 110-117 |

Number of pages | 8 |

ISBN (Electronic) | 0897916557 |

DOIs | |

State | Published - Jul 16 1994 |

Event | 7th Annual Conference on Computational Learning Theory, COLT 1994 - New Brunswick, United States Duration: Jul 12 1994 → Jul 15 1994 |

### Publication series

Name | Proceedings of the Annual ACM Conference on Computational Learning Theory |
---|---|

Volume | Part F129415 |

### Other

Other | 7th Annual Conference on Computational Learning Theory, COLT 1994 |
---|---|

Country | United States |

City | New Brunswick |

Period | 7/12/94 → 7/15/94 |

### ASJC Scopus subject areas

- Software
- Theoretical Computer Science
- Artificial Intelligence

## Fingerprint Dive into the research topics of 'On learning read-k-satisfy-j DNF'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the 7th Annual Conference on Computational Learning Theory, COLT 1994*(pp. 110-117). (Proceedings of the Annual ACM Conference on Computational Learning Theory; Vol. Part F129415). Association for Computing Machinery. https://doi.org/10.1145/180139.181051