Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1985-1989 Copyright 1985-1989 Universität Bonn, Institut für Informatik, Abt. V
8535

10.12.2008

Learning Read-Once Formulas with Queries
Dana Angluin, Lisa Hellerstein and Marek Karpinski
[Download PostScript] [Download PDF]

A read-once formula is a boolean formula in which each variable occurs at most once. Such formulas are also called &my;-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.

Last Change: 12/10/08 at 16:14:01
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope