Dana Angluin, Lisa Hellerstein and Marek Karpinski

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-89-528
August 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.

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},
    Institution = {EECS Department, University of California, Berkeley},
    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