An Average Case Optimal 1-Variable Pattern Language Learning Algorithm II
This page contains the implementation
of a variant of an algorithm presented in
the technical report [1].
If you first like to see an animation of the algorithm click
here.
Receiving a sequence of example strings from an unknown 1-variable pattern
language the algorithm computes a sequence of hypotheses that explain the
examples seen so far.
At any stage of the learning procedure the algorithm remembers the common
prefix and suffix of all strings received so far
plus a single appropriate example among them (that means it requires only
constant space).
To test the algorithm choose a 1-variable pattern like
abxbcaxxdad,
where a,b,c,d,...
denote single letters (the constants) and
x the pattern variable.
Then input a sequence of example strings generated from this pattern,
for example replacing x by
dag one gets the string
abdagbcadagdagdad.
Each example string can be entered in the marked box.
After each string press the button
Learn
and the algorithm will answer with a new hypothesis.
A correct hypothesis will be computed as soon as samples are provided that are
generated from the pattern by substituting the pattern variable
with a nonsymmetric string (that means x is not replaced by a string of the
form y z y, where y,z are (nonempty) substrings - for precise definitions
see the paper).
This is a version with faster convergence.
Bibliography
-
Rüdiger Reischuk
and Thomas Zeugmann
Learning One-Variable Pattern Languages in Linear Average Time.
Technical Report DOI-TR-140, Department of Informatics, Kyushu University,
September 1997.
[Abstract]
[Full Paper].
-
R. Reischuk and
T. Zeugmann,
Learning One-Variable Pattern Languages in Linear Average Time,
in ``Proc. 11th Annual Conference on Computational Learning
Theory - COLT'98,'' July 24th - 26th, Madison, pp. 198 - 208, ACM Press 1998.
[Abstract]
[Full Paper].
-
R. Reischuk and
T. Zeugmann,
An Average-Case Optimal One-Variable Pattern Language Learner,
Journal of Computer and System Sciences
Vol. 60, No. 2, 2000, 302-335.
(Special Issue for COLT'98).
[Abstract]
[Full Paper].
Back to my
Homepage
Implemented by
S. Gehman
and Rüdiger Reischuk.
Last change November 1, 2004.