עמוס ביימל

The learnability of multiplicity automata is studied. Multiplicity automata is a theorem from automata theory relating to the number of states in a minimal multiplicity automation for a function f to the rank of a certain matrix F. This theorem was used to formulate a simple algorithm for learning multiplicity automata with a better query complexity. The theorem was also used to prove the learnability of some classes that were not known to be learnable before. While multiplicity automata were shown to be useful to prove the learnability of some subclasses of DNF formulae and various other classes, it also has some limitations. This method was shown to be unapplicable to resolve the learnability of some other open problems.