Publication Details
Title: Learning Read-Once Formulas with Queries
Author: D. Angluin, L. Hellerstein, and M. Karpinski
Group: ICSI Technical Reports
Date: July 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-50.pdf
Overview:
A read-once formula is a boolean formula in which each variable occurs at most once. Such formulas are also called m-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[1]). Our results improve on Valiant's previous results for read-once formulas [18]. We also show that no polynomial time algorithm using only membership queries or only equivalence queries can exactly identify all read-once formulas.
Bibliographic Information:
ICSI Technical Report TR-89-050
Bibliographic Reference:
D. Angluin, L. Hellerstein, and M. Karpinski. Learning Read-Once Formulas with Queries. ICSI Technical Report TR-89-050, July 1989
Author: D. Angluin, L. Hellerstein, and M. Karpinski
Group: ICSI Technical Reports
Date: July 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-50.pdf
Overview:
A read-once formula is a boolean formula in which each variable occurs at most once. Such formulas are also called m-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[1]). Our results improve on Valiant's previous results for read-once formulas [18]. We also show that no polynomial time algorithm using only membership queries or only equivalence queries can exactly identify all read-once formulas.
Bibliographic Information:
ICSI Technical Report TR-89-050
Bibliographic Reference:
D. Angluin, L. Hellerstein, and M. Karpinski. Learning Read-Once Formulas with Queries. ICSI Technical Report TR-89-050, July 1989