Learning commutative deterministic finite state automata in polynomial time

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 7,4]. We show that the entire class of commutative deterministic finite state automata (CDFAs) of an arbitrary alphabet sizek is predictable inO(s ^k) time with the worst case number of mistakes bounded above byO(s ^kk logs), wheres is the number of states in the target DFA. As a corollary, this result implies that the class of CDFAs is also PAC-learnable from random labeled examples in timeO(s ^k) with sample complexity, using a different class of representations. The mistake bound of our algorithm is within a polynomial, for a fixed alphabet size, of the lower boundO(s+k) we obtain by calculating the VC-dimension of the class. Our result also implies the predictability of the class of finite sets of commutative DFAs representing the finite unions of the languages accepted by the respective DFAs. Part of this work was supported by the Office of Naval Research under contract number N00014-87-K-0401 while the author was at the Department of Computer and Information Science, University of Pennsylvania, and N0014-86-K-0454 while at the Department of Computer and Information Sciences, U.C. Santa Cruz. The author’s email address is abe@IBL.CL.nec.co.jp