An Average Case Optimal 1-Variable Pattern Language Learning Algorithm

Implementation for Interactive Learning, Faster Version

This page contains the implementation of a variant of an algorithm presented in the technical report [1] and, in more polished form, in the article [1].

First, you may wish to see an animation of this variant of the algorithm (if you still use netscape 4.x, please cclick 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).

If You see this text, Your Browser doesn't support Java-Applets
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.