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