Abstract

1. Introduction
Patterns are a very natural way to define formal languages. Suppose you are interested in the language of all strings over the alphabet A = {0,1} starting with 11, ending with 010, and containing the substring 01011 somewhere, but may be otherwise arbitrary. Thus, all strings in your language follow the pattern π 1 = 11 x 01011x 1010, provided you are willing to allow the variables x 0 , x 1 to be substituted by any string over {0,1} including the empty one. As for another example, consider the set of all strings having even length 2n such that the prefix of length n is identical to the suffix starting at position n + 1. In that case, the wanted language follows the pattern π2 = xoxo. Though patterns have already been considered since the beginning of this century (cf., e.g., Thue [28], and Bean et al. [5]), the formal introduction of patterns and pattern languages goes back to Angluin [2]. Since then, pattern languages and variations thereof have been widely investigated (cf., e.g., Salomaa [21, 22], and Shinohara and Arikawa [26] for an overview). This continuous interest in pattern languages has several reasons, among them the learnability in the limit of the class of all pattern languages from positive data (cf. An- gluin [2, 3]). Gold [8] introduced the corresponding learning model. Let L be any formal language; then a text for L is any infinite sequence of strings that contains eventually all the strings of L, and nothing else. The information given to the learner are successively growing initial segments of a text. Processing these segments, the learner has to output hypotheses about the target language L. Thereby the hypotheses are chosen from a pre- specified set of admissible hypotheses called hypothesis space. Additionally, the sequence of hypotheses has to converge to a hypothesis correctly describing the target language (cf. Definition 1). For pattern languages, the relevant hypothesis space is the set of all patterns. In partic- ular, Angluin [2] showed the pattern languages to be learnable in the limit by outputting so-called descriptive patterns (see below) as hypotheses. This approach has several advan- tages, since the resulting hypotheses are consistent, and the resulting learning algorithm is set-driven. Here consistency means that the hypothesis correctly and completely reflects the information provided so far. A learner is said to be set-driven provided its output depends exclusively on the range of its input. In general, consistency and set-drivenness considerably limit the learning capabilities (cf., e.g., Zeugmann and Lange [34]). On the other hand, this approach has also a major disadvantage, since no efficient algorithm is known for computing descriptive patterns, and finding a descriptive pattern of maximum possible length is known to be NP-complete. Therefore, it is unlikely that there exists a polynomial-time algorithm for computing a descriptive pattern as hypothesis. Consequently, it is only natural to ask whether efficient learning algorithms for pattern languages can benefit from the concept of descriptive patterns at all. For answering this question, several authors looked at special cases. For example, one can add the require- ment that every variable appears at most once in the pattern. Such patterns are called regular, since the languages they generate are regular. For example, pattern πι above is regular while pattern π 2 is not. Computing descriptive patterns for regular pattern languages can be done in polynomial time (cf. Shinohara [24, 25]). Further examples comprise the non-cross pattern languages as well as the class of unions of at most k regu- lar pattern languages, where k is a priori fixed (cf., e.g., [26]).  Another natural restriction is obtained by a priori bounding the number k of different variables that are allowed to occur in a pattern. Such patterns are called k-variable patterns. For example, π 1 above is a 2-variable pattern while π 2 is a one-variable pattern. However, to our knowledge it is still unknown whether polynomial-time algorithms exist that compute descriptive k-variable patterns for any fixed k > 1. (Compare with [11, 16, 12].) Therefore, Lange and Wiehagen [17] have considered learners that are allowed to output inconsistent guesses until enough shortest strings of the target pattern language have been provided. Their algorithm achieves polynomial update time. Moreover, it is still set-driven (cf. [33]), and outperforms Angluin's [2] algorithm with respect to its storage requirements, since it is iterative. That is, it is computing its current guess from its previously made one, and the next input string. Nevertheless, what really counts in practical applications is not just the time for com- puting a single guess, but the overall time needed by the learner until convergence. We re- fer to this time as the total learning time. On the one hand, it is easy to show that the total learning time is unbounded in the worst case, while in the best case [log 1,4] ( | A | + k − 1) ] + 1 many strings are sufficient to achieve convergence (here k denotes the number of different variables in the target pattern, and [A] the alphabet size) (cf. Zeugmann [33]). Therefore, we are mainly interested in the average or expected total learning time. Unfortunately, the expected total learning time of Lange and Wiehagen's [17] algorithm was shown to be exponential in the number of different variables occurring in the target pattern (cf. [33]). Throughout the present paper we consider the special case of one-variable target pat- terns. In the case of one-variable pattern languages, a polynomial-time algorithm for computing descriptive patterns has been known for a long time. It has running time O(n 4 log n) for inputs of size n and was presented by Angluin [2]. She was aware of pos- sible improvements of the running time only for certain special cases, and she hoped that further study would provide insight for a uniform improvement. We obtain such a uniform improvement by presenting an algorithm that computes a descriptive one-variable pattern in only O(n² log n) steps (Section 2). In addition, we show that our algorithm can be par- allelized efficiently, using O (log n ) time and O ( n ³ / log n ) processors on an EREW-PRAM (Section 3). Previously, it was not known whether there exist efficient parallel algorithms for learning one-variable pattern languages. Moreover, we use a modified version of the sequential algorithm as a subroutine in order to devise a learning algorithm for one-variable patterns whose expected total learning time is O(ℓ² log ℓ) if the sample strings are drawn from the target language according to a probability distribution with expected string length ℓ. The probability distribution must be such that strings of equal length have equal probability, but can be arbitrary otherwise (cf. Section 4). Finally, we turn our attention to active learning. In contrast to the model described above, now the learner gains information concerning the target object by asking questions to an oracle (cf. Definition 3). In particular, 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, i.e., by asking questions of the form “L(τ)ニL(π)?,” where π is the pattern to be learned and τ is an arbitrary one-variable pattern. The number of queries asked by our algorithm is polynomial (cf. Section 5).  A different algorithm that learns arbitrary pattern languages with a polynomial number of superset queries is known (cf. [4]), but that algorithm uses patterns with more than one variable in its queries even when the pattern to be learned is a one-variable pattern. Finishing this section, we would like to mention that learning of pattern languages has also been investigated in Valiant's [29] probably approximately correct (PAC) learning model. Here, the learner has access to a random source of positive and negative examples and must produce in polynomial time with high probability a pattern which is consistent with nearly all future positive and negative examples from the source. Schapire [23] has shown that it is highly unlikely that general pattern languages can be learned in this model. On the other hand, Kearns and Pitt have shown that under certain assumptions k-variable pattern languages can be learned in this model for any fixed k (cf. [15]). The paper is structured as follows. Subsection 1.1 formally defines the pattern lan- guages and some additional preliminaries. The different learning models considered in this paper are introduced in Subsection 1.2. Next, we present our improved sequential algorithm for finding one-variable descriptive patterns (cf. Section 2). Its efficient paral- lelization is outlined in Section 3. In Section 4 we provide the announced average-case analysis concerning the expected total learning time of our resulting learning algorithm. Finally, we study the learnability of one-variable pattern languages from superset queries (cf. Section 5), and discuss the results obtained (cf. Section 6).
1.1. The Pattern Languages
Let IN = {0, 1, 2, . . .} be the set of all natural numbers, and let IN+ = IN \ {0}. For all real numbers x we define [x], the floor function, to be the greatest integer less than or equal to x. Patterns and pattern languages are defined as follows (cf. [2]). Let A = {0,1,...} be any non-empty finite alphabet containing at least two elements. By A* we denote the free monoid over A (cf. Hopcroft and Ullman [9]). The set of all finite non-null strings of symbols from A is denoted by A+, i.e., A+ = A* \ {ε}, where ε denotes the empty string. By |A| we denote the cardinality of A. Furthermore, let X = {xi | i ∈ IN} be an infinite set of variables such that A N X = 0. Patterns are non-empty strings over A U X , e.g., 01, 0x0111, 1x0x00x1x2x0 are patterns. The length of a string s ∈ A* and of a pattern π is denoted by |s| and |π|, respectively. By Pat we denote the set of all patterns. Let π ∈ Pat, 1 ≤ i ≤ |π|; we use π(i) to denote the i-th symbol in π, e.g., 0 x o 111(2) = x 0 , and 0x 0111(5) = 1. If π(i) ∈ A , then we refer to π(i) as a constant; otherwise π(i) ∈ X, and we refer to π(i) as a variable. Analogously, we use s(i) to denote the i-th symbol in a string s ∈ A+ for all i = 1, . . , |s|.  By #var(π) we denote the number of different variables occurring in π, and by # π; (π) we denote the number of occurrences of variable xi in π. If #var(π) = k, then we refer to π as a k-variable pattern. Let k ∈ IN, by Patk we denote the set of all k-variable patterns. In the case k = 1 we conventionally denote the variable occurring by x, i.e., we omit its index. Furthermore, if # x,(π) = 1 for all variables occurring in pattern π , then we call π a regular pattern. Now let π ∈ Patk, and let uo, . . , uk-1 ∈ A+. We denote by π[uo/xo, . . , uk-1/xk-1] the string s ∈ A+ obtained by substituting uj for each occurrence of xj, j = 0, . . , k − 1, in the pattern π. The tuple ( u 0 , . . , U k –1 ) is called substitution. For every π ∈ Pat k we define the language generated by pattern π by L(π) = {π[u0/x0,...,uk-1/xk-1] ↑ u0,...,uk-1 E A+}1. By PAT k we denote the set of all k-variable pattern languages. Finally, PAT = Ukein PATk denotes the set of all pattern languages over A. From the viewpoint of formal language theory the class of pattern languages has sev- eral interesting properties. First, it is incomparable with the class of regular languages and the class of context-free languages (cf. [2]). Second, it is not closed under union, com- plement, intersection, Kleene closure, homomorphism, or inverse homomorphism. But it is closed under concatenation and reversal. Furthermore, it is one of the rare examples of a class of languages where the equivalence problem is easily decidable but the inclu- sion problem is undecidable (cf. [13]).  One reason why one-variable pattern languages are more interesting for practical purposes than general pattern languages is that several problems are decidable or even efficiently solvable for one-variable pattern languages but undecidable or NP-complete for general pattern languages. For example, in the case of general pattern languages the word problem is NP-complete (cf. [2]) and the inclusion problem is undecidable (cf. [13]), but both problems are decidable in linear time for one- variable pattern languages. On the other hand, PAT 1 is still incomparable to the regular and context free languages. In the remaining sections of this paper, we will be mainly concerned with one-variable patterns and their languages. A finite set S = {so,s1,...,sr} ⊆ A+ of strings is called a sample. A pattern π is consistent with a sample S if S ⊆ L(π). In order to formalize the notion of when a pattern is a concise description of a given sample S, a (one-variable) pattern π is called descriptive for S if it is consistent with S and there is no other consistent (one-variable) pattern τ such that L(T) ⊂ L(π). Angluin [2] showed that any consistent one-variable pattern of maximum length is descriptive, except for the trivial case when the sample consists of a single string only.
1.2. Learning and Inductive Inference
Pattern languages have been introduced originally in the context of inductive infer- ence.  Research on inductive inference is concerned with formalizing and analyzing the process of gradually learning concepts from successively larger sets of examples. Fre- quently, the concepts are taken to be formal languages (cf., e.g., Osherson et al. [20], Zeugmann and Lange [34]). In this case, a distinction is made between learning from informant and learning from text. If L is the language to be identified, every sequence i = (s 0, b 0), (s 1, b 1), (s 2, b 2), . . . with b j ∈ {+, −} for all j ∈ N satisfying {s j ∈ j ∈ N} = L. That is, every string over the relevant alphabet is classified as to whether it be- longs to L or not. Furthermore, every infinite sequence t = ( sj )jEIN of strings such that range(t) = {sj�j E IN} = L is said to be a text for L, or, synonymously, a positive presentation.  By Text(L) we denote the set of all texts for L.  Furthermore, let t be a text, and let n ∈ IN. We set t n = s 0 , . . , s n , and we refer to t n as the initial segment of t of length n + 1. Moreover, we define t to denote the range of t n , i.e., t t = { s j | 0 ≤ i ≤ n }. As in Gold [8], we define an inductive inference machine (abbr. IIM) to be an algo- rithmic device which works as follows: The IIM takes as its input larger and larger initial segments of a text t and on every input it first outputs a hypothesis, i.e., a pattern, and then it requests the next input. DEFINITION 1. PAT is called learnable in the limit from text iff there is an IIM M such that for every L ∈ PAT and every t ∈ Text(L), (1) for all n ∈ IN, M(tn) is defined, (2) there is a pattern π ∈ Pat such that L(π) = L and for almost all n ∈ IN, M(t,) = π. The learnability of the one-variable pattern languages is defined analogously by replac- ing PAT and Pat by PAT 1 and Pat 1 , respectively. The pattern languages as well as the class of all one-variable pattern languages consti- tute an indexable class L of uniformly recursive languages. That is, there are an effective enumeration L 0 , L 1 , L 2 , . . . of all and only the languages in L and a recursive function f such that for all j ∈ IN and all strings s ∈ A* we have
In the following we refer to indexable classes with uniformly decidable membership as indexable classes for short. Note that Definition 1 is a bit sharper than the usual definition of learnability in the limit. The point here is that in our definition the IIM is requested to output on every input a pattern as hypothesis, while in the general case, the IIM is allowed to request the next input without making any guess. IIMs behaving thus are called responsive. Throughout this paper, we exclusively deal with responsive IIMs. Angluin [3] gave sufficient and necessary conditions for indexable classes of languages being inferable from text (not necessarily responsively). In particular, she proved that an inference machine that always outputs as its hypothesis a pattern which is descriptive for the input read so far responsively infers all pattern languages (cf. [2]). This approach has another advantage, since it results in a set-driven learner. Set-drivenness has been introduced by Wexler and Culicover [30], and is defined as follows. DEFINITION 2. Let L be any indexable class. An IIM is said to be set-driven with respect to L iff its output depends only on the range of its input; that is, iff M(t x ) = M(iy) for all x, y ∈ IN and all texts t, ˆ f ∈ U L ∈ L Text(L) provided t ‡ = f † Note that in general one cannot expect to learn set-drivenly. For more information concerning this subject the reader is referred to Lange and Zeugmann [18]. When dealing with set-driven learners, it is technically advantageous to describe them in dependence of the relevant set t, obtained as input instead of the initial segments t, usually fed to an IIM. We refer to these sets as samples in accordance with the def- We set inition made above. Now, let t = s 0 , s 1 , . . . be any text, and let m ∈ IN. n = ∑ j =0 | s j |, and refer to n as the input length of the initial segment t m. Analogously, let S = {so,s1,...,sr} be a sample. Then we set n = ∑j=0 |sj|, and refer to n as the input length of sample S Furthermore, we mainly deal with the time complexity of the pattern learning al- gorithms considered throughout this paper.  Except in Chapter 3, where we use the PRAM-model, we assume the same model of computation and the same representation of patterns as Angluin [2], i.e., in particular a random access machine that performs a reasonable menu of operations each in unit time on registers of length O(log n ) bits, where n is the input length. The inputs are read via a serial input device, and reading a string of length n is assumed to require n steps. Moreover, we aim at both determining the update time and the total learning time which we define next. Let M be any IIM. Then, for every L ∈ PAT and t ∈ Text(L), let Conv( M, t) = the least number m such that for all n ≥ m, M(t,) = M(t,,) denote the stage of convergence of M on t. Moreover, by TM(tn) we denote the time to compute M(tn), and we refer to TM(tn) as the update time of M. Furthermore, the total learning time taken by the IIM M on successive input t is defined as
Finally, we describe the model of active learning mentioned in the introduction we want to deal with, i.e., learning via queries. The objects to be learned are the elements of a prespecified indexable class L defined over some alphabet A. Additionally, we assume an indexable class H again defined over A as well as a fixed effective enumeration ( h j ) j ∈ N of it as hypothesis space for L. Clearly, H must comprise L. A hypothesis h is said to describe a target language L iff L = h, i.e., for all s ∈ A*, s ∈ h iff s ∈ L. The source of information about the unknown target L are queries to an oracle. Following Angluin [4] we distinguish membership, equivalence, subset, superset, and disjointness queries. Input to a membership query is a string s, and the output is yes if s ∈ L and no otherwise. As for the other queries, the input is an index j and the output is yes if L = hj (equivalence query), hj ⊆ L (subset query), L ⊆ hj (superset query), and L ∩ hj = ∅ (disjointness query), and no otherwise. If the answer is no, additionally a counterexample is returned, i.e., a string s ∈ L△hj (the symmetric difference of L and hj ), s ∈ hj \ L, s ∈ L \ hj, and s ∈ L ∩ h j , respectively. Throughout this paper we always assume that all queries are answered truthfully. DEFINITION 3 (Angluin [4]). Let L be any indexable class and let H be a hypothesis space for it.  A learning algorithm exactly identifies a target L E L with respect to H with access to a certain type of queries if it always halts and outputs an index j such that L = h j Besides the source of information, there is another major difference to Definition 1. That is, now the learner is allowed only one guess, and that hypothesis must be correct. The complexity of a query learner is measured by the total number of queries to be asked in the worst-case.
An Improved Sequential Algorithm
2.
In this section we present an algorithm that computes a descriptive one-variable pattern for a given sample. The input to the algorithm is a sample S, S = { S0, S1, . . , Sr-1}, of r non-empty strings over A. Without loss of generality, we assume that so is the shortest string in S. Our algorithm runs in time O(n | s 0 | log | s 0 |) and is simpler and much faster than the original algorithm by Angluin [2], which needs time O(n2|so|2 log |so|). Recall that n denotes the input length of S. Angluin's [2] algorithm computes explicitly a representation of the set of all consistent one-variable patterns for S . This requires a tricky data structure which can represent exponentially many patterns in polynomial space. In order to get a faster algorithm we avoid to represent all consistent patterns, but rather work with a polynomial-size subset thereof. Before we describe our algorithm in detail, we need to review and to establish a few basic properties of one-variable patterns and the languages generated by them. LEMMA 1 (Angluin [2], Lemma 3.9). Let τ ∈ Pat, and let π ∈ Pat 1 . Then L( τ ) ⊆ L( π ) if and only if τ can be obtained from π by substituting a pattern ρ ∈ Pat for x. For a pattern π to be consistent with S, there must be strings α 0, . . . , α r -1 ∈ A + such that si can be obtained from π by substituting αi for x, for all 0 ≤ i ≤ r − 1. Given a consistent pattern π, the set {α 0 , . . . ,α r -1} is denoted by α( S, π ). Furthermore, a sample S is called prefix-free if | S | > 1 and no string in S is a prefix of all other strings in S . LEMMA 2. If S is a prefix-free sample then there exists a descriptive pattern π ∈ Pat 1 for S such that at least two strings in α(S,π) start with a different symbol. Proof. Let u denote the longest common prefix of all strings in S. The pattern ux is consistent with S because u is shorter than every string in S, since S is prefix-free. Consequently, there exists a descriptive pattern π ∈ Pat 1 for S with L(π) ⊆ L(ux). Now, by Lemma 1 we know that there exists a pattern Q E Pat 1 such that π = ux [ Q /x ] . Since u is a longest common prefix of all strings in S , we can conclude Q (1) & A . Hence, Q = xt for some τ ∈ Pat 1 ∪ {ε}, and at least two strings in α( S, uxτ ) must start with a different symbol. Let Cons(S) = {π l π ∈ Pat 1 , S ⊆ L(π), ∃ i, j [i ≠ j, α i, α j ∈ α(S,π), α i (1) ≠ α j (1)]}, i.e., Cons(S) is the set of all consistent patterns π for S such that at least two strings in α( S, π ) start with a different symbol. Note that Cons( S ) is in general only a subset of all patterns that are consistent with S, and that Cons(S) = 0 provided S is not prefix-free. LEMMA 3. Let S be any prefix-free sample. Then Cons(S) ≠ 0, and every pattern π ∈ Cons(S) of maximum length is descriptive for S. Proof. Let S be prefix-free.  According to Lemma 2 there exists a descriptive pattern for S belonging to Cons(S); thus Cons(S) ≠ ∅. Now, suppose there is a pattern π ∈ Cons(S) of maximum length which is not descriptive for S . Thus, S ⊆ L(π), and, moreover, there Hence, by exists a pattern τ ∈ Pat 1 such that S ⊆ L(τ) as well as L(τ) ⊂ L(π). Lemma 1 we know that 7 can be obtained from 7 by substituting a pattern 0 for x. Since at least two strings in α( S, π ) start with a different symbol, we immediately get Q(1) E X. Moreover, at least two strings in a(S,T) must also start with a different symbol. Hence τ ∈ Cons(S) and ρ = xv for some pattern ν. Note that |ν| ≥ 1, since otherwise τ = π[ ρ/x] = π contradicting L(τ) ⊂ L(π). Finally, by |ν| ≥ 1, we may conclude |τ| > |π|, a contradiction to π having maximum length. Thus, no such pattern τ can exist, and hence, π is descriptive. Note that the lemma above does heavily depend on the restriction to one-variable patterns. For example, let S = {111000,000111}. Obviously, S is prefix-free, and there is only one consistent pattern π ∈ Pat 1 , i.e., x . On the other hand, if we drop the restriction to exclusively consider elements from Pat 1 , we may take xoxoxoxixixi as a descriptive pattern. Next, we explain how to deal with samples that are not prefix-free. First, the algorithm checks whether the input sample consists of a single string s. If this is the case, it simply outputs s as a descriptive pattern and terminates. Otherwise, it checks whether so is a prefix of all other strings s 1 , . . , s r -1. If this is the case, the algorithm outputs ux ∈ Pat 1 , where u is the prefix of s 0 of length | s 0 | — 1, and terminates. Obviously, S ⊆ L ( ux ). Suppose there is pattern τ such that S ⊆ L(τ), and L(τ) ⊂ L(ux). Then we may again apply Lemma 1, i.e., there must be a pattern e such that τ = ux[e/x]. But this immediately implies ρ = x, since otherwise |τ| > | s 0 |, and thus, S C L(τ). Consequently, ux is descriptive. In all other cases | S | contains at least two strings and s 0 is not a prefix of all other strings in the sample. Hence, | S | is prefix-free and Lemma 3 applies. Therefore, it is sufficient to find and output a longest pattern in Cons( S ). In the rest of this section we will show how this can be done efficiently. The observation that leads to an improved algorithm for prefix-free samples is that the number of patterns in Cons(S) is bounded by a small polynomial, as we show next. Let k, l ∈ IN, k > 0; we call patterns with k occurrences of x and l occurrences of constants (k,l)-patterns. Note that a (k,l)-pattern has length k + l. Furthermore, every pattern π ∈ Cons( S ) satisfies |π | ≤ |s 0 |, since we exclusively consider non-erasing substitutions. Obviously, there can only be a (k, l)-pattern in Cons(S) if there is a positive integer m o satisfying | so | = km 0 + l. Clearly, m 0 refers to the length of the string substituted for the occurrences of x in the relevant ( k, l )-pattern to obtain s 0 . Thus, for m 0 = 1 there are |s 0 | many possible pairs ( k, l ) such that k + l = |s 0 |. For m 0 = 2, the number l must satisfy 0 ≤ l = | s 0 | — 2k, hence there are at most [| s 0 |/2] many possible pairs (k, l ) with |s 0 | = 2k + l, and so on. Therefore, there are at most [|s 0 |/k | possible values of l for a fixed value of k . Hence, the number of possible (k,l)-pairs for which (k,l)-patterns can exist in Cons(S) is bounded by
The algorithm considers all possible ( k, l )-pairs in turn.  We describe the algorithm for one specific (k, l)-pair. If there is a (k, l)-pattern π ∈ Cons(S), the lengths m, of the strings α ; ∈ α( S , π ) must satisfy m ; = (| s i | − l ) /k . In addition, it is clear that α ; is simply the substring of si of length mi starting at the first position d where the input strings differ.  If ( | s i | — l )/k is not integral for some i, then there is no consistent (k, l )-pattern and the algorithm does not need to perform any further computation for this particular (k,l)-pair. The following lemma shows that the (k,l)-pattern in Cons(S) is unique, if it exists at all. LEMMA 4. Let S = { so , . . , sr-1} be any prefix-free sample. For every given (k, l)-pair, there is at most one (k, l)-pattern in Cons(S). Proof. Let u be the longest common prefix of the strings in S, possibly u = ε. All patterns in Cons(S) start with ux. Thus, if | u | > l there cannot be any (k,l)-pattern in Cons(S).  Now, assume |u| ≤ l.  If ( |s i | − l ) /k is not integral for some i, there is again no ( k, l )-pattern in Cons ( S ). Otherwise, we show by induction on j that the j-th symbol in a (k, l)-pattern π ∈ Cons(S) is unique, or there is no such pattern π. Note that all α i and m i are already determined by the (k, l)-pair. Obviously, the hypothesis is true for 1 ≤ j ≤ |u| + 1. Let us assume that the first j — 1 symbols of π are already fixed and contain b ≤ k variables and c ≤ l constants so far. For each i, the prefix of si corresponding to the first j — 1 symbols of π has length bmi + j — 1 — b. If all strings si have the same symbol a ∈ A in position bmi + j — b, the j-th symbol of π must be α. In that case, the candidate pattern is extended by α, and c := c + 1. If all strings si have the symbol α i (1) in position bmi + j − b, the j − th symbol of π must be x, and another occurrence of x has been detected. Thus, the candidate pattern is extended by x, and b := b + 1. If none of the two conditions holds, there is no (k,l)-pattern in Cons(S). Otherwise, the candidate pattern π is uniquely determined. Now, three cases are possible. First, c > l, i.e., more than l constants occur in the candidate pattern π, and therefore, no (k, l)-pattern in Cons(S) can exist. Second, b > k, i.e., more than k variables appear in π. Consequently, there is again no ( k, l )-pattern in Cons(S). Finally, k variables and l constants appear in the candidate pattern π. Now, one can easily check whether π is consistent. If it is, π ∈ Cons(S), and we are done. Otherwise, there is no (k, l)-pattern in Cons(S). An algorithm computing the unique candidate π for the ( k, l )-pattern in Cons( S ) follows straightforwardly from the proof above. For the sake of presentation, we omit the consistency test here. Additionally, Algorithm 1 does not test whether the numbers m i are integral, since it is run later only for pairs (k, l) leading to integral values of the m,. Furthermore, we assume a subprocedure taking as input a sample S, and returning the longest common prefix u as well as the first position d where the input strings differ. The following algorithm either returns a pattern π or NIL. If NIL is returned then there is no (k, l)-pattern in Cons(S). Algorithm 1 On input (k,l), S = {so, . . , sr-1}, and u, d do the following: for j = 0, . . ,r − 1 do m j ← (|s j | − l ) /k od ; π ← u; b ← 0; j ← d; c ← | u |; while j ≤ k + l do if s 0 (bm 0 + j − b) = si(bmi + j − b) for all 1 ≤ i ≤ r − 1 then if c < l then π ← πso(bmo + j − b); c ← c + 1 else return  NIL fi else if b < k then π ← πx; b ← b + 1 else return NIL fi fi j ← j + 1 od: return π Note that minor modifications of Algorithm 1 perform the consistency test S ⊆ L(π) even while π is constructed. Example 1 Let S = {0001000010, 1011010110, 100101001010, 11001010110010, 110111110111110} Then |s 0 | = 10 and there are 27 possible ( k,l )-pairs, i.e., (1,9), (2,8), . . . , (10,0), (1,8), . . . ,  (5,0),  (1,7),  (2,4),  (3,1),  (1,6),  (2,2),  (1,5),  (2,0),  (1,4),  . . . ,  (1,0). Next, checking for |si|, |s2|, |s3|, and |si| whether or not mi = (|si| — l)/k is integral immediately rules out 12 of the listed ( k, l )-pairs.  Clearly, for S the longest common prefix is u = ε , and thus d = 1. Running Algorithm 1 on the remaining 15 pairs returns NIL for (1,9), (1,8), (1,7), (1,6), (1,5), (1,4), (1,3) as well as for (2,8) and (2,6). Thus, Cons(S) contains only patterns for the pairs (2,4), (2,2), (1,2), (2,0), (1,1), and (1,0). These are x 10x10, x0x0, x10, xx, x0, and x, respectively. The longest among these patterns is x 10x 10, and it is descriptive for S . Putting Lemma 4 and the fact that there are O(|s 0 |  log |s 0 |) many possible ( k, l )-pairs together, we directly obtain: LEMMA 5. Then |Cons(S)| = Let S = {so,...,s,-1} be any prefix-free sample. O ( | s o | log | s o | ) Using Algorithm 1 as a subroutine, Algorithm 2 below for finding a descriptive pattern for a prefix-free sample S follows the strategy exemplified above. Thus, it simply computes all patterns in Cons(S) and outputs one with maximum length. For inputs of size n the overall complexity of the algorithm is O(n | s 0 | log | s 0 |) = O(n 2 logn), since at most O(|s 0 | log |s 0 |) many tests must be performed, which have time complexity O(n) each. Algorithm 2 On input S = {so,...,s,-1} do the following: P ← 0; for k = 1, . . . |so| do for mo = 1, . . , [ [[] do if there is a (k, | s 0 | — km 0 )-pattern π ∈ Cons(S ) then P ← P ∪ {π} od od; Output a maximum-length pattern π ∈ P. It should be noted that the number of ( k, l )-pairs for which the test has to be performed is actually smaller than O ( | s 0 | log | s 0 |) for many inputs. This is because the requirement that (|si| — l)/k is integral for all i restricts the set of possible values of k if not all strings have the same length. More precisely, only those values of k that are divisors of |si| — |sj for all 0 < i,j < r — 1 must be considered. Another remark concerns the order in which the (k,l)-pairs are processed. Since it suffices to output a consistent pattern having maximum length, it is practically helpful to process the ( k, l )-pairs in order of non-increasing k + l. This ensures that the algorithm can terminate as soon as it encounters the first consistent pattern. The worst-case complexity is not improved, however, because all ( k, l )-pairs have to be processed if the descriptive pattern is x.
3.
An Efficient Parallel Algorithm
Whereas the RAM (random access machine) model has been generally accepted as the most suitable model for developing and analyzing sequential algorithms, such a consensus has not yet been reached in the area of parallel computing. Nevertheless, the PRAM ( parallel random access machine ) model, introduced by Fortune and Wyllie [7], is usually considered an acceptable compromise (cf., e.g., Zeugmann [32] for an overview). A PRAM consists of a number of processors, each of which has its own local memory and can execute its local program, and all of which can communicate by exchanging data through a shared memory (cf., e.g., JáJá [10]). The advantages of the PRAM model over competing parallel machine models include the simplicity with which PRAM algorithms can be described and analyzed, and the high level of abstraction this model offers. Its drawback is the somewhat unrealistic assumption of a globally shared memory which causes problems for the implementation of PRAM algorithms on existing parallel com- puters. It has been shown, however, that PRAM algorithms can be executed efficiently on a number of parallel architectures [1, 14]. Different variants of the PRAM model have been considered with respect to the con- straints on simultaneous accesses to the same memory location by different processors. The CREW-PRAM allows concurrent read accesses but no concurrent write accesses (CREW stands for concurrent read – exclusive write ). The various PRAM models, rang- ing from EREW to CRCW, have been shown to be equally powerful except for logarithmic factors in running time or processor requirements. For ease of presentation, we will de- scribe our algorithm for the CREW-PRAM model. The algorithm can be modified to run on an EREW-PRAM, however, by the use of standard techniques. For any further information, we refer the reader to JáJá [10]. To our knowledge, no parallel algorithm for computing descriptive one-variable pat- terns has been known previously. We show how Algorithm 2 can be efficiently parallelized by using several well-known techniques including prefix-sums, tree-contraction, and list- ranking as subroutines (cf. [10]). First, we observe that a parallel algorithm can deal with non-prefix-free samples S in the same way as the sequential algorithm. Checking whether S is singleton or whether s 0 is a prefix of all other strings can be easily done in time O (log n ) using O ( n /log n ) processors. Therefore, without loss of generality we assume that these prefix-tests have been performed, and that the input sample S = { s 0 , . . , s r-1} is prefix-free. In addition, we assume that the prefix-tests have returned the first position d where the input strings differ and an index t, 1 ≤ t ≤ r − 1, such that s 0 (d)̸= s t (d). Obviously, a parallel algorithm can deal with all O( | s 0 | log | s 0 |) possible ( k, l )-pairs in parallel. For each ( k, l )-pair, our parallel algorithm computes the unique ( k, l )-pattern in Cons(S), if it exists. Finally, it suffices to output any obtained pattern having maximum length. Next, we show how to efficiently parallelize the two steps to be performed for each ( k,l )-pair, i.e., computing a candidate ( k,l )-pattern π and checking whether S ⊆ L(π). An illustrative example can be found at the end of this section. For a given ( k, l )-pair, the algorithm uses only the strings s 0 and s t for calculating the unique candidate π for the (k,l)-pattern in Cons(S). Considering only two strings reduces the processor requirements, and an easy modification of the proof of Lemma 4 shows that the candidate pattern remains unique even if only two strings that differ in position d are considered. Position j t in s t is said to be b-corresponding to position j 0 in s 0 if j t = j 0 +b(m t −m 0 ), where 0 ≤ b ≤ k. Intuitively, the meaning of b-corresponding positions is as follows. Suppose there is a (k, l)-pattern π which is consistent with s 0 and s t . Furthermore, assume that position j 0 in s 0 corresponds to a constant symbol in π , and that b occurrences of x are to the left of that constant symbol. Then that symbol corresponds to position jt = jo + b(mt = mo) in st. For example, let π = 0x0x00x1, so = π[0/x] = 0000001, and s t = π[1111/ x ] = 01111011110011111. Thus, m 0 = 1 and m t = 5. Hence position 20 in s t is 3-corresponding to position 8 in s 0 , since 8 + 3(5 — 1) = 20. In order to be able to compute the candidate pattern from so and st, the algorithm calculates the entries of an auxiliary array EQUAL[j, b] of Boolean values first, where j ranges from 1 to |s 0 | and b ranges from 0 to k. Intuitively, EQUAL[j, b] is true iff the symbol in position j in s 0 is the same as the symbol in its b-corresponding position in s t Formally, the array is defined as follows: EQUAL[ j, b ] = true iff s 0 ( j ) = s t ( j + b ( m t − m 0 )) The array EQUAL has O(k|so|) entries, and each value can be calculated in constant time. Using O(k|so|/ logn) processors, the resulting time requirement is O(logn) for computing EQUAL. The following lemma shows how a candidate pattern can be obtained from EQUAL within the same time and processor bounds. LEMMA 6. Let S = {so, . . , sr-1} be a sample, and let n be its size. Given the array EQUAL, the unique candidate π for the (k, l)-pattern in Cons(S), or NIL, if no such pat- tern exists, can be computed on an EREW-PRAM in time O(log n) using O(k|s 0 |/log n) processors. Proof. Sequentially, the candidate pattern can be obtained from EQUAL in a way similar to Algorithm 1 in Section 2, namely by starting at EQUAL[1, 0] with the empty pattern π and visiting entries of EQUAL according to the following rule:  If EQUAL[j, b] is true, append s 0 ( j ) to π and go to EQUAL[ j + 1, b ]. Otherwise, append x to π and go to EQUAL[j + m 0, b + 1]. This is iterated until at least one index lies outside the valid range. If the procedure terminates because it tries to visit EQUAL||so|+1, k|, a candidate pattern has been obtained. Otherwise, there is no (k,l)-pattern in Cons(S), and NIL can be returned. To perform this calculation efficiently in parallel, a directed graph G = (V, E) is built from the array EQUAL. The set of nodes V consists of one node for each entry of EQUAL and one additional node, i.e., nodes v j,b for 1 ≤ j ≤ |s 0 | and 0 ≤ b ≤ k and an additional node v|so|+1,k. Note that |V| = O(k|so|). The following arcs are added to E:
EQUAL[j, b] = false iff (Vj,b, Vj+mo,b+1) E E These are the only arcs in the graph G. Note that each node of G has outdegree at most 1 and indegree at most 2, and that G is acyclic. In other words, G is a forest of binary in-t rees. Now we observe that a candidate (k, l)-pattern exists if and only if there is a path in G from v 1,0 to v 1,0 l+1,k. In addition, this path can be used to determine the candidate pattern. In order to extract the path, the tree-contraction technique can be used. We view each in-tree of G as an arithmetic expression tree where every internal node represents a + operation and every leaf node gets a 0, except for the leaf node v 1,0 which gets a 1. The expressions represented by all trees and subtrees of G can be evaluated simultaneously in time O(log n ) using O(k|s 0 |/log n ) processors on an EREW-PRAM. At the end, precisely the nodes reachable from v 1,0 have the value 1, whereas all other nodes are 0. Hence, the path from v 1,0 to the root of its in-tree can easily be extracted using prefix-sums and list-ranking. In addition, if the path does indeed end at V lsol+1,k, the candidate (k,l)-pattern can be obtained directly from the path and the string so. This is because the length of the candidate pattern π is equal to the number of nodes on the path minus one, and because π can be computed from the path by replacing each of the first |π | — 1 nodes by the appropriate symbol. More specifically, each node v j,b corresponding to a true entry EQUAL[j, b] is replaced by the constant s 0 (j), and each node vj,b corresponding to a false entry is replaced by the variable x . At this stage, the algorithm has either discovered that no (k, l)-pattern exists, or it has obtained a candidate (k, l)-pattern π. In the latter case, it needs to check whether π is indeed consistent with S. LEMMA 7. Given a candidate pattern π with k occurrences of x and l occurrences of constants, a parallel algorithm can check whether π is consistent with a sample S of size n in time O(log n) with O(n/log n) processors on a CREW-PRAM. Proof. Given the candidate pattern π, each symbol of a string s; ∈ S either corresponds to a constant in the pattern or to an occurrence of x (more specifically, it is the z-th symbol of an instantiation of x in si, for some z). We associate one bit with each symbol in each si, such that S ⊆ L(π) if and only if all these bits are true. For a symbol corresponding to a constant in the pattern, the bit is set to true if the symbol is equal to that constant. For a symbol which is the z-th symbol of an instantiation of x in si, the bit is set to true if the symbol is equal to the (d + z — 1)-th symbol of si, where d is the position of the first x in π. In other words, α is set to the substring of s i that starts in position d and has length mi, and it is checked whether this choice is consistent with all other occurrences of x in π . The Boolean AND of these n bits can then be computed in time O (log n ) with O(n/logn) processors on an EREW-PRAM. The resulting value is true if and only if π is consistent with the whole sample S . Now we show how the bits associated to all symbols in the sample can be calculated in the same time and processor bounds. In the following, the calculation is described for the symbols in one specific string si. First, the algorithm assigns a value to each symbol π(j) of the pattern. If j = 1 or π(j − 1) ∈ A, the value 1 is assigned to π(j). If j > 1 and π(j − 1) = x, the value m, is assigned to π(j). A prefix-sums calculation over the values assigned to the symbols in the pattern yields, for each symbol in the pattern, the position of its corresponding symbol in si (for constant symbols) or the position of the first symbol of its corresponding instantiation in si (for variable symbols). Next, a pair (j,z) is associated with each symbol in si and initialized to (0,0). For the j-th symbol π(j) in the pattern (1 ≤ j ≤ k + l), the (0,0)-pair associated to its corresponding symbol in s is replaced by (j, 0) if π(j) ∈ A, and by (j, 1) if π(j) = x. As a consequence, now the pair associated to a symbol in si is (j, 0) if the symbol corresponds to π(j) ∈ A and (j, 1) if the symbol starts the instantiation of π(j) = x. Symbols in the z-th position, z > 1, of an instantiation of x still have (0,0). The following operation on pairs of integers can easily be shown to be associative:
After a parallel prefix computation using the operation ⊕ on the pairs associated to the symbols in si, the pair associated to a symbol in the z-th position of an instantiation of π(j) = x is (j, z). The desired bit values can then be computed in constant time per bit as follows: Assume that the result of the prefix computation is (j,z) for symbol si(h). If π(j) E A, the bit associated to si(h) is true if and only if si(h) = π(j). If π(j) is x, the bit associated to si(h) is true if and only if si(h) = si(d + z = 1). For the prefix-sum computations over the values associated to symbols of the pattern time O(logn) and O((k + l)/logn) = O(|so|/logn) processors are sufficient. The prefix- sum computations over the pairs associated to symbols of si can be performed in time O(logn) using O(|si|/logn) many processors. Performing these computations in parallel for all i, 0 ≤ i ≤ r − 1, requires O(log n) time and O(n/log n) processors on an EREW- PRAM. A straightforward implementation of the computation of the bit values requires concurrent read access, however, because several processors may access the same symbol in π or in some s i when comparisons are performed. THEOREM 1. There exists a parallel algorithm that computes descriptive one-variable patterns in time O (log n ) using O ( ls 0 | max { | s 0 | 2 , n log | s 0 |} / log n ) = O (n 3 / log n ) proces- sors on a CREW-PRAM for samples S = { s 0 , . . , s r − 1 } of size n. Proof. If | S | = 1 or S is not prefix-free, O ( n / log n ) processors and O (log n ) time clearly suffice.  Otherwise, the number of processors required for calculating the array EQUAL and the candidate pattern in parallel for all possible ( k, l )-pairs according to Lemma 6 can be bounded as follows: Furthermore, checking which of the candidate patterns are consistent with S using the algorithm from Lemma 7 for all ( k, l )-pairs in parallel requires O ( n | s 0 | log | s 0 | / log n ) processors. A simple maximum calculation then suffices to output a consistent pattern with maximum k + l, which is descriptive by Lemma 3. As already mentioned earlier, it is not difficult to make the algorithm run on an EREW- PRAM in the same time and processor bounds. For this purpose, it is only necessary to make a sufficient number of copies of all memory locations that are accessed by several processors at the same time in order to ensure that each processor can work with its private copy. The details are somewhat tedious but standard, and therefore omitted here. Furthermore, note that the work performed by the parallel algorithm, i.e., the product of its time and processor requirements, is the same as that performed by the improved sequential algorithm from Section 2 whenever | s 0 |² = O (n log | s 0 |). If | s 0 | is larger, the work performed by the parallel algorithm exceeds that of the sequential algorithm by a factor less than O(|so|²/n) = O(|so|). Example 2  We give an example for the computation of a (k, l)-pattern in Cons(S) by the parallel algorithm. Let the sample S contain the following strings:
The values for m, are given for the ( k, l )-pair (2, 6), which is the pair which we focus on for the rest of this example. First, the algorithm finds that S is prefix-free. It determines that d = 2 (the first position where the strings differ) and t = 1 (s t is a string that differs from s 0 in position d ). The entries of the array EQUAL are then computed from s 0 and s 1 . The resulting values are given next, using 0 to denote "false" and 1 to denote "true."
In order to check whether there exists a candidate (2,6)-pattern, the algorithm creates a graph G from the array EQUAL. The graph is depicted in Figure 1. Obviously, there is a path from v 1,0 to v | so |+1,2 in G. Hence, there is a candidate (2,6)-pattern, and it can be derived from the path and from s 0 as follows:
The nodes v2,0 and v 8,1 on the path correspond to false-entries of the array EQUAL. As these nodes appear in positions 2 and 7 on the path, respectively, the candidate pattern π has occurrences of x in positions 2 and 7. The constant symbols in π are obtained by replacing v j,b by s 0 (j) for the remaining nodes on the path except the last one. The algorithm verifies that the resulting (2,6)-pattern 0x0101x1 is consistent with the sample and concludes that it is contained in Cons(S). In addition, this pattern turns out to be a longest pattern in Cons( S ) and therefore descriptive for the given sample. It should be mentioned that there is a special case for which the processor requirements of the algorithm can be improved. If the input sample contains two strings that are not identical but have equal length, the algorithm can be modified to use these two strings instead of s 0 and s to calculate the candidate ( k, l )-patterns. This has the advantage that the value of an entry EQUAL[j, b] of the array EQUAL does not depend on the second index b, because the value m, is identical for the two strings. Hence, the array EQUAL is only one-dimensional in this case. Therefore, the size of EQUAL and the corresponding graph is only O(n), and the candidate pattern π can be obtained in time O(log n) with O(n/logn) processors instead of O(k|s 0 |/logn) processors as before. Consequently, the overall processor requirement is reduced to O(n | s 0 | log | s 0 | / log n ) in this case. Further- more, note that it is not necessary to compute candidate patterns for all O(|so|log |so|) (k,l)-pairs. Let si and si be the two strings that are not identical but have equal length. Then it is sufficient to check for the O(|si|) possible substitution lengths mi whether there is a candidate pattern which can generate si and si by substituting strings of length mi for x. The processor requirement for this alternative implementation is O(n |si |/ log n), which is an improvement if | s i | = o (| s 0 | log | s 0 |).  A corresponding improvement is possible for the sequential algorithm from Section 2 in this special case as well.
4.  Analyzing the Expected Total Learning Time
Until now, we have dealt with the update time of our set-driven learners by analyzing the proposed algorithms for computing descriptive one-variable patterns.  Now, we are interested in the resulting total learning time. Let π be the pattern to be inferred. The total learning time of any algorithm that tries to infer π is unbounded in the worst case, because there are infinitely many strings in L(π) that can mislead the algorithm. To see this, assume that π = x and that the learning algorithm is initially given strings of the form Ou for some u ∈ A+. The algorithm cannot rule out the possibility that the pattern to be inferred is Ox until it sees a string 0 or au for some a ∈ A \ {0} and u ∈ A *. On the other hand, in the best case two examples, namely π[0/x] and π[1/x], do always suffice for a learning algorithm that outputs descriptive patterns as hypotheses. Hence, we assume that the strings presented to the algorithm are drawn from L(π) according to a certain probability distribution. This allows us to obtain results about the expected total learning time of an algorithm. The probability distribution must satisfy two criteria: any two strings in L(π) of equal length must have equal probability, and the expected string length must be finite. We refer to such distributions as proper probability distributions. The assumption that strings of equal length are equally probable seems a very natural assumption. We present a learning algorithm that infers a one-variable pattern π with expected total learning time O( ℓ 2 log ℓ ), where ℓ is the expected length of a string drawn from L( π ) according to the probability distribution. It turns out advantageous not to calculate a descriptive pattern each time a new string is read. Instead, our proposed one-variable pattern learning algorithm, Algorithm 1LA, reads a certain number of strings before it starts to perform any calculations at all. It waits until the length of a sample string is smaller than the number of sample strings read so far and until at least two different sample strings have been read. During these first two phases, it outputs s 1 , the first sample string, as a hypothesis as long as all sample strings read so far are the same, and it outputs x as a hypothesis once a sample string different from §1 has been encountered. If the pattern π is a constant pattern, i.e., |L(π)| = 1, the correct hypothesis is output after the first sample string is read, and the algorithm never reaches the third phase. Otherwise, the algorithm uses a modified version of Algorithm 2 from Section 2 to calculate a set P ′ of candidate patterns when it enters Phase 3. More precisely, it does not calculate the whole set P ′ at once.  It rather uses the function first_candidate once to obtain a longest pattern in P ′ , and the function next_candidate repeatedly to obtain the remaining patterns of P ′ in order of non-increasing length.  This has the benefit of reducing the memory requirements for Algorithm 1LA substantially. The pattern τ obtained from the call to first_candidate is used as the current candidate pattern. Each new sample string s is then compared to the current candidate pattern τ. If s ∈ L(τ), τ is output as a hypothesis. Otherwise, next_candidate is called to obtain a new candidate pattern τ ′ . Now, τ ′ becomes the current candidate pattern and is output as a hypothesis, no matter whether s ∈ L(τ′). If the longest common prefix of all sample strings including the new string s is shorter than that of all sample strings excluding s, however, first_candidate is called again and a different list of candidate patterns is considered. Note that Algorithm 1LA may output inconsistent hypotheses, because the current candidate pattern τ may fail to generate a previously read sample string that has been discarded or even the current sample string if τ has just been obtained by a call to next_candidate in order to replace a previous candidate pattern that failed to generate the current sample string. Algorithm 1LA is shown in Figure 2. The functions first candidate and next candidate represent a modified version of the algorithm from Section 2.  Let S = {s,s'}.  Let P'(S) = { vx }, if s = vc for some c ∈ A and s' = sw  for some string w. Otherwise, denote by u the longest common prefix of s and s', and let P'(S) be the set of all patterns τ = uo that can generate s and s' if we allow substitutions that replace different occurrences of x by different strings of the same length. The algorithm from Section 2 yields exactly P'(S) if we omit the consistency check. Hence, P'(S)ニCons(S), where Cons(S) is as defined in Section 2. Note that P'( S ) necessarily contains the pattern π if s and s' are in L(π) and if the longest common prefix of s and s' is the same as the longest constant prefix of π. Furthermore, P ′ ( S ) contains at most O ( s | log | s |) patterns. Since we omit the consistency checks, a call to first_candidate and all subsequent calls to next_candidate until either the correct pattern is found or the prefix changes can be performed in time O(|s|² log |s|) altogether. We will show that Algorithm 1LA correctly infers one-variable pattern languages from text in the limit, and that it correctly infers one-variable pattern languages from text with probability 1 if the sample strings are drawn from L(π) according to a proper probability distribution. 2  In the latter case, the expected total learning time is shown to be O( ℓ 2 log ℓ), where ℓ is the expected length of a sample string. THEOREM 2.  Let π be an arbitrary one-variable pattern.  Algorithm 1LA correctly infers π from text in the limit. Proof. If π is a constant pattern, Algorithm 1LA outputs π after reading a single sample string and doesn't change its hypothesis later on. Otherwise, let π = uxμ, where u ∈ A* is a string of d — 1 constant symbols and μ ∈ Pat 1 ∪ {ε}. As every string in L(π) will be eventually presented to Algorithm 1LA, sooner or later it will have encountered two strings that differ in position d. At this point, pattern π will be among the candidate patterns in { Phase 1 } r ← 0; repeat r ← r + 1: read string s, if S 1 = S 2 = ··· = s, then output hypothesis s 1 else output hypothesis x fi until | s, | < r; { Phase 2 } while s 1 = s 2 = ··· = s r do r ← r + 1; read string s, if s, = s, then output hypothesis s, else output hypothesis x fi od; { Phase 3 } s ← a shortest string in { S1, S2, . . . , Sr}; u ← maximum length common prefix of { S 1 , S 2 , . . . , S r }; if u = s then s' ← a string in {s1, s2, . . . , sr} that is longer than s else s' ← a string in { s 1 , s 2 , . . , s r } that differs from s in position | u | + 1 fi τ ← first_candidate(s, s'); forever do read string s": if u is not a prefix of s" then u ← maximum length common prefix of s and s"; s' ← s": τ ← first_candidate(s, s') else if s" $ L( τ ) then τ ← next_candidate(s, s', τ) fi output hypothesis τ od Figure 2: Algorithm 1LA the set P' implicitly maintained by Algorithm 1LA. For every pattern π' ∈ P'\{π} with |π′| ≥ |π|, there are infinitely many strings in L(π) \ L(π′). Hence, all these patterns π′ will be eventually discarded by the algorithm, and it will output the correct hypothesis π After that, the algorithm will never change its hypothesis. THEOREM 3. Let π be an arbitrary one-variable pattern. If sample strings are drawn from L(π) according to a proper probability distribution, Algorithm 1LA correctly infers π with probability 1. Proof. If π is a constant pattern, Algorithm 1LA outputs π after reading a single sample string and converges. Otherwise, let π = uxμ, where u ∈ A* is a string of d — 1 constant symbols and µ ∈ Pat 1 ∪ {ε}. After Algorithm 1LA has read two strings that differ in position d, pattern π will be one of the candidate patterns in the set P ′ implicitly maintained by the algorithm.  As each new sample string differs from the first sample string in position d with probability (|A| — 1)/|A| ≥ 1/2 (this is a consequence of the fact that strings in L(π) of equal length are equally probable), this event will happen eventually with probability 1. After that, as long as the current candidate pattern τ is different from π, the probability that the next sample string read is not in the language of τ is at least 1/2 (cf. Lemma 8 below). Hence, all candidate patterns will be discarded with probability 1 until π becomes the current candidate pattern and is output as a hypothesis. After that, the algorithm converges. LEMMA 8. Let π = uxμ be a one-variable pattern with constant prefix u, and μ ∈ Pat 1 ∪ {ε}.  Let s 0 , s 1 ∈ L(π) be arbitrary such that s 0 (|u|+ 1)̸= s 1 (|u|+ 1).  Let τ̸= π be a pattern from P'({ s 0 , s 1 }) with | π |. Then τ fails to generate a string s drawn from L(π) according to a proper probability distribution with probability at least (| A | − 1)/| A |. Proof. Denote the number of occurrences of constant symbols in π and τ by # a (π), and # A ( τ ), respectively. Recall that # x ( π ) and # x ( τ ) denotes the number of occurrences of x in π and τ, respectively. Note that either # x (τ) > # x (π) or # x (τ) > # x (π) (or both). This is obvious if | π > | π |, and for | π | = | π | this follows from the fact that there is at most one ( k, l )-pattern in P ′ ({ s 0 , s 1 } ) for each ( k, l )-pair. Let n be the length of the string s drawn from L(π). If n — # A(π) is not divisible by # x ( τ ), then Pr(s ∈ L(τ) | |s| = n ) = 0. Otherwise, we distinguish the following cases: Case 1. # x ( τ ) > # x ( π ). Let I x be the set of positions in s which correspond to the first symbol of a substitution string α x that is substituted for x in π to obtain s. Similarly, let I, be the set of positions in s which correspond to the first symbol of a substitution string that is substituted for x in τ to obtain s, assuming such a substitution exists. As |I r | > |I r |, I r contains a position i r which corresponds to the first symbol of a substitution string with respect to 7, but to a constant or a second, third, fourth, etc. symbol of α π with respect to π. Hence, τ can only generate s if that constant or second, third, fourth, etc. symbol of α π is equal to the first symbol of a substitution string with respect to τ , which must in turn be equal to the first symbol of α x because π and τ have the same constant prefix. The probability for this to happen is 1/1AI. Case 2. # x ( τ ) > # x ( π ). Let I π be the set of positions in s which correspond to constants with respect to π, and let I, be the set of positions in s which correspond to a constant with respect to τ. As | I r | > | I π | , I r contains a position i , which corresponds to a constant c with respect to τ but to a symbol of α π with respect to π . The probability that this symbol of α x is equal to c is 1/| A |. Now, we analyze the total expected learning time of Algorithm 1LA. Obviously, the total expected learning time is O(l) if the pattern π to be learned is a constant pattern. Hence, we assume in the following that π contains at least one occurrence of x. The total learning time of Algorithm 1LA is divided into three phases. Phase 1 refers to the time when the algorithm reads strings but does not yet perform any calculations because |s,| ≥ r. Phase 2 refers to the time when the algorithm has already encountered a sample string s, with |s,| < r, but is waiting for a sample string that differs from s 1 . Phase 3 starts when the algorithm makes the first call to first_candidate , and it ends when the algorithm outputs the correct hypothesis for the first time. Next, we recall the definition of the median, and establish a basic property of it that is used later. As usual, we use E(R) to denote the expectation of a random variable R, DEFINITION 4. Let R be any random variable with range(R) ⊂ IN. The median of R is the number μ ∈ range(R) such that Pr(R < μ) ≤ ≒ and Pr(R > μ) < ≒ P ROPOSITION 1. Let R be a random variable with range( R ) ⊂ IN+. Then its median µ satisfies μ ≤ 2E(R). Proof.
This proposition also follows from the Markov inequality Pr(R > t) ≤ E(R)/t, which holds for all random variables R assuming only non-negative values and for all positive real numbers t. In addition, note that the median can be significantly smaller than the expectation. For example, the median is always finite, even if the expectation is not. The proposition above is only a worst-case estimate. Let D be any proper probability distribution, and let L be the random LE MMA 9. variable taking as values the length of a string drawn from L(π) with respect to D. Fur- thermore, let μ be the median of L and let l be its expectation.  Then, the expected number of steps performed by Algorithm 1LA during Phase 1 is O(μℓ). Proof. Let Li be the random variable whose value is the length of the i-th string read by the algorithm. Obviously, the distribution of Li is the same as that of L. Let R be the random variable whose value is the number of strings Algorithm 1LA reads in Phase 1. Let L Σ := L 1 + · · · + L R be the number of symbols read by Algorithm 1LA during Phase 1. Let W 1 be the random variable whose value is the time spent by Algorithm 1LA in Phase 1. Obviously, W 1 = O(L Σ ) Claim 1. For i < r, we have:
As Li must be at least i provided R > i, Equation (1) can be proved as follows:
Similarly, it can be shown that
Furthermore, it is clear that
Now, we rewrite E(LE):
For (β), we use Equations (1) and (2) to obtain:
Hence, the expected number of steps performed in Phase 1 is E(W 1 ) = O(E(L x )) O( μℓ ). Now, under the same assumptions as in Lemma 9, we can estimate the expected number of steps performed in Phase 2 as follows. LEMMA 10.  During Phase 2, the expected number of steps performed by Algorithm 1LA is O(l). Proof. If different sample strings have already been read during Phase 1, no work is performed in Phase 2. Otherwise, denote by T the number of strings read in Phase 2. As π contains at least one variable, the probability that a newly read sample string differs from the previously read strings is at least f. Hence, Pr(T' = t) < 2-(t-l) for t > 1. Denote by W 2 the number of steps performed in Phase 2. Furthermore, since it is clear that E(W 2 | T = t) = tE(L), we obtain:
Finally, we deal with Phase 3.  Again, let L be as in Lemma 9. Then, the average amount of time spent in Phase 3 can be estimated as follows. 24 LEMMA 11. During Phase 3, the expected number of steps performed in calls to the functions first_candidate and next_candidate is O(μ² log μ). Proof. Denote by W$ the number of steps performed in all calls to the functions first candidate and next_candidate in Phase 3. We study the conditional expectation E(W, ° | R = r) first. We account for the function calls in groups consisting of one call to first_candidate and all subsequent calls to next_candidate prior to another call to first_candidate. Note that such a group of candidate calls requires time O(|s|2 log |s|) altogether, where s is the shorter of the two parameters for the call to first_candidate. If R = r, the shortest string read in Phase 1 has length at most r — 1, and each group of candidate calls takes at most O((r — 1)² log(r — 1)) steps. How many groups of candidate calls are performed? With probability 1, at least one group is started. A new group is started only when the longest common prefix of all sample strings becomes shorter. Since at least two strings are read before the first group of candidate calls is started, the probability for a second group is at most 1/2. Whenever the longest common prefix of all sample strings changes, the probability that the new prefix is the final one and that, therefore, the next group of candidate calls is the last one is at least 1/2. Hence, the probability that k groups of candidate calls are performed is at most 2-(k-'), and we have:
Furthermore, we can rewrite E(W 3 ) as follows:
Obviously, Equation (4) implies (α) = O(μ² logμ). In addition, (β) can be bounded as follows:
Hence, we obtain E(W ξ) = O(μ² logμ) LEMMA 12. During Phase 3, the expected number of steps performed in reading strings is O(μℓ log μ). Proof. Denote by W3 the number of steps performed while reading strings in Phase 3. We make a distinction between strings read before the correct set of candidate patterns is considered, and strings read afterwards until the end of Phase 3. The former are accounted for by random variable V 1 , the latter by V 2 . If the correct set of candidate patterns, i.e., the set containing π, is not yet considered, the probability that a new string does not force the correct set of candidate patterns to be considered is at most 1/2. Denote by K the random variable whose value is the number of strings that are read in Phase 3 before the correct set of candidate patterns is considered. We have:
Assume that the correct set of candidate patterns P ′ contains M patterns that are con- sidered before pattern π. For any such pattern τ, the probability that a string drawn from L(π) according to a proper probability distribution is in the language of τ is at most 1/2, because either τ has an additional variable or τ has an additional constant symbol (Lemma 8). Denote by V, the steps performed for reading strings while the i-th pattern in P' is considered. Since M = O(R log R), we obtain:
During Phase 3, the expected number of steps performed in checking LEMMA 13. whether the current candidate pattern generates a newly read sample string is O(μℓ logμ). Proof. Denote by W cd the number of steps performed during Phase 3 for checking whether a newly read sample string can be generated by the current candidate pat- Each such check requires a number of steps that is linear in the length of the tern. respective sample string. For each string read in Phase 3, only one such check is per- formed. Hence, each check can be charged to the corresponding read, and we obtain E(W 3cd ) = O(E(W 3 )) = O(μE(L) log μ). Putting it all together, we arrive at the following expected total learning time required by Algorithm 1LA. THEOREM 4. If the sample strings are drawn from L(π) according to a proper prob- ability distribution with expected string length ℓ the expected total learning time of Algo- rithm 1LA is O( ℓ ² log ℓ ). Proof. Taking into account that µ = O(E(L)), the assertion follows directly from the Lemmas 9 through 13. It should be mentioned that Algorithm 1LA can be implemented with very small space requirements. It suffices to store only two sample strings and one candidate pattern in memory. The two sample strings are the shortest string s encountered so far and a sample string s' that differs from s, either by being longer than s (if all sample strings have the form sv) or by having a different character in position | u | + 1 (if the longest common prefix u of the sample strings satisfies | u | < | s |). In addition, a third string, namely the newly read sample string, must be stored temporarily.
5. Learning with Superset Queries
Angluin [4] showed that the class of all pattern languages is not learnable with poly- nomially many queries if only equivalence, membership, and subset queries are allowed as long as any hypothesis space H is considered such that range(H) = PAT. Applying the same proof technique, this result may be easily extended to the one-variable pattern languages.  That is, there is no query learning algorithm exactly inferring PAT 1 with respect to any hypothesis space H with range(H) ⊂ PAT that uses only polynomially many queries. On the other hand, positive results are also known. First, Lange and Wiehagen [17] showed PAT to be exactly learnable using polynomially many disjointness queries with respect to the hypothesis space PAT ∪ FIN, where FIN is the set of all finite languages. Additionally, they proved that PAT ∪ FINQ is exactly learnable with respect to PAT ∪ FINQ using polynomially many disjointness queries, too, where FINQ is the set of all finite query languages really needed. Moreover, their proof technique easily extends to the one-variable pattern languages, i.e., PAT 1 is exactly inferable with respect to PAT 1 U FIN by asking polynomially many disjointness queries.  It remains open, however, whether polynomially many disjointness queries do suffice, if the admissible hypothesis space is PAT or PAT 1 itself, respectively. Second, Angluin [4] established an algorithm exactly learning PAT with respect to PAT by asking polynomially many superset queries. Clearly, this algorithm also learns one-variable patterns as a special case.  But what can be said about the hypothesis space needed?  Angluin's [4] algorithm starts by determining the length of π by asking L(π) ⊆ L(π) for τ = x 1 , x 1 x 2 , x 1 x 2 x 3 and so on until the answer is no. If i is the minimum for L(π) Q L(x 1 . . x i ), then |π | = i — 1. Thus, this approach works for one- variable patterns, too, but it requires choosing general patterns τ for asking the queries. It does not work if the hypothesis space contains only one-variable patterns, however. Moreover, there seems to be no way to modify this superset query algorithm for general pattern languages to obtain an algorithm that learns PAT 1 with respect to PAT 1 . Hence, the following question arises naturally. Does there exist a superset query algorithm learning PAT 1 with respect to PAT 1 that uses only polynomially many superset queries? Using the results of previous sections, we are able to answer this question affirmatively. Nevertheless, whereas PAT can be learned with respect to PAT by restricted superset queries, i.e., superset queries not returning counterexamples, our algorithm for exactly learning PAT 1 with respect to PAT 1 needs counterexamples. Interestingly enough, it does not need a counterexample for every query answered negatively, instead two coun- terexamples always suffice. The reason why counterexamples are so useful to learn one-variable patterns seems to be that they limit the search space tremendously. The next theorem shows that one- variable patterns are not learnable by a polynomial number of restricted superset queries. LEMMA 14. Let w ∈ A*. If L(xwx) ⊆ L(τ), then τ = x or τ = xwx. Proof. By Lemma 1 we know that L(π) ⊆ L(π) implies π = τ[ρ/x] for some ρ ∈ Pat. Here xwx = τ[ρ/x] for some ρ ∈ Pat 1 . Obviously, τ must begin and end with an x . If τ = x, we are done. Now, let τ̸= x. Thus, τ = xτ ′ x, and since xwx = ( xτ ′ x)[ q/x], the pattern ρ must also begin and end with an x. If Q = x then τ = xwx, and again we are done. Finally, if Q = xQ'x, then xwx = l τ[Q/X] = x Q'xτ'[Q/X]x Q'x̸= xwx, a contradiction. Now, we are ready for proving the theorem announced above. THEOREM 5.  Any algorithm exactly identifying all L ∈ PAT 1 generated by a pattern π of length n with respect to PAT 1 by using restricted superset and equivalence queries only must make at least |A|n-2 > 2n-2 queries in the worst case. Proof. Assume any learning algorithm LA. For constructing an adversary, we consider all patterns π = xwx, w ∈ A+, of length n and show that LA has to ask at least |A|π−2 many queries when learning one of the languages L(π). Note that there are | A | n −2 many pairwise different such patterns. We denote the target language by L*. We can assume that the Algorithm LA does not ask the question L* C L(x), since this question is answered yes for each possible π . Furthermore, without loss of generality we can assume that no question is asked twice. Now, Lemma 14 is the only ingredient needed. Suppose, the Algorithm LA is asking any pattern τ, i.e., whether or not L, ⊆ L(τ) or L, ＝ L(τ). The adversary maintains a list S of all patterns π described above, and simply answers each superset and equivalence query with no, until | S | = 1, in which case he gives up. If τ has been one of the patterns xwx, this pattern is deleted from S, otherwise S remains unchanged.  By Lemma 14, all answers given are compatible with the remaining element π of S , and thus at least | A | n − 2 many queries are necessary for exactly identifying L* = L(π). Furthermore, we can show that learning one-variable pattern languages with a poly- nomial number of superset queries is not possible if the algorithm may ask for a single counterexample only. THEOREM 6. Any algorithm that exactly identifies all one-variable pattern languages by restricted superset queries and one unrestricted superset query needs at least 2(k-1)/4 — 1 queries in the worst case, where k is the length of the counterexample returned. Proof. Take an arbitrary algorithm that learns one-variable patterns with superset queries and asks only for one counterexample. Assume again that there is no query L(π) C L(x). The alphabet A should contain the symbol 0. Let 71, . . , , , , , be the patterns queried by the algorithm if all questions are answered no and let L(π) ⊆ L(π j ) be the first (and only) unrestricted query. Let τ j+1, τ j+2, . . . be the following queries, if the algorithm gets Ok as the counterexample and all following questions are also answered no. The constant k is some number such that Ok f L(7j) and either k or k —1 is a multiple of 4. Such a k must exist unless τ j ∈ 0*x0* (when we choose 1k instead and change in the rest of the proof all O's to 1). Let x = 0, 0 = x, and let A = {
or be a set of patterns of length k with m = k/4 or m = (k — 1)/4. Obviously, 0k E L(π) for all π E A. We force the algorithm to ask at least 2™ — 1 queries by letting it identify a pattern π ∈ A with π̸= τ i for 1 ≤ i ≤ 2m. Such a π exists because | A | = 2m. How does the algorithm react, if it learns π and eventually gets Ok as the counterex- ample? We claim that the first 2m — 1 questions are answered no because L(Ti) Z L(π). The counterexample Ok is then really a counterexample because Ok E L(π) by definition of A It remains to be shown that τ i̸= π implies L( τ i )̸2 L( π ). Assume L( τ i )ጋL( π ). Then τ i [ Q /x] = π for some Q ∈ Pat 1 . Since τ i̸= x and π begins and ends with an x , τ i must be of the form τ i = xwx and ρ of the form ρ = xρ ' x . Then π = xρ ' xω ' xρ ' x for some ω ' . We can, however, show that π has no proper prefix that is also a suffix and whose length is between 2 and [|π|/2]. Here x q'x would be such a prefix/suffix, so we have a contradiction and L( τ i ) ∑ L( π ) follows. Why does π not have such a prefix/suffix?  Let us assume ν is such a prefix/suffix. If |v| is odd, then v = xaixazxaz. . xaix because it is a prefix.  On the other hand ν = 0ā;0ā;_10 . . .ā20ā;x because it is a suffix, and thus ν = 0 . . = x . . , a contradiction. If | ν | is even, then ν = xa ι xa 2 xa 3 . . xa i and ν = ā i 0ā i_10 . . ā 2 0ā 1 x . Now x = ā i (first symbols) and ai = x (last symbols), again a contradiction. Figure 3: Algorithm Q. This algorithm learns a pattern π by superset queries. The queries have the form “L(π) ⊆ L(π),” where τ ∈ Pat 1 is chosen by the algorithm. If the answer to a query L(π) ⊆ L(π) is no, the algorithm can ask for a counterexample C(π). By w<i we denote the prefix of w of length i and by max( R ) some maximum-length element of R . The new algorithm works as follows (see Figure 3). Assume the algorithm should learn some pattern π. First the algorithm asks whether L(π) ⊆ L(0) = {0} holds. This is the case iff π = 0, and if the answer is yes the algorithms knows the right result. Otherwise, the algorithm obtains a counterexample C(0) E L(π). Let C(0) ξ i be the prefix of C(0) with length j. By asking questions L(π) C L(C(0)<jx) for j = 1,2,3,... until the answer is no, the algorithm computes i = min{ j | L(π) ∑ L(C(0)≤ i x ) } Now we know that π starts with C(0)≤i−1 (since L(π) ⊆ L(C(0)≤i−1x) = C(0)≤i−1 A+); but what about the i-th position of π?  If π has no i-th position, i.e., |π| = i — 1, then π contains no variable and therefore π = C(0). The algorithms asks L(π) ⊆ L(C(0)) to determine whether this is indeed the case. An example is π = 1011 and C (0) = 1011; here i = 4 since {1011} = L(π) ⊆ L(C(0)≤ ³ x ) = 101 A +, but {1011} = L(π) ⊆ L(C(0)≤ ⁴ x ) = 1011A+.  The question L(π) ⊆ L(C(0)) is answered affirmatively and the algorithm presents C (0) = 1011 as its correct hypothesis. Otherwise, i.e., if L(π) E L(C(0)), then π contains at least one variable and π(i) cannot be a symbol from A since this would imply that π(i) is equal to the i-th symbol of C (0) and, therefore, L(π) ⊆ L(C(0)≤ i x ), a contradiction. Thus π(i) = x. At this point the algorithm uses the counterexample for the query L(π) ⊆ L(C(0)≤ ix) to construct a set S = {C(0), C(C(0)<ix)}. By construction, the two counterexamples differ in their i-th position, but coincide in their first i — 1 positions. Algorithm 2 on page 12 computes R = Cons(S), the set of all patterns consistent with S and coinciding with the words in S in their first i — 1 positions. Since π is consistent with S and coincides with S in the first i — 1 positions, π ∈ R. Again we narrowed the search for π to a set R of candidates. Let m be the length of the shortest counterexample in S. Then |R|= O(m logm) by Lemma 5. Now, the only task left to be performed is to find π among all patterns in R. We find π by removing other patterns from R. The following lemma gives a sufficient and necessary condition for this end. LEMMA 15. Let S ⊆ A+ and let π, τ ∈ Cons(S) with |π | ≤ |τ |. Then L(π) ⊆ L(π) implies π = τ Proof. If |π| < |τ| then L(π) Q L(τ). Let us therefore assume |π| = |τ|. By Lemma 1, we have L(π) ⊆ L(τ) iff π = τ[∅/ x ] for some ∅ ∈ Pαt 1. Since |π| = |τ|, we must have | ρ | = 1; thus either ρ = x or ρ ∈ A. If ρ ∈ A, then π ∈ A*, a contradiction since all patterns in Cons(S) contain at least one x . Hence, Q = x and π = τ [ x / x ] = τ. The algorithm tests L(π) ⊆ L(π) for a maximum length pattern τ ∈ R and removes τ from R if L(π) Q L(π). Iterating this process finally yields the longest pattern τ for which L(π) C L(π). Lemma 15 guarantees that τ = π. It is important to start with long patterns, since Lemma 15 does not hold for | τ | < | π |. For finding the correct i, the algorithm asks up to |π| queries followed by up to O(m log m) additional queries to identify π. The number of queries (and the running time) is therefore polynomial in the pattern length and the length of the counterexamples returned. Example 3 Let A = {0,1} and let π = 01x0xx1x. The algorithm starts by asking L(π) ⊆ L(0) and the answer is no. The algorithm now asks for a counterexample to L(0) and gets 0110101101101. To compute the fixed prefix up to the first x of π, the next queries are L(π) ⊆ L(0x), L(π) ⊆ L(01x), and L(π) ⊆ L(011x). Since the first two answers are yes, but the third answer is no, the algorithm knows that either π E A+ or the fixed prefix is 01 followed by an x. By asking L(π) ⊆ L(01101011011101) ( no ) the second possibility turns out to be right. Now we have to give a counterexample, say, 010000000001000, to L(π) C_L(011x). The algorithm constructs the sample S = {01101011011101, 010000000001000} and computes R = Cons(S) = {01x0x0xx0x1x0x, 01x0xx1x, 01x}, which must contain π. After the question L(π) C_L(01x0x0xx0x1x0x) is answered no, 01x0x0xx0xx1x0xx is removed from R and 01x0xx1x is the longest remaining pattern. The next question L(π) ⊆ L(01x0xx1x) is answered yes and 01x0xx1x is identified as π. In this example seven queries suffice to identify π. The following theorem states the main result of this section. THEOREM 7. There exists an algorithm Q learning PAT 1 with respect to PAT 1 by ask- ing only superset queries. The query complexity of Q is O(|π|+ m logm) many restricted superset queries plus two superset queries (these are the first two queries answered no) for every language L(π) ∈ PAT 1 , where m is the length of the shortest counterexample returned.
6.  Conclusions and Open Problems
During the last 15 years pattern languages have attracted considerable attention in ma- chine learning, formal language theory, and several interesting applications have emerged (cf., e.g., Shinohara and Arikawa [26] and the references therein).  Taking the growing interest in applications into account, the problem of efficient learning becomes a major issue. This demand leads to several new and interesting questions. Clearly, any efficient learner is required to have a polynomial update time. Furthermore, it is highly desirable to provide performance bounds concerning the total learning time, and/or to elaborate efficient parallel learners. The present paper addressed these issues for the special case of one-variable pattern language inference. First, we provided a new algorithm learning PAT 1 consistently, set- drivenly, and responsively from positive data (cf. Algorithm 2). This algorithm achieves update time O(n² log n) for input samples of size n, which saves a factor of n² over the best previously known algorithm by Angluin [2]. Moreover, the computation of descrip- tive patterns was efficiently parallelized achieving parallel update time O(logn) using O(n 3 / logn) processors on an EREW-PRAM. The resulting parallel learning algorithm is still consistent, set-driven and responsive. As far as we know, this is the first parallel algorithm computing descriptive patterns. Next, we turned our attention to the total learning time of Algorithm 2, and arrived at a modified version of it which has optimal expected total learning time. Here, by optimal we mean that the total learning time of Algorithm 1LA equals the update time of Algorithm 2 up to a constant factor. The price paid is giving up the requirements to learn consistently and set-drivenly. It is also interesting to compare our algorithm to Lange and Wiehagen's [17] inference procedure learning all pattern languages. This algorithm has been analyzed with respect to its expected total learning time, too (cf. [33]). An easy inspection of the analysis given in [33] shows that the expected total learning time of Lange and Wiehagen's algorithm is O(ℓμ- 1 ) for target languages L(π), where ℓ is again the expected string length, and µ is the probability to see a shortest string from L(π). Hence, whenever μ < 1/(ℓ logℓ) our Algorithm 1LA behaves better than Lange and Wiehagen's [17] with respect to its expected total learning time. The difference in behavior finds its explanation in the fact that Lange and Wiehagen's algorithm definitely needs two different shortest strings from L(π) for achieving convergence, while our Algorithm 1LA does not. As far as we know, 1LA is the first pattern language learning algorithm which provably converges even in case it has not received any string of minimal length from L(π). Moreover, we could successfully apply our basic technique for computing descriptive patterns to obtain an efficient active learning algorithm asking superset queries. Addition- ally, we established a tight bound on the number of unrestricted superset queries needed by any algorithm learning PAT 1 with respect to PAT 1 by asking superset queries: just two are necessary and sufficient. Next, we discuss possible generalizations of the results obtained. Let us start with erasing one-variable pattern languages.  Taking into account that {π[ε/π]} is singleton for all π ∈ Pat 1 , our results easily generalize to erasing one-variable pattern languages. Clearly, if a pattern does not contain any variable, there is only one text for it.  Otherwise, the resulting pattern language is infinite. Thus, as long as any of our learners has just seen a singleton sample, it outputs the only string in it as hypothesis. Otherwise, it always ignores the shortest string in the sample but behaves otherwise as described. The same idea applies mutatis mutandis to our query learner. Further research should deal with unions of one-variable pattern languages. This class is much richer and more interesting than PAT 1 itself (cf., e.g. [21, 22, 26]). Furthermore, a distinction has to be made between unbounded unions and an a priori restricted number m of allowed unions. In the first case, the whole class is not learnable if erasing sub- stitutions are allowed (cf. [26]). As far as a priori bounded unions are concerned, their learnability by a polynomial update-time algorithm has been known for a rather long time (cf., e.g. [26]), but nothing is known concerning the resulting total learning time and efficient parallelizations.
ACKNOWLEDGEMENTS
A substantial part of this work has been done while the second author was visiting the Research Institute of Fundamental Information Science (RIFIS) (now Department of Informatics) of Kyushu University at Fukuoka, Japan. This visit has been supported by the Japanese Society for the Promotion of Science under Grant No. 106011.  He is greatfully indebted to Setsuo Arikawa for providing excellent working conditions during his stay at RIFIS. He also thanks Janos Csirik for several discussions and suggestions. The fifth author kindly acknowledges the support by the Grant-in-Aid for Scientific Research (C) from the Japan Ministry of Education, Science, Sports, and Culture under Grant No. 07680403.