Average-Case Optimal 1-Variable Pattern Language Learning Algorithm I

This page presents an implementation of a learning algorithm first described in the technical report [1] and, in more polished form, in [3].
First, you may wish to see an animation of the algorithm (if you still use netscape 4.x, please 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. 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).

Starting the Interactive Learning

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 examples 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).

You may also test a modified version of this algorithm with faster convergence in case of highly symmetric example strings.

Bibliography

  1. 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, Fukuoka, Japan, September 1997.
    [Abstract] [Full Paper].
  2. 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].
  3. 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 Back to my Homepage

Implemented by Semen Gehman and Rüdiger Reischuk.

Last change: November 1, 2004

Valid HTML 4.0!