1-Variable Pattern Learner
Implementation for Interactive Learning

This page presents an implementation of an average case optimal learning algorithm for 1-variable pattern languages described in the technical report [1].
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).

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].