Learning μ-branching programs with queries
Vijay Raghavan, Dawn E. Wilkins · 1993
We show that the class of p-branching programs can be exactly learned in ()(rz5) time us:n$ only O(n) equivalence queries and O(n ) membership queries, but neither type of query alone is sufficient for polynomial time learning.