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).
Last change: 2. November 1998
Implemented by
Rüdiger Reischuk and Semen Gehman.