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
\pi of the form x_0 \alpha_1 x_1 ... \alpha_m x_m
for unknown m but known c,
from number of examples polynomial in m (and exponential in c), where
x_0,\ldots,x_m are variables and
where \alpha_1,...,\alpha_m are each strings of terminals of
length c. This assumes that the algorithm randomly draws samples
with natural and plausible assumptions on the distribution.
With the aim of finding a better algorithm, we also explore computer
simulations of a heuristic.