ECCC-Report TR04-038https://eccc.weizmann.ac.il/report/2004/038Comments and Revisions published for TR04-038en-usWed, 28 Apr 2004 08:38:22 +0300
Paper TR04-038
| A Polynomial Time Learner for a Subclass of Regular Patterns |
John Case,
Sanjay Jain,
RĂ¼diger Reischuk,
Frank Stephan,
Thomas Zeugmann
https://eccc.weizmann.ac.il/report/2004/038Presented 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.
Wed, 28 Apr 2004 08:38:22 +0300https://eccc.weizmann.ac.il/report/2004/038