One of the earliest paradigms for feasible exact learning,  Angluin’s  formulation of learning from membership and equivalence queries, continues to supply a framework for new and interesting results. More specifically, its embodiment in an algorithm for learning multiplicity automata can be used to solve several previously open problems, as explained in this well-written compendium of several recent conference papers.

The heart of this work lies in identifying concept classes that can be represented by infinite matrices (Hankel matrices) of finite rank; such matrices correspond in turn to multiplicity automata. Some of these classes are satisfy-O ( 1 ) DNF; polynomials over finite fields; and certain unions of n-dimensional boxes. All of these classes have Hankel matrix ranks that are polynomially bounded in the concept size, implying feasible exact learnability.

The authors also improve previously published algorithms for learning multiplicity automata, thus supplying new and sometimes more efficient algorithms for learning classes such as deterministic finite-state automata and nondeterministic unambiguous automata. The results in this paper are somewhat orthogonal to earlier work, as they do not encompass some known-to-be-learnable classes, such as monotone DNF, read-once DNF, and 2-DNF.

The extensive list of references reads like a synopsis of known exact learning results, many of which are extended or improved on by this paper.