Authors: John Case, Sanjay Jain, Rüdiger Reischuk, Frank Stephan
and Thomas Zeugmann
Theoretical Computer Science, Vol. 364, Issue 1, 2006, 115-131. |
(Special Issue Algorithmic Learning Theory (ALT 2003)).
An algorithm for learning a subclass of erasing regular
pattern languages is presented.
On extended regular pattern languages generated by patterns
π of the form
x0 α1x1 ... αmxm,
where x0, ..., xm are variables and
α1, ..., αm
strings of terminals of length c each,
it runs with arbitrarily high probability of success
using a number of examples polynomial in m (and exponential in c).
It is assumed that m is unknown, but c is known and that
samples are randomly drawn according to some distribution,
for which we only require that it has certain natural and plausible
Aiming to improve this algorithm further we also explore computer
simulations of a heuristic.
Keywords: Learning theory; Inductive inference; Regular pattern languages,
Learning from examples; Probabilistically exact learning
©Copyright 2006, Elsevier Science B.V.