# Learning Read-Once Formulas with Queries

### Dana Angluin, Lisa Hellerstein and Marek Karpinski

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-89-528

August 1989

### http://www.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://www.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://www.eecs.berkeley.edu/Pubs/TechRpts/1989/5897.html %F Angluin:CSD-89-528