A Polynomial Time Learner for a Subclass of Regular Patterns
John Case, Sanjay K. Jain, Rüdiger Reischuk, Frank Stephan, Thomas Zeugmann · Electronic colloquium on computational complexity · 2004
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 x0 1x1::: mxm for unknown m but known c , from number of examples polynomial in m (and exponential in c ), where x0; : : : ; xm are variables and where 1; :::; 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 nding a better algorithm, we also explore computer simulations of a heuristic.