On characterizing and learning some classes of read-once functions
Lisa Hellerstein, Richard M. Karp · 1989
This thesis examines some classes of read-once functions. A read-once function is a boolean function that can be expressed as a read-once formula. A read-once formula is a boolean formula over the basis (AND, OR, NOT) in which each variable occurs exactly once. The thesis has two main parts. In the first part, we introduce a generalization of the read-once property. We say that a function f is read-once on a subset Z of its inputs if f can be written as a formula in which every variable in Z occurs at most once. We present a simple necessary and sufficient condition for f to be read-once on Z. It has been shown that a monotone function f is read-once (on all its inputs) if and only if for every minterm S and for every maxterm T of f, $\vert S\bigcap T\vert=1$. We consider the natural generalization of this condition to the case of functions that are read-once on Z: for every minterm S and for every maxterm T of f, $\vert S\bigcap T\bigcap Z\vert\leq1$. We show that this generalized condition is necessary but not sufficient. We then present a class of functions of which the generalized condition is both necessary and sufficient. The second part of the thesis addresses problems in computational learning theory. We present a polynomial time algorithm for exactly learning monotone read-once formulas with membership queries. Using this algorithm as a subroutine, we show a polynomial time algorithm for exactly learning unrestricted read-once formulas with membership and equivalence queries. Unrestricted read-once formulas cannot be learned with membership or equivalence queries alone, so this algorithm uses a minimal set of query types. We generalize the algorithm to show that other classes of unate formulas, such as the class of unate DNF formulas, can also be exactly learned in polynomial time using membership and equivalence queries. Finally, we present results on the complexity of search and decision problems involving read-once functions.