Learning a subclass of regular patterns in polynomial time

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 x 0 α 1 x 1 ... α m x m, where x 0, ..., x m 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. © 2006 Elsevier B.V. All rights reserved.