Dana Angluin and Lisa Hellerstein and Marek Karpinski

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-89-528

, 1989

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1989/CSD-89-528.pdf

A read-once formula is a boolean formula in which each variable occurs at most once. Such formulas are also called mu-formulas or boolean trees. This paper treats the problem of exactly identifying an unknown read-once formula using specific kinds of queries. <p>The main results are a polynomial time algorithm for exact identification of monotone read-once formulas using only membership queries, and a polynomial time algorithm for exact identification of general read-once formulas using equivalence and membership queries (a protocol based on the notion of a minimally adequate teacher). Our results improve on Valiant's previous results for read-once formulas. We also show that no polynomial time algorithm using only membership queries or only equivalence queries can exactly identify all read-once formulas.

---

BibTeX citation:

@techreport{Angluin:CSD-89-528,
    Author= {Angluin, Dana and Hellerstein, Lisa and Karpinski, Marek},
    Title= {Learning Read-Once Formulas with Queries},
    Year= {1989},
    Month= {Aug},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1989/5897.html},
    Number= {UCB/CSD-89-528},
    Abstract= {A read-once formula is a boolean formula in which each variable occurs at most once. Such formulas are also called mu-formulas or boolean trees. This paper treats the problem of exactly identifying an unknown read-once formula using specific kinds of queries. <p>The main results are a polynomial time algorithm for exact identification of monotone read-once formulas using only membership queries, and a polynomial time algorithm for exact identification of general read-once formulas using equivalence and membership queries (a protocol based on the notion of a minimally adequate teacher). Our results improve on Valiant's previous results for read-once formulas. We also show that no polynomial time algorithm using only membership queries or only equivalence queries can exactly identify all read-once formulas.},
}

EndNote citation:

%0 Report
%A Angluin, Dana 
%A Hellerstein, Lisa 
%A Karpinski, Marek 
%T Learning Read-Once Formulas with Queries
%I EECS Department, University of California, Berkeley
%D 1989
%@ UCB/CSD-89-528
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1989/5897.html
%F Angluin:CSD-89-528