This page presents an implementation
of an average case optimal learning algorithm for 1-variable
pattern languages described in
the technical report .
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).
Implemented by Rüdiger Reischuk and Semen Gehman.
Last change: 6. Oktober 1998