Learning One-Variable Pattern Languages in Linear Average Time

Rüdiger Reischuk∗Med. Universität zu Lübeck
Institut für Theoretische Informatik
Wallstraße 40
23560 Lübeck, Germany
reischuk@informatik.mu-luebeck.de

Abstract
A new algorithm for learning one-variable pattern languages is proposed and analyzed withrespect to its average-case behavior. We consider the total learning time that takes into account all operations till an algorithm has converged to a correct hypothesis. For the expectation it is shown that for almost all meaningful distributions defining how the pattern variable is replaced by a string to generate random
examples of the target pattern language thisalgorithm converges within a constant numberof rounds with a total learning time that is linear in the pattern length. Thus, the algorithm
is average-case optimal in a strong sense.
Though one-variable pattern languages cannot
be inferred finitely, our approach can also be
considered as probabilistic finite learning withhigh confidence.

1

INTRODUCTION

The formal definition of patterns and pattern languages
goes back to Angluin [1]. Since then, pattern languages
and variations thereof have been widely investigated(cf., e.g., [12, 13, 15].
As far as learning theory is concerned, pattern languages are a prominent example of nonregular languages
that can be learned in the limit from positive data. The
corresponding learning model goes back to Gold [5]. Let
L be any language; then a text for L is any infinite sequence of strings containing eventually all strings of L ,∗This work was performed while this author was visiting
the Department of Informatics at Kyushu University andwas supported by the Japan Society for the Promotion of
Science under Grant JSPS 29716102.

Thomas Zeugmann
Department of Informatics
Kyushu University
Kasuga 816-8580
Japan
thomas@i.kyushu-u.ac.jp
and nothing else. The information given to the learnerare successively growing initial segments of a text. Processing these segments, the learner has to output hypotheses about L . The hypotheses are chosen froma prespecified set called hypothesis space. The sequenceof hypotheses has to converge to a correct descriptionof the target language.
Looking at applications of limit learners, efficiency
becomes a central issue. But defining an appropriate
measure of efficiency for learning in the limit is a difficult
problem (cf. [10]). Various authors have studied theefficiency of learning in terms of the update time needed
for computing a new single hypothesis. But what counts
in applications is the overall time needed by a learner
until convergence, i.e., the total learning time. Since thetotal learning time is unbounded in the worst-case, we
study the expected total learning time. Next, we shortly
summarize what has been known in this regard.
Angluin [1] provides a learner for the class of all pattern languages that is based on the notion of descriptive patterns. Here a pattern π is said to be descriptive(for the set S of strings contained in the input provided so far) if π can generate all strings contained in
S and no other pattern having this property generates
a proper subset of the language generated by π . Since
no efficient algorithm is known for computing descriptive patterns, and finding a descriptive pattern of maximum length is N P -hard, its update time is practicallyinfeasible.
Therefore, one has considered restricted versions ofpattern language learning in which the number k of different variables is fixed, in particular the case of a single variable. Angluin [1] gives a learner for one-variable
pattern languages with update time O(`4 log `) , where` is the sum of the length of all examples seen so far.
Nothing is known concerning the expected total learning
time of her algorithm.
Erlebach et al. [3, 4] have presented a one-variable
pattern learner achieving an average total learning timeO(|π|2 log |π|) , where |π| is the length of the target
pattern. This result is also based on finding descriptive
patterns quickly. While this approach has the advantagethat the descriptiveness of every hypothesis output isguaranteed, it may have the disadvantage of preventing
the learner to achieve a better expected total learningtime. Thus, we ask whether there is a one-variable pattern language learner achieving a subquadratic expected
total learning time. Clearly, the best one can get is alinear average total learning time. If this is really possible, then such a learner seems to be more appropriate for potential application than previously obtained
ones, even if there are no guaranteed properties concerning the intermediately calculated hypotheses. Sucha learner would have already finished his learning taskwith high probability before any of the known learnerhas computed a single guess.
What we like to present in this paper is such a onevariable pattern learner. Moreover, we prove that ourlearner achieves an expected linear total learning time
for a very large class of distributions with respect towhich the input examples are drawn.

2

PRELIMINARIESLet N = {0, 1, 2, . . .} be the set of all natural numbers,+
and let N = N \ {0} . For all real numbers y wedefine byc , the floor function, to be the greatest integer
less than or equal to y . Let Σ be an alphabet withs := |Σ| ≥ 2 . By Σ∗ we denote the free monoid over
Σ , and we set Σ+ = Σ∗ \ {ε} , where ε is the empty
string. Let x be a symbol with x ∈/ Σ . Every string
over (Σ ∪ {x})+ is called a one-variable pattern. We
refer to x as the pattern variable. Pat denotes the setof all one-variable patterns. We write #(π, x) for thenumber of occurrences of the pattern variable x in π .
The length of a string w ∈ Σ∗ and of a patternπ ∈ Pat is denoted by |w| and |π| , respectively. Let
w be a string with ` = |w| ≥ 1 , and let i ∈ {1, . . . , `} ;we use w[i] and w[−i] to denote the i -th symbol in w
counted from left to right and right to left, respectively,i.e.,w= w[1] w[2] . . . w[` − 1] w[`]
= w[−`] w[−` + 1] . . . w[−2] w[−1].

For 1 ≤ i ≤ j ≤ ` we denote the substring w[i] . . . w[j]of w by w[i . . . j] . Let π ∈ Pat and u ∈ Σ+ ; we use
π[x/u] for the string w ∈ Σ+ obtained by substituting
all occurrences of x in π by u . The string u is called asubstitution. For every π ∈ Pat we define the language
generated by pattern π byL(π) := {y ∈ Σ+ | ∃ u ∈ Σ+ , y = π[x/u]}
For discussing our approach to learning all one-variable
pattern languages we let
π = w0 xα1 w1 xα2 w2 . . . wm−1 xαm wm
be the target pattern throughout this paper. Here theαi denote positive integers (the multiplicity by which x
appears in a row), and wi ∈ Σ∗ the separating constant
substrings, where for 1 ≤ i < m the wi are assumed
to be nonempty.
The learning problem considered in this paper is exact learning in the limit from positive data. A sequence(ψi )i∈N+ of patterns is said to converge to a pattern πif ψi = π for all but finitely many i .

Definition 1. Given a target pattern π, the learnergets a sequence of example strings X1 , X2 , . . . from
L(π) . Having received Xg he has to compute as hypothesis a one-variable pattern ψg . The sequence ofguesses ψ1 , ψ2 , . . . eventually has to converge to a pattern ψ such that L(ψ) = L(π) .
Note that in the case of one-variable pattern languages this implies that ψ = π . Some more remarks
are mandatory here. Though our definition of learning resembles that one given in Gold [5], there is alsoa major difference. In [5] the sequence (Xi )i∈N+ is required to exhaust L(π) in the limit, that is to fulfill+{Xi | i ∈ N } = L(π) . Nevertheless, in real applications this requirement will be hardly fulfilled. We therefore omit this assumption here. Instead, we only require
the sequence (Xi )i∈N to contain “enough” information
to recognize the target pattern π . What is meant by“enough” will be made precise when discussing the setof all admissible distributions with respect to which theexample sequences are allowed to be randomly drawn.
We continue with the complexity measure considered in this paper. The length of the pattern π P
to belearned is given
P by n := nw + nx with nw := |wi |and nx :=αi . This parameter will be consideredas the size of problem instances, and the complexity
analysis will be done with respect to this value n . We
assume the same model of computation and the same
representation of patterns as Angluin [1], i.e., in particular a random access machine that performs a reasonable menu of operations each in unit time on registers oflength O(log n) bits, where n is the input length. The
inputs are read via a serial input device, and reading astring of length n is assumed to require n steps.
In contrast to previous work [1, 6, 14, 16], we measure the efficiency of a learning algorithm by estimating
the overall time taken by the learner until convergence.
This time is referred to as the total learning time. We
aim to determine the total learning time in dependence
on the length of the target pattern. Of course, if examples are provided by an adversary the number of examples one has to see before being able to converge isunbounded in general. Thus analyzing the total learning time in such a worst-case setting will not yield muchinsight. But such a scenario is much too pessimistic
for many applications, and therefore, one should consider the average-case behavior. Analyzing the expected
total learning time of limit learners has been initiatedby Zeugmann [17]. Average-case complexity in generaldepends very much on the distribution over the input
space. We perform our analysis for a very large class of
distributions. An optimal result of linear expected total
learning is achieved by carefully analyzing the combinatorics of words generated by a one-variable pattern.
This linear bound can even be shown to hold with highprobability. Letµ : Σ+ → [0, 1]
be the probability distribution specifying how given apattern π the variable x is replaced to generate random examples π[x/Z] from L(π) . Here Z = Zµ is arandom variable with distribution µ .
+Range(Z) := {w ∈ Σ | µ(w) > 0}
denotes the range of Z , i.e., the set of all substitution
strings that may actually occur. From this we get aprobability distributionµπ : Σ+ → [0, 1]
for the random strings generated by π based on µ . Let
X = Xπ,µ denote a random variable with distributionµπ . The random examples are then generated according
to X , thus the relation between X and Z is given by
X = w0 Z α1 w1 Z α2 w2 . . . wm−1 Z αm wm . Notethat µ is fixed, and in particular independent of thespecial target pattern to be learned.
What we consider in the following is a large class
D of distributions µ that is defined by requiring only
very simple properties. These properties basically exclude the case where only a small subset of all possible example strings occur and this subset does notprovide enough information to reconstruct the pattern.
We show that there exists an algorithm that efficiently
learns every one-variable pattern on the average withrespect to every distribution in D .
By E[|Z|] we denote the expectation of |Z| , i.e.,
the average length of a substitution. Then the expected
length of an example string X for π is given by E[|X|]= nw + nx · E[|Z|] ≤ n · E[|Z|] . Obviously, if one
wants to analyze the bit complexity of a learning algorithm with respect to the pattern length n one has toassume that E[|X|] , and hence E[|Z|] , is finite, otherwise already the expected length of a single example
will be infinite.
Assumption 1.
E[|Z|] < ∞ .
Let X = X1 , X2 , X3 , . . . denote a sequence ofrandom examples that are independently drawn according to µπ . Note that the learner, in general, does nothave information about µπ a priori. On the other hand,the average-case analysis of our learning algorithm presupposes information about the distribution µ . Thus,
unlike the PAC-model, our framework is not completely
distribution-free. Nevertheless, we aim to keep the information required about µ as small as possible. Finally, letL(π, µ) := {y ∈ Σ+ | µπ (y) > 0}
be the language of all example strings that may actuallyoccur.

3

PROBABILISTIC ANALYSIS OF
SUBSTITUTIONS

For obtaining most general results we would like to put
as little constraints on the distribution µ as possible.
Note that one cannot learn a target pattern if only example strings of a very restricted form occur. This will
be in particular the case if Range(Z) itself is containedin a nontrivial one-variable pattern language. For seeing
this, suppose there exists a pattern φ ∈ Pat \ {x} suchthat Range(Z) ⊆ L(φ) . Clearly, then the languages
generated by π = w0 xu0 w1 xu1 w2 . . . wm−1 xum wm and
π 0 = w0 φu0 w1 φu1 w2 . . . wm−1 φum wm cannot be distinguished, since L(π, µ) ⊆ L(π 0 ) . Thus, even from an
information theoretic point of view the learner has nochance to distinguish this case from the one where thepattern to be learned is actually π 0 and the examples
are generated by the corresponding projection µ0 ofµ . Hence, such a problem instance (π, µ) should be
regarded as the instance (π 0 , µ0 ) . To exclude this case,let us define
p0 :=
max
Pr[Z ∈ L(φ)] .
φ pattern, |φ|>1

and let us make

Assumption 2.

p0 < 1 .
An alternative approach would be to consider thecorrectness of the hypotheses computed with respect
to the distribution µ . The learner solves the learning problem if he converges to a pattern ψ for whichL(ψ, µ) = L(π, µ) . This model is equivalent, but conceptually more involved and complicates the algorithm.
Therefore we stick to the original definition. If p0 < 1then the following quantities
pa := max Pr[Z[1] = σ] ,
σ∈Σ

pe

:=

max Pr[Z[−1] = σ] ,σ∈Σare smaller than 1, too. Otherwise, for some σ it would
hold Range(Z) ⊆ L(σx) or Range(Z) ⊆ L(xσ) . To
illustrate these quantities, consider the special situation of length-uniform distributions, i.e., distributions where the lengths |Z| of the substitutions may
be arbitrary, but for each length ` all possible strings
over Σ+ of that length have the same probability. Then
it is easy to see that p0 ≤ 1/s and pa = pe = 1/s .
In general, define
p := max{pa , pe } < 1 ,and for sequences of substitutions Z = Z1 , Z2 , Z3 , . . .
the eventFg [Z] :=Z1 [1] = Z2 [1] = · · · = Zg [1]∨Z1 [−1] = Z2 [−1] = · · · = Zg [−1].
Then Pr[Fg ] ≤ 2p g − 1 .
Moreover, we define f (Z) := min{g | ¬Fg [Z]} .
Lemma 1. The expectation of f (Z) can be boundedas E[f (Z)] ≤ 2/(1 − p) .
Proof. Clearly, if m < min{g | ¬Fg [Z]} then Fm [Z]holds. Thus, we can estimate Pr[f (Z) > m] ≤ 2pm−1 ,and a simple calculation yields∞
X
E[f (Z)] =Pr[f (Z) > m]
m=0

≤ 2+2·

X
m≥2

=

2
1−p

pm−1

4

SYMMETRY OF STRINGS

We now come to the main technical tool that will help
us to detect the pattern variable and its replacements
in example strings, respectively.
Definition 2. Let y = y[1]y[2] . . . y[`] ∈ Σ+ bea string of length ` . If for some k with 1 ≤ k ≤ `/2
the k -length prefix and suffix of y are identical, thatis y[1 . . . k] = y[` − k + 1 . . . `] , we say that y has ak –symmetry u = y[1 . . . k] (or symmetry, for short).
A symmetry u of y is said to be the smallest symmetry
if |u| < |û| for every symmetry û of y with û 6= u .
Definition 3. Let u be a symmetry of y and+choose c, d ∈ N maximal such that y = uc v0 ud ,for some string v0 , i.e., u is neither a prefix nor a suffix
of v0 . This includes the special case v0 = ε . In thiscase, since c and d are not uniquely determined, wechoose c ≥ d such that their difference is at most 1 .
This unique representation of a string y will be calledfactorization of y with respect to u or simply
u –factorization, and u the base of this factorization.
If all occurrences of u are factored out including
also possible ones in v0 one gets a representation y =uc0 v1 uc1 v2 . . . vr ucr with positive integers ci ( c0 =c , cr = d ) and strings vi that do not contain u
as substring. This will be called a complete u –factorization of y .
Of particular interest for a string y will be its symmetry of minimal length, denoted by mls(y) , which
gives rise to the minimal factorization of y . For
technical reasons, if y does not have a symmetry thenwe set mls(y) := |y| + 1 . Let sym(y) denote thenumber of all different symmetries of y .
The following properties will be important for thelearning algorithm described later.
+

Lemma 2. Let k ∈ N and let u, y ∈ Σ+ be any
two strings such that u is a k –symmetry of y . Then
we have(1) u is a smallest symmetry of y iff u itself has nosymmetry.
(2) If y possesses the factorization y = uc v0 udthen it has k 0 -symmetries for k 0 = 2k, 3k, . . . ,min{c, d} k , too.
(3) If uc v0 ud is the minimal factorization of y then,for all k 0 ∈ {1, . . . , max{c, d}mls(y)} , y does
not have other k 0 -symmetries.
(4) sym(y) ≤ |y| / 2 mls(y) .
Proof. If a symmetry u of a string y can be written
as u = u0 v u0 for a nonempty string u then obviously
u0 is a smaller symmetry of y . Hence, (1) follows.
Assertion (2) is obvious. If there were other symmetries in between then it is easy to see that u itself musthave a symmetry and thus cannot be minimal. This
proves (3).

If v0 contains u as a substring there may be otherlarger symmetries. For this case there must be strings
v1 , v2 such that y can be written as
y = uc v1 ud v2 uc v1 ud
where v1 does not contain u as substring. Then y has
an additional symmetry for k 0 = (c + d) k + |v1 | . Theremay be even more symmetries if v2 is of a very special
form containing powers of u , but we will not elaborateon this further. The important thing to note is that thelength of such symmetries grows at least by an additive
term k = mls(y) . The bound on sym(y) follows.
Assertion (4) of the latter lemma directly implies thesimple boundsym(y) ≤ |y|/2 ,which in most cases, however, is far too large. Only
strings over a single letter alphabet can achieve thisbound. For particular distributions the bound is usually much better. To illustrate this, we again consider
the length-uniform case. Then, the probability that arandom string y has a minimal symmetry of length k
is given by
Pr[mls(y) = k] = Pr[|y| ≥ 2k] · s−k .
Furthermore, given that mls(y) = k the probability
that it has at least c symmetries is bounded by
1
Pr[sym(y) ≥ c | mls(y) = k] ≤ s−k·2 (c−1) ·.
1 − s−2c+1
Thus, the probability of having at least c symmetries
is at mostXs−2c+1s−k·(2c−1) ≤.
(1 − s−2c+1 )2k≥1

Now, we consider the expected number of symmetries. To motivate our Assumption 3, we first continue
to look at the length-uniform case.
Lemma 3. In the length-uniform cases.
E[sym(Z)] ≤
2(s
−
1)2
P
α
c
Proof. Using the equalityc≥1 c · α = (1−α)2 forα = s−2k in the estimation below one getsE[sym(Z)] =X
X
Pr[mls(Z) = k] ·c · Pr[sym(Z) = c | mls(Z) = k]
c≥1

k≥1

≤

X

s−k

≤

k≥1

=
≤

c · s−k 2(c−1) ·

c≥1

k≥1

X

X

sk

X

c · (s−2k )c ·c≥1

1
1 − s−1

X
1
s−2k
·
sk ·
−1
1−s
(1 − s−2k )2
k≥1
X
s
s−k
2(s − 1)k≥1=

1
1 − s−2c+1s.
2 (s − 1)2

Thus, in this case the number of symmetries only
depends on the size s of the alphabet and therefore,
it is independent of the length of the strings generated.
Let us now estimate the total length of all factorizationsof a string y , which can be bounded by |y| · sym(y) .
For the length-uniform case,
E[|Z| · sym(Z)] ≤ E[|Z|] · E[sym(Z)] .
can be shown, but for arbitrary distributions, we haveto require

Assumption 3.

It can be shown that this procedure considers each
bit position y[j] at most a logarithmic number of times
from which the bound O(` log `) follows easily. For
most strings, however, the complexity is linear sincemore than linear time is needed only for strings of highly
regular structure.
Algorithm 2.
The second, and in the worst-case more efficient algorithm first computes a maximal overlap of y , thatis a substring w of maximal length such that

E[|Z| · sym(Z)] < ∞ .

Remember that we already had to assume E[|Z|] tobe finite. Trivially, the expectation of |Z| · sym(Z) is
guaranteed to be finite if E[|Z|2 ] < ∞ , that means thevariance of |Z| is finite, but in general weaker conditions suffice.
If 0 < E[|Z| · sym(Z)] < ∞ then we also have 0 <E[sym(Z)] < ∞ . Thus we can find a constant c suchthat
E[|Z| · sym(Z)] ≤ c · E[|Z|] · E[sym(Z)] = O(1).
Symmetries and factorizations should be computed fast;
we thus show:
Lemma 4. The minimal symmetry of a string ycan be found in O(|y|) operations.
Given the minimal symmetry, all further symmetries
can be generated in linear time.
From a symmetry, the corresponding factorization canbe computed in linear time as well.
Proof. To find the minimal symmetry an iterative
scanning of specific bit positions of y is done. Let `denote the length of y .

Algorithm 1.
For j = 1, 2, . . . , ` − 1 , we will construct subsets Ij
of [1 . . . `] with the property:t ∈ Ij ⇐⇒ y[t . . . t + j − 1] = y[1 . . . j] .
The sets are initialized with Ij = {1} for all j .
Then I1 := {t | y[t] = y[1]} .
Assume that Ij−1 has been constructed.
if j ∈ Ij−1 theny[j . . . 2j − 2] = y[1 . . . j − 1] implyingy[1 . . . 2j − 2] = y[1 . . . j − 1]2 .
∀ t ∈ Ij−1 :if t + j − 1 ∈ Ij−1 then t ,→ I2j−2
if 2j − 1 ≥ ` then stop and output FAILURE
else j := 2j − 1
if j ∈/ Ij−1 then∀ t ∈ Ij−1 :if y[t + j − 1] = y[j] then t ,→ Ij
if ` − j + 1 ∈ Ij
thenstop with success and output y[1 . . . j]
if j ≥ ` then stop and output FAILURE
else j := j + 1

y = w ν1 = ν2 w
for some nonempty strings ν1 , ν2 . If |w| ≤ |y|/2 theny can be written in the formy = wνw
for some string ν , that means w is a symmetry of y .
Since w was chosen maximal it is even the maximal
symmetry. If |w| > |y|/2 then in the representationy = w ν1 = ν2 w the string w overlaps with itself, thus
it cannot be used as a symmetry. However, let κ denotethe length of the νi , r = ` − κ the length of w , andr0 := ` mod κ . Thenw[κ + 1 . . . r] = w[1 . . . r − κ] ,which implies in particular w[1 . . . κ] = w[κ+1 . . . 2κ] .
In the same way, w[κ+1 . . . 2κ] = w[2κ+1 . . . 3κ] , thus
w can be written as
w = w[1 . . . κ] br/κc w[1 . . . r0 ]andy = w[1 . . . κ] br/κc +1 w[1 . . . r0 ],where w[1 . . . r0 ] is empty for r0 = 0 . Now define(w,
if |w| ≤ `/2,w[1 . . . κ], if r0 = 0,w0 :=w[1 . . . r0 ], otherwise .
Note that w0 is a symmetry of y . As already mentioned it is the maximal one in the first case, whereas
in the other cases the maximal one is w[1 . . . κ]`/2κ if
r0 = 0 , resp. w[1 . . . κ](`−κ)/2κ w[1 . . . r0 ] for r0 > 0 .
Symmetries of size between w0 and the maximal one
are of the form w[1 . . . κ]L w[1 . . . r0 ] for some 1 ≤ L <`/2κ . Having obtained w0 , iteratively in the same way
we first compute the maximal overlap of this string andfrom this a substring w1 , and so forth until for the firsttime wj has zero overlap. Then wj is the minimal
symmetry of y .
A maximal overlap (sometimes also called a maximal
border) can be computed in linear time, see for example [2], chapter 3.1, where an algorithm of complexity
2 |y| − 3 is described.
Given the maximal overlap, the string w0 can easily
be obtained in a linear number of steps. Since for all j
the length of wj is at most half the length of wj−1 thewhole iterative procedure stays linearly bounded.
Once we have found a symmetry u , computing thecomplete u –factorization of y is just a simple patternmatching of u against y , which can be done by wellestablished methods in linear time.
From a complete minimal factorization based on u1
other symmetries can be deduced by checking powers of
u1 and the equality of substrings between these powers.
This can be done in a linear number of operations.
+Let Σ+
thatsym denote the set of all strings in Σ
possess a symmetry and let

psym := Pr[Z ∈ Σ+
sym ] .
We require that the distribution is not restricted to
substitutions with symmetries – with positive probability also nonsymmetric substitutions should occur.
Assumption 4.
psym < 1 .
Now consider the event
Qg [Z] := {Z1 , . . . , Zg } ∈ Σ+sym .
Qg [Z] means that among the first g substitutions all
have a symmetry. Obviously,
Pr[Q [Z]] ≤ p g .
gsym

Define q(Z) := min{g | ¬Qg [Z]} . Similarly toLemma 1, one can show
Lemma 5. E[q(Z)] ≤ 1/(1 − psym ) .

5

BASIC SUBROUTINES: FACTORIZATIONS AND COMPATIBILITY

For a subset A of Σ∗ let PRE(A) and SUF(A) denotethe maximal common prefix and suffix of all strings in
A , respectively. Let mpre (A) and msuf (A) be theirlengths. The first goal of the algorithm is to recognize
the prefix w0 and suffix wm before the first and last
occurrence of the variable x , respectively, in the pattern π . In order to avoid confusion, x will be called
the pattern variable, where variable simply refers to any
data variable used by the learning algorithm.
The current information about the prefix and suffix is stored in the variables PRE and SUF . The remaining pattern learning is done with respect to thecurrent value of these variables. If the algorithm seesa new string X such that PRE({X, PRE}) 6= PRE or
SUF({X, SUF}) 6= SUF then these variables will be updated. We will call this the begin of a new phase.
Definition 4. For a string Y ∈ Σ+ a (PRE, SUF) factorization is defined as follows. Y has to startwith prefix PRE and end with suffix SUF . For the remaining middle part Y 0 we select a symmetry u1 . Thismeans Y can be written as Y = PRE u1c1 v1 u1d1 SUF+
for some strings u1 , v1 and c1 , d1 ∈ N .
If such a representation is not possible for a given
pair (PRE, SUF) then Y is said to have no (PRE, SUF)
–factorization.
Moreover, Y 0 may have other symmetries u2 , u3 , . . .
giving rise to factorizations Y = PRE uici vi uidi SUF+

for ci , di ∈ N . For simplicity, we assume that thesymmetries ui are ordered by increasing length, in particular u1 always denotes the minimal symmetry withcorresponding minimal factorization.
Lemma 6. Let Y = PRE u c1 v u d1 SUF be111

the minimal (PRE, SUF) –factorization of Y . Then,for every string Ỹ of the form Ỹ = PRE u1 ṽ u1 SUF
for some string ṽ , the minimal (PRE, SUF) –factorization of Ỹ is based on u1 , too.
Proof. That u1 gives rise to a factorization is obvious. There cannot be one of smaller length because this
implies that u1 has a symmetry and contradicts that
u1 is minimal for Y .
Though the following lemma is easily verified, it isimportant to establish the correctness of our learner presented below.
Lemma 7. Let π = w0 x v x wm be any pattern with#(π, x) ≥ 2 , let u ∈ Σ+ , and let Y = π[x/u] . ThenY has a (w0 , wm ) –factorization with base u and its
minimal (w0 , wm ) –factorization is based on the minimal symmetry u1 of u .
The results of Lemma 4 directly translate toLemma 8. The minimal base for a (PRE, SUF) –factorization of a string Y can be computed in timeO(|Y |) . All additional bases can be found in linear
time. Given a base, the corresponding (PRE, SUF) –factorization can be computed in linear time as well.
Definition 5. Two strings Y, Ỹ are said to be
directly compatible with respect to a given pair(PRE, SUF) if from their minimal (PRE, SUF) –factorizations a single pattern ψ = ψ(Y,Ỹ) can be derived
from which both strings can be generated. More precisely, it has to hold:
Y = PRE u1c1 v1 u1d1 SUF and˜Ỹ = PRE ũ1c̃1 ṽ1 ũ1d1 SUF , and forY:= u c1 − 1 v u d1 − 1 and
mid

1

1

1

˜
Ỹmid := ũ1c̃1 − 1 ṽ1 ũ1d1 − 1 every occurrence of u1
in Ymid – including further ones in v1 – is matchedin Ỹmid either by an occurrence of ũ1 (which indicatesthat at this place π has a pattern variable) or by u1
itself (indicating that the constant substring u1 occurs
in π ). In all the remaining positions Ymid and Ỹmid
have to agree.
We extend this compatibility notion to pairs consisting of a string Y and a pattern π . Y is directly compatible to π with respect to (PRE, SUF) if for the minimal symmetry u1 of the (PRE, SUF) –factorization of
Y holds π[x/u1 ] = Y .
The following lemma is easily verified.
Lemma 9. Assume that (PRE, SUF) = (w0 , wm )has the correct value. If a string Y is generated fromπ by substituting the pattern variable by a nonsymmetric string u then the string u1 on which its minimal(PRE, SUF) –factorization is based equals u . Thus, Y
is directly compatible to π .

Proof. It is easy to see that for a nonsymmetric stringu the string
Y = π[x/u] = w0 uα1 w1 uα2 w2 . . . wm−1 uαm wm
has u as the basis for its minimal (w0 , wm ) –factorization. That u gives rise to a factorization is obvious, and if there were a smaller one it would imply
that u has a symmetry. Since the constant substrings
w1 , . . . , wm−1 may contain u as a substring the actual factorization may show more powers of u , but it
is unique since occurrences of u cannot overlap – again
because u is nonsymmetric. If the constant substring
wi of π has a decomposition with respect to u of theform uβi,0 ωi,1 uβi,1 . . . ωi,ni uβi,ni , where the βi,j areintegers and the ωi,j are substrings not containing u ,then the middle part Ymid of Y without prefix, suffix
and first and last occurrence of u looks likeuα1 −1 uβ1,0 ω1,1 uβ1,1 . . . ω1,n1 uβ1,n1 uα2 uβ2,0 ω2,1 uβ2,1. . . ω2,n2 uβ2,n2 uα3 . . . uαm −1 .
When checking direct compatibility of Y against π
it becomes obvious whether a substring u in Y corresponds to a variable or not.
If one of the substitutions u, ũ for Y = π[x/u] ,resp. Ỹ = π[x/ũ] is a prefix of the other, let us sayũ = u u0 for some nonempty string u0 then there may
be an ambiguity if u u0 appears as a constant substringin Ymid . If this is not followed by another occurrenceof u0 it can easily be detected. In general, if u u0 is aconstant in π then the number of occurrences following this substring will be the same in the corresponding
positions in Ymid and Ỹmid , otherwise it has to be one
more in Ỹ .
Using this observation it is easy to see that even insuch a case testing of direct compatibility is easy.
Lemma 10. Let the minimal factorizations of two
strings Y, Ỹ be given. Then by a single joint scan one
can check whether they are directly compatible, and if
yes construct their common pattern ψ(Y, Ỹ ) . The scancan be performed in O(|Y | + |Ỹ |) bit operations.
Moreover, for a pattern π it can be checked in timeO(|Y | + |π|) whether Y is directly compatible to π .
The extra effort in the degenerated case of u beinga prefix of ũ can be omitted if in this case the patternmatching is done from right to left since the procedure
is completely symmetric. This will only fail if u is bothprefix and suffix of ũ , implying that ũ = u u0 u . But
this means that ũ has a symmetry and thus cannot
derive from a minimal factorization of Ỹ .
Definition 6. A string Y is downwards compatible to a string Ỹ with respect to a given pair(PRE, SUF) if for some κ ≥ 1, from the minimal (PRE,SUF) –factorization of Y and the κ -th (PRE, SUF) –factorization of Ỹ a single pattern ψ = ψ(Y, Ỹ , κ) canbe derived from which both strings can be generated.
We also say that Ỹ is upwards compatible to Y .

Again, these notions are extended to pairs consistingof a string and a pattern.
Lemma 11. Assume (PRE, SUF) = (w0 , wm ) having the correct value. Let Y = π[x/u] for a nonsymmetric string u . Any other string Ỹ in L(π) obtainedby substituting the pattern variable by a string ũ forwhich u is not a symmetry is upwards compatible to Y
with respect to (PRE, SUF) .
The pattern ψ(Y, Ỹ ) equals the pattern π to be learned.
Given the (PRE, SUF) –factorization of both strings,
ψ(Y, Ỹ ) can be constructed in time at most O((1 +sym(Ỹ )) · (|Y | + |Ỹ |)) , where sym(Ỹ ) := sym(ũ) denotes the number of symmetries of the string ũ thatgenerates Ỹ .
Furthermore, given a pattern ψ and the factorizationof a string Y it can be checked in time O(|Y | + |ψ|)whether Y is upwards compatible to ψ . For Y , downwards compatibility to ψ can be checked and ψ(Y, ψ, ·)can be constructed in linear time, too.
Proof. Let u be nonsymmetric, Y = π[x/u] , andletYmid = uα1 −1 uβ1,0 ω1,1 uβ1,1 . . .
ω1,n1 uβ1,n1 uα2 uβ2,0 ω2,1 uβ2,1 . . . uαm −1 .
IfỸ = π[x/ũ] = w0 ũα1 w1 ũα2 w2 . . . wm−1 ũαm wmthen Ỹ has a (w0 , wm )–factorization based on ũ . Notethat this factorization will not be minimal if ũ itself
has symmetries. Since w1 , . . . , wm−1 may contain ũ
the actual factorization may show more powers of ũ .
By assumption, u is not a symmetry for ũ andsince one may either work from left to right or rightto left we may assume that u is not a prefix of ũ .
When comparing Ymid to Ỹmid after the first α1 − 1
occurrences of u in Ymid have been read and matchedagainst occurrences of ũ in Ỹmid the next occurrence ofu in the substring uβ1,0 will be detected as a constant.
This is because this substring also occurs in Ỹmid andu is not a prefix of ũ . The same holds for the otheroccurrences of u in Y .
Given the corresponding factorizations, checking
whether Ymid and Ỹmid match can be done by a single pass over the strings and has linear time complexity. However, one has to find that factorization of Ỹ
that matches the one of Y . Considering the symmetries of Ỹ in increasing length this will be symmetrysym(ũ) . In the worst-case, if ũ contains only one symbol sym(ũ) can be as large as |ũ|/2 , but such a casewill be easier to handle.
This can even be sped-up. One observation is thata string with c symmetries yields a least by a factor cmore occurrences of its minimal symmetry in the minimal factorization. Thus, once one output pattern ψ hasbeen computed, which also gives the number of occurrences of the pattern variable, strings Ỹ with a muchlarger number of occurrences in the minimal factorization based on a string ũ1 can simply be discarded unlessψ itself contains lots of substrings ũ1 . More precisely,
let#(Y, u):=maximal number of nonoverlapping
occurrences of u in Y .

PRE and SUF are not defined. Thus, as long as thealgorithm has seen only one string, it will output thisstring.
Otherwise, we try to generate a pattern from 2 compatible strings received so far. If this is not possible or if
one of the examples does not have a factorization thenthe output will be the default pattern

Since u is nonsymmetric and Y = π[x/u]#(Y, u) = #(π, x) + #(π, u) .
For Ỹ = π[x/ũ] and a symmetry ũi of a factorizationof Ỹ such that ũi is a substring of ũ it holds,#(Ỹ , ũi ) = #(ũ, ũi ) · #(π, x) + #(π, ũi ) .
Let ψ a pattern that is supposed to equal the pattern
π to be learned. Thus, to find the right factorization ofa string Ỹ to check upwards compatibility against ψfrom the minimal factorization one can compute#(Ỹ , ũ1 ) − #(ψ, ũi )#(ψ, x)to get an estimate on #(ũ, ũ1 ) . When all symmetriesof Ỹ are known it is then easy to find that string ũ directly that matches this value. However, when checking
upwards compatibility of a string Ỹ to a string Y , wedo not have a precise estimate on #(π, x) , there is only
the upper bound #(Y, u) available from the factorization of Y . This implies a lower bound on #(ũ, ũ1 ) of
the form#(ũ, ũ1 ) ≥#(Ỹ , ũ1 ) − #(Y, ũi ).
#(Y, u)Thus, unless #(π, u) is relatively large compared to#(π, x) this gives a good approximation which symmetry of Ỹ should be used.
Note that one cannot decide whether a string Y wasgenerated by substitution with a nonsymmetric stringby counting the number of its factorizations – which islikely to be one. However, there are rare cases with morefactorization than the one induced by the substitution –for example, if α1 and αm have a common nontrivial
divisor or even if α1 = αm = 1 , but by chance w1 =v u v 0 and wm−1 = v 00 u v for some arbitrary stringsv, v 0 , v 00 .

6

THE ALGORITHM

The learner may not store all example strings he has
seen so far. Therefore let A = Ag = Ag (X ) denote theset of examples he remembers after having got the firstg examples of the random sequence X = X1 , X2 , . . . ,and, similarly, let PREg and SUFg be the values ofthe variables PRE and SUF at that time. We will callthis round g of the learning algorithm.
Let us first describe the global strategy of the learning procedure. When the pattern is a constant π = w
all example strings are equal to w and the variables

ψ0 := PREg x SUFg .
If a non-default pattern has been generated as a hypothesis further examples are tested for compatibility
with respect to this pattern. As long as the test is positive the algorithm will stick to this hypothesis, else a
new pattern will be generated. In the simplest versionof the algorithm we remember only a single example ofthe ones seen so far. Instead of a set A we will use asingle variable Y .
The One-Variable Pattern Learning Algorithm
Y := X1 ;PRE := X1 ;SUF := X1 ;output X1 ;for g = 2, 3, 4, . . . do
PRE0 := PRE ; SUF0 := SUF ;ψ := output of previous round;read the new example Xg ;if Xg = ψ then output ψ , else
PRE := PRE({PRE, Xg }) ;SUF := SUF({SUF, Xg }) ;if PRE 6= PRE0 or SUF 6= SUF0 thencompute the (PRE, SUF) –factorization of Y ;ψ0 := PRE x SUF ;ψ := ψ0 endif;
compute the (PRE, SUF) –factorization of Xg ;case 1: Y does not have a factorization
then output ψ0 :case 2: Xg does not have a factorization
then output ψ0 and Y := Xg ;case 3: ψ = ψ0
if Xg is downwards compatible to Y
then output ψ(Xg , Y, ·) ,else output ψ0 ,if Xg is shorter than Y then Y := Xg ;case 4: Xg is upwards compatible to ψ
then output ψ ;case 5: Xg is downwards compatible to ψ
then output ψ(Xg , ψ, ·) and Y := Xg ;else output ψ0 .

7

PROOF OF CORRECTNESS

Since the example strings are generated at random it
might happen that only “bad examples” occur in whichcase no learning algorithm can eventually come up witha correct hypothesis. Therefore, the following claims
cannot hold absolutely in a probabilistic setting, butthey will be true with probability 1. Remember thatπ = w0 xα1 w1 xα2 w2 . . . wm−1 xαm wm is the pattern tobe learned. Since not all substitutions start with thesame symbol or end with the same symbol (rememberthat we have assumed p < 1 ) with probability 1 asequence X contains strings Xi , Xj , Xk , where Xκ =π[x/uκ ] such thatui [1] 6= uj [1]andui [−1] 6= uk [−1] .

Note that j may be equal to k . Let g be the maximumof i, j, k and consider a triple for which g is minimal.
By the construction of the sets PRE and SUF roundg will start a new phase in which now the variables
PREg = w0 and SUFg = wm have the correct values.
We do not care about the output of the algorithm
before this final phase has been reached. It remains toshow that the algorithm will converge in the final phase.
For this purpose, let us distinguish whether the patterncontains the variable only once, in which case there will
be examples without any symmetry, or more than once(the case that the pattern does not contain any variable
is obvious).
If π = w0 xw1 then with probability 1 there will
be an example Xg obtained from a substitution [x/u]with a nonsymmetric string u . Then Xg does not havea (PREg , SUFg ) –factorization and thus case 2 occurs.
Since Y is set equal to X from then on always case 1
occurs. The algorithm will always choose case 1 andoutput ψ0 , which in this case is the correct answer.
Otherwise, the pattern contains the variable at least
twice and any example does have a (PREg , SUFg ) –factorization. Lemma 11 shows that a nonsymmetric substitution generates a string that is downwards compatible to any other string in L(π) . Thus, as soon as Xg issuch a string, which again happens with probability 1,
the output ψg will equal the pattern π . Furthermore
the algorithm will never change its output from thisround on since case 4 “ Xg0 is upwards compatible toψ ” will hold for any g 0 > g .
Let us summarize these properties in the following
Lemma 12. After the algorithm has detected thecorrect prefix and suffix it will converge immediately tothe correct hypothesis π as soon it gets the first example
generated by a nonsymmetric substitution.

8

COMPLEXITY ANALYSIS

Let ψg denote the output of round g , and Yg the valueof Y at the end of that round. Let T imeg (X ) denotethe number of bit operations in round g on example
sequence X , and recall that Z and X are defined as
random variables for the substitutions and examples,
respectively.
Lemma 13. For each round g it holds
E[T imeg (X )] ≤ O E[|X|] · 1 + E[sym(Z)]≤ O n · E[|Z|] · 1 + E[sym(Z)] .

Proof. By Lemma 10 and 11 in each round g thenumber of bit operations can be estimated by
T imeg (X ) ≤O(|Yg−1 |) + O(|Xg |)+ max {O((|Yg−1 | + |Xg |) · (1 + sym(Yg−1 )),O((|ψg−1 | + |Xg |) · (1 + sym(Xg )),O(|ψg−1 | + |Xg |)}
≤ O |Yg−1 | + |Xg | + |ψg−1 | + |Yg−1 | · sym(Yg−1 )+ |Xg | · sym(Yg−1 ) + |ψg−1 | · sym(Xg )+ |Xg | · sym(Xg ) .
By construction of the algorithm and the fact that apattern is never longer than an example string it generates we can bound E[|Xg |] as well as E[|Yg−1 |] andE[|ψg−1 |] by E[|X|] . Moreover, Assumption 3 directly
implies that E[|Xg |·sym(Xg )] and E[|Yg−1 |·sym(Yg−1 )]are both bounded by O(E[|X|]·E[sym(Z)]) . Note, that
Xg is independent of Yg−1 and ψg−1 . Thus
E[|Xg | · sym(Yg−1 )]= E[|Xg |] · E[sym(Yg−1 )]= E[|X|] · E[sym(Z)]andE[|ψg−1 | · sym(Xg )]= E[|ψg−1 |] · E[sym(Xg )]≤ E[|X|] · E[sym(Z)] .

This simplifies the expectation toE[T imeg (X )] ≤
O E[|Yg−1 |] + E[|Xg |] + E[|ψg−1 |]+ E[|Yg−1 | · sym(Yg−1 )] + E[|Xg | · sym(Yg−1 )]+ E[|ψg−1 | · sym(Xg )] + E[|Xg | · sym(Xg )]≤ O E[|X|] + E[|X|] · E[sym(Z)] .

Now we can also bound the total learning time.
Lemma 14. The expected total learning time isbounded by

 1

1
+
.
O n · E[|Z|] · (1 + E[sym(Z)]) ·1 − p 1 − psym
Since E[|Z|]) , E[sym(Z)] , p , and psym are characterized by the distribution for substituting the patternvariable they are all independent of the problem size.
This means the complexity grows linear with the size ofthe problem.
Proof. The number of rounds can be bounded by
the number of rounds to reach the final phase plus thenumber of rounds in the final phase till ψg = π . By
Lemma 1 and 5 the expectation of both is a constantthat only depends on the probabilities p and psym .
Let G be a random variable that counts the number ofrounds till convergence. Then,
1
1
E[G] ≤ O+.
(1)
1 − p 1 − psym

Let T imetotal (X ) denote the total number of operations on example sequence X . Then
GX
T imetotal (X ) =T imeg (X )
g=1

=

X

Pr[G = t] ·tX

T imeg (X )

g=1

t≥2

and
E[T imetotal (X )] =
t
hX
i
X
E
Pr[G = t] ·T imeg (X ) ≤
g=1

t≥2

 hX
i
O E
Pr[G = t] · t · E[|X|] · 1 + E[sym(Z)]t≥2≤
O E[|X|] · (1 + E[sym(Z)]) · E

hX

Pr[G = t] · t

i

!

t



= O E[|X|] · (1 + E[sym(Z)]) · E[G] ≤


 1
1
+
O n · E[|Z|] · (1 + E[sym(Z)]) ·1 − p 1 − psym
= O(n) .
Summarizing, we state the main result of this paper.
Theorem 1. One-variable pattern languages can beinferred in linear expected total learning time for all distributions that fulfill the Assumptions 1 through 4 madeabove.
Clearly, the expected value of a random variable isonly one aspect of its distribution. Looking at potential
applications of our learning algorithm, a hypotheticaluser might be interested in knowing how often the total learning time exceeds its average substantially. For
answering this question we could compute the varianceof the total learning time. Then Chebyshev’s inequality
provides the desired tail bounds. However, in our particular setting, there is an easier way to figure out how
good the distribution of the total learning time is centered around its expected value. The main ingredient is
the following additional nice feature of our algorithm.
It convergence immediately in the final phase when an
example with a nonsymmetric replacement occurs.
The expectation of this event is E[G] , hence withprobability at least 1/2 the algorithm converges within
2 E[G] rounds. If this did not happen, no matter which
bad examples have occurred, again there will be convergence in the next 2 E[G] rounds with probability atleast 1/2 . Thus, the probability of failure decreases exponentially with the number of rounds, more precisely,
for allh m ∈ N it holds:i
Pr T imetotal ≥ 2 · m · E[T imetotal ]≤ 2−m .

(2)

Since the distribution of T imetotal decreases exponentially, all higher moments of it exist. In particular, we may conclude that the variance of T imetotal issmall.

9

CONCLUSIONS

We have shown that one-variable pattern languages arelearnable for basically all meaningful distributions within an optimal linear total learning time on the average.
The algorithm obtained is quite simple and is based onsymmetries that occur in such languages. Thus, ourapproach to minimize the expected total learning time
turned out to be quite satisfactory.
Additionally, our learner requires only space that islinear in the length of the target pattern. Therefore,
it is not only faster than the algorithms presented by
Angluin [1] and Erlebach et al. [3] but also more spaceefficient. The only known algorithm using even lessspace is Lange and Wiehagen’s [7] learner. But theiralgorithm is only successful for a much smaller class ofprobability distributions, since it requires shortest examples in order to converge. On the other hand, ourlearner maintains the incremental behavior of Lange
and Wiehagen’s [7] algorithm. While it is no longer
iterative, it is still a bounded example memory learner.
A learner is called iterative, if it uses only its last guess
and the next example in the sequence of example stringsfor computing its actual hypothesis. A bounded example memory learner is additionally allowed to memorize
an a priori bounded number of examples it already has
had access to during the learning process. For more
information concerning these learning models, we refer
the reader to Lange and Zeugmann [8].
Moreover, our algorithm does not only possess an
expected linear total learning time, but also very goodtail bounds. Note that, whenever learning in the limit isconsidered one cannot decide whether or not the learnerhas already converged to a correct hypothesis. If convergence is decidable, we arrive at finite learning. It iseasy to see that one-variable pattern languages are notfinitely learnable. On the other hand, a bit of priorknowledge about the underlying probability distributions nicely buys a stochastically finite learner with highconfidence. Recall that the number G of rounds depends only on p and psym . Now, assuming that one
has the additional knowledge of upper bounds for bothp and psym , Formula 1 can be used to estimate the expected number of rounds. Let G̃ be this estimate, andlet δ ∈ (0, 1) be the confidence parameter given to themodified learner as additional input. Now, the modified
learner computes the least m such that 1 − 2m ≥ δ ,and runs our algorithm for 2·m· G̃ rounds. While doing
this, no output is provided. After having finished theserounds, the modified learner outputs the last guess πmade by our algorithm, and stops thereafter. Now, using the same argument as above for proving (2), one
easily sees that π must be correct for the target to belearned with probability at least δ . Furthermore, thetotal learning time remains linear in the length of thetarget pattern.
Note that stochastically finite learning with highconfidence is different from PAC-learning. First, it is
not completely distribution independent. Thus, fromthat perspective, this variant is weaker than the PACmodel. But the hypothesis computed is probably exactly correct. Moreover, the learner receives exclusively
positive data while the correctness of its hypothesis ismeasured with respect to all data. Hence, from thatperspective, our model of stochastically finite learningwith high confidence is stronger than the PAC-model.
Our approach also differs from U-learnability introduced by Muggleton [9]. First of all, our learner is fed
positive examples only, while in Muggleton’s [9] model,
examples labeled with respect to their containment in
the target language are provided. Next, we do not makeany assumption concerning the distribution of the target patterns. Furthermore, we do not measure the expected total learning time with respect to a given classof distributions over the targets and a given class of
distributions for the sampling process, but exclusively
in dependence on the length of the target. Finally, we
require exact learning and not approximately correct
learning.
We have implemented the algorithm and the reader
is referred to http://www.itheoi.mu-luebeck.de/pages/
reischuk/Algor/learn/LearnUnser.html for getting access to the resulting Java-applets.
Next, we shortly discuss possible directions of further research. An obvious extension would be to consider k -variable pattern languages for small fixed k >1 . Already for k = 2 the situation becomes considerably more complicated and requires additional tools.
Another direction to pursue would be to learn languages that are the union of at most ` one-variable
pattern languages for some fixed ` .
Finally, the approach presented in this paper seems
to be quite suited to tolerate errors in the example data.
Let us assume that there is some (small) probability thaterror model 1: in an example string X[1] . . . X[l] asymbol X[i] is changed to a different one,error model 2: X[i] is changed to a different symbolor removed or replaced by two symbols X[i]σ for someσ ∈ Σ.
A property of the pattern language like the common
prefix of all strings now is only accepted if it is supported by a large percentage of examples. The details
and modification of the algorithm will be given in another paper.

References[1] D. Angluin. Finding Patterns Common to a Set ofStrings, Journal of Computer and System Sciences
21:46–62, 1980.
[2] M. Crochmore and W. Rytter. Text Algorithms,
Oxford University Press, 1994.
[3] T. Erlebach, P. Rossmanith, H. Stadtherr, A. Steger and T. Zeugmann. Efficient learning of onevariable pattern languages from positive data, DOITR-128, Kyushu University, Fukuoka, Japan, 1996.

[4] T. Erlebach, P. Rossmanith, H. Stadtherr, A. Steger and T. Zeugmann. Learning One-Variable Pattern Languages Very Efficiently on Average, in
Parallel, and by Asking Queries, in M. Li and
A. Maruoka (Eds.), Proc. 8th International Workshop on Algorithmic Learning Theory, 1997, Lecture Notes in Artificial Intelligence 1316, 260–276,
Springer-Verlag.
[5] E. Gold. Language identification in the limit, Information & Control 10:447–474, 1967.
[6] M. Kearns and L. Pitt. A polynomial-time algorithm for learning k -variable pattern languages
from examples, in R. Rivest, D. Haussler and
M. K. Warmuth (Eds.), Proc. 2nd Annual ACM
Workshop on Computational Learning Theory,
1989, 57–71, Morgan Kaufmann.
[7] S. Lange and R. Wiehagen. Polynomial-time inference of arbitrary pattern languages, New Generation Computing 8:361–370, 1991.
[8] S. Lange and T. Zeugmann. Incremental Learning from Positive Data, Journal of Computer and
System Sciences 53(1):88–103, 1996.
[9] S. Muggleton. Bayesian Inductive Logic Programming, in M. Warmuth (Ed.), Proc. 7th Annual
ACM Conference on Computational Learning Theory, 1994, 3–11, ACM Press.
[10] L. Pitt. Inductive inference, DFAs and computational complexity, in K.P. Jantke (Ed.), Proc. 2nd
International Workshop on Analogical and Inductive Inference, 1989, Lecture Notes in Artificial Intelligence 397, 18–44, Springer-Verlag.
[11] R. Reischuk and T. Zeugmann. Learning OneVariable Pattern Languages in Linear Average
Time, DOI-TR-140, Kyushu University, Fukuoka,
Japan, 1997.
http://www.i.kyushu-u.ac.jp/ thomas/tr.html[12] A. Salomaa. Patterns, (The Formal Language Theory Column), EATCS Bulletin 54:46–62, 1994.
[13] A. Salomaa. Return to patterns, (The Formal Language Theory Column), EATCS Bulletin 55:144–
157, 1994.
[14] R. Schapire. Pattern languages are not learnable,
in M.A. Fulk and J. Case (Eds.), Proc. 3rd Annual ACM Workshop on Computational Learning
Theory, 1990, 122–129, Morgan Kaufmann.
[15] T. Shinohara and S. Arikawa. Pattern inference, in“Algorithmic Learning for Knowledge-Based Systems,” (K. Jantke and S. Lange (Eds.)) Lecture
Notes in Artificial Intelligence 961, 1995, 259–291,
Springer-Verlag.
[16] R. Wiehagen and T. Zeugmann. Ignoring data may
be the only way to learn efficiently, Journal of Experimental and Theoretical Artificial Intelligence
6:131–144, 1994.
[17] T. Zeugmann. Lange and Wiehagen’s pattern language learning algorithm: An average-case analysis
with respect to its total learning time, RIFIS-TR
111, Kyushu University, Fukuoka, Japan, 1995, toappear in Annals of Mathematics and Artificial Intelligence.