Lange and Wiehagen's pattern language learning algorithm: An average-case analysis with respect to its total learning time |
| |
Authors: | Thomas Zeugmann |
| |
Affiliation: | (1) Department of Informatics, Kyushu University, Kasuga 816-8580, Japan |
| |
Abstract: | The present paper deals with the best-case, worst-case and average-case behavior of Lange and Wiehagen's (1991) pattern language
learning algorithm with respect to its total learning time. Pattern languages have been introduced by Angluin (1980) and are
defined as follows: Let
be any non-empty finite alphabet containing at least two elements. Furthermore, let
be an infinite set of variables such that
. Patterns are non-empty strings over
. L(π), the language generated by pattern π, is the set of strings which can be obtained by substituting non-null strings from
for the variables of the pattern π. Lange and Wiehagen's (1991) algorithm learns the class of all pattern languages in the
limit from text. We analyze this algorithm with respect to its total learning time behavior, i.e., the overall time taken
by the algorithm until convergence. For every pattern π containing k different variables it is shown that the total learning time is
in the best-case and unbounded in the worst-case. Furthermore, we estimate the expectation of the total learning time. In
particular, it is shown that Lange and Wiehagen's algorithm possesses an expected total learning time of
with respect to the uniform distribution.
This revised version was published online in June 2006 with corrections to the Cover Date. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|