An Average Case Optimal 1Variable 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 1variable 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 1variable 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 OneVariable Pattern Languages in Linear Average Time.
Technical Report DOITR140, Department of Informatics, Kyushu University,
September 1997.
[Abstract]
[Full Paper].

R. Reischuk and
T. Zeugmann,
Learning OneVariable 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 AverageCase Optimal OneVariable Pattern Language Learner,
Journal of Computer and System Sciences
Vol. 60, No. 2, 2000, 302335.
(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.