TR04-038 Authors: John Case, Sanjay Jain, RĂ¼diger Reischuk, Frank Stephan, Thomas Zeugmann

Publication: 28th April 2004 08:38

Downloads: 1313

Keywords:

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.