06/01/1990 09:00 AM
Computer Science
We consider the problem of learning the commutative subclass of regular languages in the on-line model of predicting {0,1}-valued functions from examples and reinforcements due to Littlestone. We show that the entire class of commutative deterministic finite state automata (CDFA\'s) of an arbitrary alphabet size k is predictable in this model, with the worst case number of mistakes bounded above by a polynomial in the number of states s in the target DFA, and independent of the length of example strings. More precisely the mistake bound is of order O(s^{2k} k log s). By Littlestone\'s result on converting a mistake bound in this model to a sample Complexity bound for PAC-learning, this result also implies that the class of CDFA\'s is PAC-learnable from random labeled examples only in polynomial time with sample complexity O (1/epsilon (log 1/delta + s^{2k} k log s)), using a different class of representations. The class of CDFA\'s is one of the few natural, non-trivial subclasses of DFA\'s which have been shown to be polynomially predictable to date.
