Learning a Subclass of Regular Patterns in Polynomial Time

Authors: John Case, Sanjay Jain, Rüdiger Reischuk, Frank Stephan and Thomas Zeugmann

Source: Theoretical Computer Science, Vol. 364, Issue 1, 2006, 115-131. (Special Issue Algorithmic Learning Theory (ALT 2003)). Abstract. An algorithm for learning a subclass of erasing regular pattern languages is presented. On extended regular pattern languages generated by patterns π of the form x0 α1x1 ... αmxm, where x0, ..., xm are variables and α1, ..., αm strings of terminals of length c each, it runs with arbitrarily high probability of success using a number of examples polynomial in m (and exponential in c). It is assumed that m is unknown, but c is known and that samples are randomly drawn according to some distribution, for which we only require that it has certain natural and plausible properties. Aiming to improve this algorithm further we also explore computer simulations of a heuristic. Keywords: Learning theory; Inductive inference; Regular pattern languages, Learning from examples; Probabilistically exact learning ©Copyright 2006, Elsevier Science B.V.