Learning a Subclass of Regular Patterns in Polynomial Time

Presented is an algorithm (for learning a subclass of erasing regular pattern languages) which can be made to run with arbitrarily high probability of success on extended regular languages generated by patterns π of the form x₀α₁x₁...α_mx_m for unknown m but known c, from number of examples polynomial in m (and exponential in c), where x₀,..., x_m are variables and where α₁,..., α_m are each strings of constants or terminals of length c. This assumes that the algorithm randomly draws samples with natural and plausible assumptions on the distribution. The more general looking case of extended regular patterns which alternate between a variable and fixed length constant strings, beginning and ending with either a variable or a constant string is similarly handled.