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

Abstract. A pattern is a string of constant and variable symbols. The language generated by a pattern pi is the set of all strings of constant symbols which can be obtained from pi by substituting non-empty strings for variables. We study the learnability of one-variable pattern languages in the limit with respect to the update time needed for computing a new single guess and the expected total learning time taken until convergence to a correct hypothesis. The results obtained are threefold. First, we design a consistent and set-driven learner that, using the con-cept of descriptive patterns, achieves update time O(n2 logn), where n is the size of the input sample. The best previously known algorithm to compute descriptive one-variable patterns requires time O(n4 logn) (cf. Angluin [1]). Second, we give a parallel version of this algorithm re-quiring time O(logn) and O(n3 / logn) processors on an EREW-PRAM. Third, we devise a one-variable pattern learner whose expected total learning time is O(`2 log `) provided the sample strings are drawn from the target language according to a probability distribution D with ex-pected string length `. The distribution D must be such that strings of equal length have equal probability, but can be arbitrary otherwise. Thus, we establish the first one-variable pattern learner having an ex-pected total learning time that provably differs from the update time by a constant factor only. Finally, we apply the algorithm for finding descriptive one-variable pat-terns to learn one-variable patterns with a polynomial number of superset queries with respect to the one-variable patterns as query language. 1