Learning read-once formulas with queries
- 2 January 1993
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 40 (1) , 185-210
- https://doi.org/10.1145/138027.138061
Abstract
A read-once formula is a Boolean formula in which each variable occurs, at most, once. Such formulas are also called μ-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]). The results of the authors improve on Valiant's previous results for read-once formulas [26]. It is also shown, that no polynomial-time algorithm using only membership queries or only equivalence queries can exactly identify all read-once formulas.Keywords
This publication has 13 references indexed in Scilit:
- Learning Read-Onee Formulas over Fields and Extended BasesPublished by Elsevier ,1991
- Prediction-preserving reducibilityJournal of Computer and System Sciences, 1990
- Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite FieldsSIAM Journal on Computing, 1990
- Learning context-free grammars from structural data in polynomial timeTheoretical Computer Science, 1990
- LEARNING SWITCH CONFIGURATIONSPublished by Elsevier ,1990
- LEARNING READ-ONCE FORMULAS USING MEMBERSHIP QUERIESPublished by Elsevier ,1989
- Computational limitations on learning from examplesJournal of the ACM, 1988
- Learning regular sets from queries and counterexamplesInformation and Computation, 1987
- A theory of the learnableCommunications of the ACM, 1984
- Fast probabilistic algorithms for hamiltonian circuits and matchingsJournal of Computer and System Sciences, 1979