Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Thomas Zeugmann:

TR04-038 | 27th April 2004
John Case, Sanjay Jain, RĂ¼diger Reischuk, Frank Stephan, Thomas Zeugmann

A Polynomial Time Learner for a Subclass of Regular Patterns

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$,
more >>>

TR98-069 | 7th December 1998
RĂ¼diger Reischuk, Thomas Zeugmann

An Average-Case Optimal One-Variable Pattern Language Learner

A new algorithm for learning one-variable pattern languages from positive data
is proposed and analyzed with respect to its average-case behavior.
We consider the total learning time that takes into account all
operations till convergence to a correct hypothesis is achieved.

For almost all meaningful distributions
defining how ... more >>>

ISSN 1433-8092 | Imprint