An Average Case Optimal 1-Variable Pattern Language Learning Algorithm
Implementation for Interactive Learning, Faster Version
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
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.
Back to my Homepage
Implemented by S. Gehman and Rüdiger Reischuk.
Last change November 1, 2004.