Abstract:
It has been shown in previous recent work that multiplicity automata are predictable from multiplicity and equivalence queries. In this paper we generalize related notions in a matrix representation and obtain a basis for the solution of a number of open problems in learnability theory. Membership queries are generalized to ``substitution'' queries for learning non-boolean functions and provide the value of the target function for a given input. In particular, using substitution and equivalence queries, we prove the learnability of the boolean XOR of terms, XOR decision trees, decision trees with integer variables and less than conditions, multivariate polynomials over a finite field and rational functions over a fixed finite field. We also provide results for the case of infinite or large fields.