Learning k-Variable Pattern Languages Efficiently Stochastically Finite on Average from Positive Data

The present paper deals with the average-case analysis of the Lange-Wiehagen (1991) algorithm learning the class of all pattern languages in the limit from positive data. Let A = f0; 1; : : :g be any non--empty finite alphabet containing at least two elements. Furthermore, let X = fx i i 2 Ng be an infinite set of variables such that A " X = ; . Patterns are non-empty strings over A[X . L(ß) , the language generated by pattern ß is the set of strings which can be obtained by substituting non-null strings from A 3 for the variables of the pattern ß . The Lange-Wiehagen (1991) algorithm is analyzed with respect to its total learning time, i.e., the overall time taken by the algorithm until convergence. The expectation of the total learning time is carefully analyzed and exponentially shrinking tail bounds for it are established for a large class of probability distributions. For every pattern ß containing k different variables it is shown that Lange and Wiehagen's algorithm posses..