This page contains implementations of two algorithms presented in the technical report [1] and ALT '97 paper [2].

All algorithms on this page deal with **one-variable patterns**.
Note that the symbol **x** is
reserved to denote the pattern variable.
Any other symbol may be used for the constants. For example,

and

are one variable patterns. The language generated by a pattern is the set
of all strings of constant symbols that can be obtained from the pattern
by substituting non-empty strings for the pattern varible **x**.
For example, substituting **x** by **gag**
gives

and

for the first and second pattern displayed above, respectively.

The first algorithm (Algorithm 2 in the paper) computes a *descriptive
pattern*. The input is a sample consisting of several strings from
the target language.
You can enter the sample in the following text area using one
line for each string.

If you press the button labeled ``Learn''
the algorithm answers with
a *descriptive* one-variable pattern.

The next algorithm learns a one-variable pattern by asking *superset
queries* (Algorithm Q in the paper). Here you think of a one-variable
pattern and then answer *superset queries* posed by the algorithm.

The algorithm presents a pattern *p* and you have to answer
*yes* if the language generated by your pattern is contained in
the language generated by *p*. Otherwise you have to answer *no*.

If you answer *no* the algorithm may ask you for a counterexample.
In that case you are asked to enter a string (in the last row)
that is contained in the
language of your pattern, but not in the language of *p*.
Finish your input by pressing "Return" on your keybord.

For your assistance, the following algorithm decides whether or
not the pattern queried by our superset algorithm generates
a *superset* of your target pattern.
Just input your target pattern (first row, left) and the query pattern
(first row, right) provided by the applet above (you may just paste it).
Before input the next query pattern, please click *clear Query*.
Also, you receive a counterexample, if the query pattern
does not generate a superset which you may just paste into the last
row of the applet above (don't forget to finish your input by
pressing ``Return'').

For example, let aa be the target pattern. The 1st query is 0,
and you answer it by clicking *No*. The applet below
provides the counterexample aa. The 2nd query is ax, and
the applet below tells you to answer it by clicking *Yes*.
Now you get the 3rd query, i.e., aax, and
the applet below tells you to answer it by clicking *No*.
Finally, you get the query aa, which obviously has to be answered
by clicking *Yes*.

**1**-
T. Erlebach, P. Rossmanith, H. Stadtherr, A. Steger, and T. Zeugmann.
Efficient learning of one-variable pattern languages from positive
examples.
DOI Technical Report DOI-TR-128, Department of Informatics, Kyushu
University, December 1996.
[gzipped Postscript]
**2**-
**T. Erlebach, P. Rossmanith, H. Stadtherr, A. Steger, and T. Zeugmann,**Learning One-Variable Pattern Languages Very Efficiently on Average, in Parallel, and by Asking Queries,*in*``Proc. 8th International Workshop on Algorithmic Learning Theory - ALT'97,'' (M. Li and A. Maruoka, Eds.), Lecture Notes in Artificial Intelligence 1316, pp. 260 - 276, Springer-Verlag 1997. Abstract

Peter Rossmanith, and Thomas Zeugmann

last change December 10, 2010