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 to compute descriptive one-variable patterns requires time O(n⁴log n) (cf. Angluin, 1980).

Second, we give a parallel version of this algorithm requiring time O(log n) and O(n³/log n) processors on an EREW-PRAM.

Third, we devise a one-variable pattern learner 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 D with expected string length l. 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 expected 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 patterns to learn one-variable patterns with a polynomial number of superset queries with respect to the one-variable patterns as query language.