•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…
•