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 .
If you first like to see an animation of the algorithm click
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
To test the algorithm choose a 1-variable pattern like
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
Each example string can be entered in the marked box.
After each string press the button
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.
and Thomas Zeugmann
Learning One-Variable Pattern Languages in Linear Average Time.
Technical Report DOI-TR-140, Department of Informatics, Kyushu University,
R. Reischuk and
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.
R. Reischuk and
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).
Back to my
and Rüdiger Reischuk.
Last change November 1, 2004.