2010-11-16 End of learning DFA & learning WA

We finished the presentation of the DFA learning algorithm, showing how to process a counterexample and discussing the query and time complexity of the algorithm.

We showed how learnability of DFA implies learnability of O(log n)-term DNF.
The key is the following exercise:

Exercise 14: Prove that if a boolean function on n variables is computed
by a T-term DNF, then it is computed by a DFA of size polynomial in 2^T and n.
Deduce that O(log n)-term DNF are learnable in polynomial time in n from MQ+EQ.

We then presented the model of Weighted Automata (WA) over the semiring and started
explaining how the algorithm for DFA learning can be extended to learning WA over finite fields. This result was first proved by Bergadano&Varricchio (1994) and shown to have many appications by Beimel et al. (1996-conference and 2000-journal), who used the name "multiplicity automata" instead of "weighted automata". We left the following lemma as an exercise:

Exercise 15: Show that the the rank of the Hankel matrix of f is at most the number of distinct states in the smallest WA for f (w.r.t. some field).