Dana Angluin (1987; pdf) defines a learning model with membership queries and theory queries (counterexamples to a proposed function). She shows that a regular language that is represented by a minimal DFA of $n$ states is learnable in polynomial time (where the proposed functions are DFAs) with $O(mn^2)$ membership-queries and at most $n−1$ theory-queries ($m$ is the size of the largest counter-example provided by the tutor). Unfortunately, she does not discuss lower bounds.
We can generalize the model slightly by assuming a magical tutor that can check equality between arbitrary functions and provide counterexamples if different. Then we can ask how hard it is to learn classes bigger than regular languages. I am interested in this generalization and the original restriction to regular languages.
Are there any known lower bounds on the number of queries in the membership and counterexample model?
I am interested in lower bounds on the number of membership queries, theory queries, or trade-offs between the two. I am interested in lower-bounds for any class of functions, even for more complicated classes than regular languages.
If there are no lower-bounds: Are there known bariers to proving query lower bounds in this model?