1-Variable Pattern Learner
Implementation for Interactive Learning, Faster Version

This page presents an implementation of an average case optimal learning algorithm for 1-variable pattern languages described in the technical report [1]. The implementation uses a modified version that performs complete compatibility tests between pairs of strings. It gives faster convergence in case of highly symmetric sample strings.
If you first like to see an animation of the algorithm click here.

Outline of the Algorithm
Receiving a sequence of sample strings from an unknown 1-variable pattern language the algorithm computes a sequence of hypotheses that explain the samples 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 sample strings generated from this pattern,
for example replacing x by dag one gets the string abdagbcadagdagdad.

Each sample 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

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, September 1997
    Presented at 11. COLT'98, Madison, Wisconsin, July 1998
    [Abstract] [Full Paper].


Last change: 2. November 1998
Implemented by Rüdiger Reischuk and Semen Gehman.