Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries

A pattern is a finite string of constant and variable symbols. The language generated by a pattern is the set of all strings of constant symbols which can be obtained from the pattern by substituting non-empty strings for var iables. We study the learnability of one-variable pattern languages in the limit with respect to the update time needed for computing a new single hyp othesis and the expected rotal learning rime taken until convergence to a c orrect hypothesis. Our results are as follows. First, we design a consisten t and set-driven learner that, using the concept of descriptive patterns, a chieves update time O(n(2)/logn), where n is the size of the input sample. The best previously known algorithm for computing descriptive one-variable patterns requires time O(n(4)/logn) (cf. Angluin, J. Comput. Systems Sci. 2 1(1) (1980) 46-62). Second, we give a parallel version of this algorithm th at requires time O(logn) and O(n(3)/logn) processors on an EREW-PRAM. Third , using a modified version of the sequential algorithm as a subroutine, we devise a learning algorithm for one-variable patterns whose expected total learning time is O(t(2)logl) provided the sample strings are drawn from the target language according to a probability distribution with expected stri ng length l. The probability distribution must be such that strings of equa l length have equal probability, but can be arbitrary otherwise. Thus, we e stablish the first algorithm for learning one-variable pattern languages ha ving an expected total learning time that probably differs from the update time by a constant factor only. Finally, we show how the algorithm for desc riptive one-variable patterns can be used for learning one-variable pattern s with a polynomial number of superset queries with respect to the one-vari able patterns as query language. (C) 2001 Elsevier Science B.V. All rights reserved.