Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries

We consider exact learning monotone CNF formulas in which each variable app ears 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 natu ral number k. We give an incremental output polynomial time algorithm for e xact learning both the read-k CNF and (not necessarily read restricted) DNF descriptions of f. The algorithm's only method of obtaining information ab out f is through membership queries, i.e., by inquiring about the value f(x ) for points x is an element of {0, 1}(n). The algorithm yields an incremen tal polynomial output time solution to the (read-k) monotone CNF/DNF dualiz ation problem. The unrestricted versions remain open problems of importance .