|
Title:
|
Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
|
|
Author:
|
Pitt, L.; Mishra, N.; Domingo Soriano, Carlos
|
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació |
|
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 in {0,1}^n. The
algorithm yields an incremental polynomial output time solution to the
bounded degree hypergraph transversal problem, and the problem of
(read-k) monotone CNF/DNF dualization, which remain open problems of
importance in the unrestricted case. |
|
Subject(s):
|
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
-CFN
-DNF
-Learning monotone
-Membership queries |
|
Rights:
|
|
|
Document type:
|
Article - Published version
Report |
|
Share:
|
|
