An Average Case Optimal 1-Variable Pattern Language Learning AlgorithmImplementation for Interactive Learning, Faster VersionThis page contains the implementation of a variant of an algorithm presented in the technical report [1] and, in more polished form, in the article [1]. First, you may wish to see an animation of this variant of the algorithm (if you still use netscape 4.x, please cclick here). Receiving a sequence of example strings from an unknown 1-variable pattern language the algorithm computes a sequence of hypotheses that explain the examples seen so far. 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). To test the algorithm choose a 1-variable pattern like
where a,b,c,d,...
denote single letters (the constants) and
x the pattern variable.
Each example 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).
This is a version with faster convergence.
Bibliography
Back to my Homepage
Implemented by S. Gehman and Rüdiger Reischuk.
Last change November 1, 2004. |