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