First, we design a consistent and set-driven learner that, using the concept of descriptive patterns, achieves update time O(n²log n), where n is the size of the input sample. The best previously known algorithm for computing descriptive one-variable patterns requires time O(n⁴log n) (cf. Angluin, 1980). Second, we give a parallel version of this algorithm that requires time O(log n) and O(n³/log n) 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(l²log l) provided the sample strings are drawn from the target language according to a probability distribution with expected string length l. The probability distribution must be such that strings of equal length have equal probability, but can be arbitrary otherwise. Thus, we establish the first algorithm for learning one-variable pattern languages having an expected total learning time that provably differs from the update time by a constant factor only.

Finally, we show how the algorithm for descriptive one-variable patterns can be used for learning one-variable patterns with a polynomial number of superset queries with respect to the one-variable patterns as query language.