# Average-Case Optimal 1-Variable Pattern Learner

## Implementation for Interactive Learning

This page presents an implementation of an average case optimal learning algorithm for 1-variable pattern languages described in the technical report [1] and, in more polished form, in [3].
First, you may wish to see an animation of the algorithm (if you still use netscape 4.x, please click here).

## Outline of the Algorithm

Receiving a sequence of example 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,

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).

If You see this text, Your Browser doesn't support Java-Applets

You may also test a modified version of this algorithm with faster convergence in case of highly symmetric sample strings.

#### Bibliography

1. Rüdiger Reischuk and Thomas Zeugmann
Learning One-Variable Pattern Languages in Linear Average Time.
Technical Report DOI-TR-140, Department of Informatics, Kyushu University, Fukuoka, Japan, September 1997.
[Abstract] [Full Paper].
2. R. Reischuk and T. Zeugmann, Learning One-Variable Pattern Languages in Linear Average Time, in ``Proc. 11th Annual Conference on Computational Learning Theory - COLT'98,'' July 24th - 26th, Madison, pp. 198 - 208, ACM Press 1998.
[Abstract] [Full Paper].
3. R. Reischuk and T. Zeugmann, An Average-Case Optimal One-Variable Pattern Language Learner, Journal of Computer and System Sciences Vol. 60, No. 2, 2000, 302-335. (Special Issue for COLT'98). [Abstract] [Full Paper].

Back to my Homepage

Implemented by Semen Gehman and Rüdiger Reischuk, and Thomas Zeugmann

Last change: November 1, 2004