Efficient Read-Restricted Monotone CNF/DNF Dualization by Learning with Membership Queries
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.
Cite
Text
Domingo et al. "Efficient Read-Restricted Monotone CNF/DNF Dualization by Learning with Membership Queries." Machine Learning, 1999. doi:10.1023/A:1007627028578Markdown
[Domingo et al. "Efficient Read-Restricted Monotone CNF/DNF Dualization by Learning with Membership Queries." Machine Learning, 1999.](https://mlanthology.org/mlj/1999/domingo1999mlj-efficient/) doi:10.1023/A:1007627028578BibTeX
@article{domingo1999mlj-efficient,
title = {{Efficient Read-Restricted Monotone CNF/DNF Dualization by Learning with Membership Queries}},
author = {Domingo, Carlos and Mishra, Nina and Pitt, Leonard},
journal = {Machine Learning},
year = {1999},
pages = {89-110},
doi = {10.1023/A:1007627028578},
volume = {37},
url = {https://mlanthology.org/mlj/1999/domingo1999mlj-efficient/}
}