Learning a subclass of regular patterns in polynomial time

AbstractAn 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