An interesting idea
MAT learning of FSAs
Angluin 1987
Exact learning in polynomial time and state space
given “queries and counterexamples”
Becomes PAC learning given membership queries only
Generalized to “multiplicity automata” (Beimel et al. 1998)
Generalized to  two-tape automata (Yokomori 2000)
In tests: transducer answers membership queries!
In real applications: humans would give the answers
Queries can often be run in parallel
might run nearly N times faster given N humans…
2/5/01