#
Algorithmic Learning Theory

### Research:

Algorithmic Learning Theory investigates what concepts can be learned
depending on the model of learning, of which there are a lot.
In this project, the emphasis is not on whether or not a concept is
learnable, but on how fast. The speed of learning can be measured in
different ways. The following two examples consist of two learning
algorithms. The first one learns from positive examples and the
second from queries.
Both algorithm learn one-variable patterns. A one-variable pattern
is a word that can also contain the variable symbol *x*.
E.g., *bxabxaa* is a one-variable pattern. The language
generated by a one-variable pattern consists of all words you get when
you substitute a non-empty word for the variable symbol in the
pattern. The language of *bxabxaa* contains, e.g., the word
*bbababbabaa*, which you get by substituting *bab* for *x*.

One-variable pattern languages are a very simple class and are well
suited to serve as an example of a learnable concept.

### Learning from positive examples

The first algorithm computes a descriptive pattern.
It is known that descriptive patterns converge to the correct pattern.
The input is a sample consisting of several strings.
You can enter the sample in the following text area using one
line for each string.
If you provide enough examples, you will get the correct answer
eventually.

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

### Learning from queries

The next algorithm learns a one-variable pattern with superset
queries. 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 that is contained in the
language of your pattern, but not in the language of *p*.

### Publications:

###
Links to Related Sites: