Learning One-Variable Patterns Efficiently via Computing Descriptive Patterns and by Asking Queries

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.

Bibliography

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