Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1991 Copyright 1991 Universität Bonn, Institut für Informatik, Abt. V
8574

Read-Once Threshold Formulas, Justifying Assignments, and Generic Transformations
Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein, Marek Karpinski
[Download PostScript] [Download PDF]

We present a membership query (i.e. interpolation) algorithm for exactly identifying the class of read-once formulas over the basis of boolean threshold functions. Using a generic transformation from [Angluin, Hellerstein, Karpinski 89], this gives an algorithm using membership and equivalence queries for exactly identifying the class of read-once formulas over the basis of boolean threshold functions and negation. We also present a a series of generic transformations that can be used to convert an algorithm in one learning model into an algorithm in a different model.

Last Change: 08/18/99 at 13:00:38
 English
Universität Bonn -> Institut für Informatik -> Abteilung V