Learning a Subclass of Regular Patterns in
Polynomial TimeJohn Case a,1 Sanjay Jain b,2 Rüdiger Reischuk cFrank Stephan d,3 Thomas Zeugmann ea Department of Computer and Information Sciences, University of Delaware,

Newark, DE 19716-2586, USA, case@cis.udel.edu
b School of Computing, National University of Singapore, Singapore 117543,

sanjay@comp.nus.edu.sg
c Institute for Theoretical Informatics, University at Lübeck, Ratzeburger Allee 160,

23538 Lübeck, Germany, reischuk@tcs.uni-luebeck.ded School of Computing and Department of Mathematics, National University ofSingapore, Singapore 117543, fstephan@comp.nus.edu.sg
e Division of Computer Science, Hokkaido University, N-14, W-9, Sapporo

060-0814, Japan, thomas@ist.hokudai.ac.jp

Abstract
An algorithm for learning a subclass of erasing regular pattern languages is presented. On extended regular pattern languages generated by patterns π of theform x0 α1 x1 . . . αm xm , where x0 , . . . , xm are variables and α1 , . . . , αm strings ofterminals of length c each, it runs with arbitrarily high probability of success using
a number of examples polynomial in m (and exponential in c ). It is assumed thatm is unknown, but c is known and that samples are randomly drawn according tosome distribution, for which we only require that it has certain natural and plausible
properties.
Aiming to improve this algorithm further we also explore computer simulations ofa heuristic.

1

Supported in part by NSF grant number CCR-0208616 and USDA IFAFS grant
number 01-04145.
2 Supported in part by NUS grant number R252-000-127-112.
3 Supported in part by NUS grant number R252-000-212-112. Most work was done
while F. Stephan stayed with the National ICT Australia which is funded by theAustralian Government’s Department of Communications, Information Technology
and the Arts and the Australian Research Council through Backing Australia’s
Ability and the ICT Centre of Excellence Program.

Preprint submitted to Elsevier Science

4 August 2006

1

Introduction

The pattern languages were formally introduced by Angluin [2]. A patternlanguage is (by definition) one generated by all the positive length substitution
instances in a pattern, such as, for example, 01xy211zx0 — where the variables(for substitutions) are letters and the terminals are digits.
Since then, much work has been done on pattern languages and extended pattern languages (which also allow empty substitutions) as well as on various
special cases of the above, see, for example, [2,6–8,13,15,22–25,27–29,32,35]
and the references therein. Furthermore, several authors have also studied finite unions of pattern languages (or extended pattern languages), unbounded
unions thereof and also of important subclasses of (extended) pattern languages, see, for example, [5,10,14,33,36,39]. Related work deals also with tree
patterns, see, for example, [1,10,12].
Nix [21] as well as Shinohara and Arikawa [34,35] outline interesting applications of pattern inference algorithms. For example, pattern language learningalgorithms have been successfully applied toward some problems in molecular biology, see [31,35]. Pattern languages and finite unions of pattern languages turn out to be subclasses of Smullyan’s [37] Elementary Formal Systems(EFSs), and Arikawa, Shinohara and Yamamoto [3] show that the EFSs canalso be treated as a logic programming language over strings. The investigations of the learnability of subclasses of EFSs are interesting because they yieldcorresponding results about the learnability of subclasses of logic programs.
Hence, these results are also of relevance for Inductive Logic Programming(ILP) [4,16,18,20]. Miyano et al. [19] intensively studied the polynomial-timelearnability of EFSs.
In the following we explain the main philosophy behind our research as wellas the ideas by which it emerged. As far as learning theory is concerned,
pattern languages are a prominent example of non-regular languages that canbe learned in the limit from positive data (see Angluin [2]). Gold [9] has
introduced the corresponding learning model. Let L be any language; then atext for L is any infinite sequence of strings containing eventually all membersof 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 L. The hypotheses are chosen from a prespecified
set called hypothesis space. The sequence of hypotheses has to converge to acorrect description of the target language.
Angluin [2] provides a learner for the class of all pattern languages that isbased 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 thisproperty generates a proper subset of the language generated by π. However no2

efficient algorithm is known for computing descriptive patterns. Thus, unlesssuch an algorithm is found, it is even infeasible to compute a single hypothesisin practice by using this approach.
Therefore, one has considered restricted versions of pattern language learningin which the number k of different variables is fixed, in particular the case of asingle variable. Angluin [2] 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. Note that this algorithm is also based on computing descriptive
patterns even of maximum length. Giving up the idea to find descriptive patterns of maximum length but still computing descriptive patterns, Erlebach etal. [8] arrived at a one-variable pattern language learner having update timeO(`2 log `), where ` is as above. Moreover, they also studied the expected total
learning time of a variant of their learner and showed an O(|π|2 log |π|) upper bound for it, where π is the target pattern. Subsequently, Reischuk andZeugmann [25] designed a one-variable pattern language learner achieving the
optimal expected total learning time of O(|π|) for every target pattern π andfor almost all meaningful distributions. Note that the latter algorithm does
not compute descriptive patterns.
Another important special case extensively studied are the regular patternlanguages introduced by Shinohara [32]. These are generated by the regularpatterns, that is, patterns in which each variable that appears, appears only
once. The learners designed by Shinohara [32] for regular pattern languages
and extended regular pattern languages also compute descriptive patterns
for the data seen so far. These descriptive patterns are computable in timepolynomial in the length of all examples seen so far.
When applying these algorithms in practice, another problem comes into play,that is, all the learners mentioned above are only known to converge in thelimit to a correct hypothesis for the target language. However the stage of
convergence is not decidable. Thus, a user never knows whether or not thelearning process has already been finished. Such an uncertainty may not betolerable in practice.
Consequently, one has tried to learn the pattern languages within Valiant’s[38] PAC model. Shapire [30] could show that the whole class of pattern languages is not learnable within the PAC model unless P/poly = N P /poly forany hypothesis space that allows a polynomially decidable membership problem. Since membership is N P -complete for the pattern languages, his result
does not exclude the learnability of all pattern languages in an extended PAC
model, that is, a model in which one is allowed to use the set of all patterns
as hypothesis space.
However, Kearns and Pitt [13] have established a PAC learning algorithm
for the class of all k-variable pattern languages, that is, languages generated
by patterns in which at most k different variables occur. Positive examples
3

are generated with respect to arbitrary product distributions while negative
examples are allowed to be generated with respect to any distribution. Additionally, the length of substitution strings has been required to be polynomially related to the length of the target pattern. Finally, their algorithm
uses as hypothesis space all unions of polynomially many patterns that havek or fewer variables – more precisely, the number of allowed unions is at
most poly(|π|, s, 1/ε, 1/δ, |Σ|), where π is the target pattern, s the bound on
the length of substitution strings, ε and δ are the usual error and confidence
parameter, respectively, and Σ is the alphabet of terminals over which thepatterns are defined. The overall learning time of their PAC learning algorithm is polynomial in the length of the target pattern, the bound for the
maximum length of substitution strings, 1/ε, 1/δ and |Σ|. The constant in
the running time achieved depends doubly exponential on k and thus, theiralgorithm becomes rapidly impractical when k increases.
As far as the class of extended regular pattern languages is concerned, Miyano
et al. [19] showed the consistency problem to be N P -complete. Thus, theclass of all extended regular pattern languages is not polynomial-time PAC
learnable unless RP = N P for any learner that uses the regular patterns as
hypothesis space.
This is even true for REGPAT1 , that is, the set of all extended regular patternlanguages where the length of terminal strings is 1, see below for a formal
definition. The latter result follows from [19] via an equivalence proof to thecommon subsequence languages studied in [17].
In the present paper we also study the special cases of learning the extended
regular pattern languages. On the one hand, they already allow non-trivial
applications. On the other hand, it is by no means easy to design an efficientlearner for these classes of languages as noted above. Therefore, we aim todesign an efficient learner for an interesting subclass of the extended regularpattern languages which we define next.
Let Lang(π) be the extended pattern language generated by pattern π. For
c > 0, let REGPATc be the set of all Lang(π) such that π is a pattern of theform x0 α1 x1 α2 x2 . . . αm xm , where each αi is a string of terminals of length cand x0 , x1 , x2 , . . . , xm are distinct variables.
We consider polynomial time learning of REGPATc for various data presentations and for natural and plausible probability distributions on the input data.
As noted above, even REGPAT1 is not polynomial-time PAC learnable unless
RP = N P . Thus, one has to restrict the class of all probability distributions.
Then, the conceptional idea is as follows (see [25–27]).
We explain it here for the case mainly studied in this paper, learning fromtext (in our notation above). One looks again at the whole learning process
as learning in the limit. So, the data presented to the learner are growing
4initial segments of a text. However, instead of allowing arbitrary text, we consider texts drawn according to some fixed probability distribution. Next, one
determines the expected number of examples needed by the learner until convergence. Let E denote this expectation. Assuming prior knowledge about theunderlying probability distribution, E can be expressed in terms the learner
may use conceptually to calculate E. Using Markov’s inequality, one easily
sees that the probability to exceed this expectation by a factor of t is boundedby 1/t. Thus, we introduce, as in the PAC model, a confidence parameter δ.
Given δ, one needs roughly E/δ examples to converge with probability at least
1 − δ. Knowing this, there is of course no need to compute any intermediate
hypotheses. Instead, now the learner firstly draws as many examples as needed
and then it computes just one hypothesis from it. This hypothesis is output,
and by construction we know it to be correct with probability at least 1 − δ.
Thus, we arrive at a learning model which we call probabilistically exact learning 4 , see Definition 7 below. Clearly, in order to have an efficient learner, one
also has to guarantee that this hypothesis can be computed in time polynomial in the length of all strings seen. For arriving at an overall polynomial-timelearner, it must be also ensured that E is polynomially bounded in a suitableparameter. We use the number of variables occurring in the regular target
pattern, the maximal length of a terminal string in the pattern and a term
describing knowledge about the probability distribution as such a parameter.
We shall provide a learner which succeeds with high probability in polynomial
time on every text which is drawn to any admissible probability distribution
prob. An admissible distribution prob has to satisfy, besides some normality
conditions, also the condition
prob(σ) ≥∞X
1|Σ|−|σ|for σ ∈ L, where≤1.
pol(|σ|)n=0 pol(n)Here, the polynomial pol is {2, 3, . . .}-valued and increasing, the language L isP
a subset of Σ∗ and the pause-symbol # has the probability 1 − σ∈L prob(σ).
This condition guarantees that long examples are still sufficiently frequent.
The more precise requirements for prob and its texts are given in Definition 5.
Furthermore, probabilistically exact learnability from text for non-empty languages implies probabilistically exact learnability from pause-free texts andinformants, where pause-free texts are those generated by probability distriP
butions satisfying σ∈L prob(σ) = 1.
Our algorithm is presented in detail in Section 3 below and runs with all
three models of data presentation in a uniform way. The complexity bounds
are described more exactly there, but, basically, the algorithm can be madeto run with arbitrarily high probability of success on extended regular languages generated by patterns π of the form x0 α1 x1 ...αm xm for unknown m
4This model has also been called stochastic finite learning (see [25–27]).

5

but known c, from number of examples polynomial in m (and exponential inc), where α1 , ..., αm ∈ Σc . Here Σc denotes the set of all strings over Σ oflength c.
Note that having our patterns defined as starting and ending with variables
is not crucial. One can just handle patterns starting or ending with terminals
easily by looking at the data and seeing if they have a common suffix or prefix.
Our results more generally hold for patterns alternating variables and fixed
length terminal strings, where the variables are not repeated. Our statements
above and in Section 3 below involving variables at the front and end are morefor ease of presentation of proof.
While the main goal of the paper is to establish some polynomial bound forthe learning algorithm, Section 4 is dedicated to giving more explicit bounds
for the basic case that Σ = {0, 1} and c = 1. The probability distribution
satisfies|Σ|−|σ|prob(σ) =(|σ| + 1)(|σ| + 2)
for σ ∈ L and prob(#) = 1 − prob(L). Although the bounds for this basic caseare much better than in the general case, it seems that the current implementation of the algorithm is even more efficient than the improved theoreticalbounds suggest. Experiments have also been run for alphabets of size 3, 4, 5
and the pattern language classes REGPAT2 and REGPAT3 .

2Preliminaries

Let N = {0, 1, 2, . . .} denote the set of natural numbers and let N+ = N \ {0}.
For any set S, we write |S| to denote the cardinality of S. Furthermore, for all
real numbers s, t with s < t we use (s, t) to denote the open interval generated
by s and t, that is, (s, t) = {r | r is a real number and s < r < t}.
Let Σ be any finite alphabet such that |Σ| ≥ 2 and let V be a countably
infinite set of variables such that Σ ∩ V = ∅. Following a tradition in formal
language theory, the elements of Σ are called terminals. By Σ∗ we denote thefree monoid over Σ, and we set Σ+ = Σ∗ \ {λ}, where λ is the empty string.
As above, Σc denotes the set of strings over Σ with length c. We let a, b, . . .
range over terminal symbols from Σ and α, σ, τ, η over terminal strings fromΣ∗ . x, y, z, x1 , x2 , . . . range over variables. Following Angluin [2], we define
patterns and pattern languages as follows.
Definition 1 A term is an element of (Σ ∪ V )∗ . A ground term (or a word
or a string) is an element of Σ∗ . A pattern is a non-empty term.
A substitution is a homomorphism from terms to terms that maps each symbola ∈ Σ to itself. The image of a term π under a substitution θ is denoted πθ.
We next define the language generated by a pattern.
6

Definition 2 The language generated by a pattern π is defined as Lang(π) ={πθ ∈ Σ∗ | θ is a substitution}. We set PAT = {Lang(π) | π is a pattern}.
Note that we consider extended (or erasing) pattern languages, that is, avariable may be substituted with the empty string λ. Though allowing empty
substitutions may seem a minor generalization, it is not. Learning erasing
pattern languages is more difficult for the case studied within this paper thanlearning non-erasing ones. For the general case of arbitrary pattern languages,
already Angluin [2] showed the non-erasing pattern languages to be learnablefrom positive data. However, Reidenbach [22] proved that even the terminalfree erasing pattern languages are not learnable from positive data if |Σ| = 2.
Reidenbach [23,24] extended his results: The terminal-free erasing patternlanguages are learnable from positive data if |Σ| ≥ 3; general erasing patternlanguages are not learnable for alphabet sizes 3 and 4.
Definition 3 (Shinohara[32]) A pattern π is said to be regular if it is of
the form x0 α1 x1 α2 x2 . . . αm xm , where αi ∈ Σ∗ and xi is the i-th variable. We
set REGPAT = {Lang(π) | π is a regular pattern}.
Definition 4 Suppose c ∈ N+ . We define{π | π = x0 α1 x1 α2 x2 . . . αm xm , where each αi ∈ Σc }.
(a) regm
c =S(b) regc = m regmc .
(c) REGPATc = {Lang(π) | π ∈ regc }.
Next, we define the learning model considered in this paper. As already explained in the introduction, our model differs to a certain extent from the
PAC model introduced by Valiant [38] which is distribution independent. In
our model, the learner has a bit of background knowledge concerning the classof allowed probability distributions. So, we have a stronger assumption, butalso a stronger requirement, that is, instead of learning an approximation for
the target concept, our learner is required to learn it exactly. Moreover, theclass of erasing regular pattern languages is known not to be PAC learnable,see [19] and the discussion within the introduction.
Definition 5 Let #, # ∈/ Σ, denote a pause-symbol and D ⊆ Σ∗ ∪{#}. Givena polynomial pol, a probability distribution prob on D is called pol-regular if(a) prob(σ) ∗ |Σ||σ| ≥ 1/pol(|σ|) for all σ ∈ D \ {#} and(b) prob(σ) ∗ |Σ||σ| ≤ prob(τ ) ∗ |Σ||τ | for all σ, τ ∈ D \ {#} with |σ| ≥ |τ |.
Note that a distribution prob on D generates only elements from D. The
second item in the definition of the pol-regular probability distribution enforcesthat in D strings of the same length have the same probability, besides the
distribution being nonincreasing in length of the data.
Next, we define the different sources of information for the learners consideredin this paper.
7

Definition 6 Let L ⊆ Σ∗ be a language.
(a) A probabilistic text for L with parameter pol is an infinite sequencedrawn with respect to any pol-regular distribution prob on the domain
D = L ∪ {#}.
(b) If L 6= ∅ then a probabilistic pause-free text for L with parameter pol is a
probabilistic text for L with parameter pol with respect to any pol-regular
distribution prob on the domain D = L.
(c) A probabilistic informant for L with parameter pol is an infinite sequenceof pairs (σ, L(σ)) where σ is drawn according to a pol-regular distribution
prob on D = Σ∗ , L(σ) is 1 for σ ∈ L and L(σ) is 0 for σ ∈/ L.
In the following, we shall frequently omit the words “probabilistic” and “withparameter pol” when referring to these types of text, pause-free text andinformant, since it is clear from the context what is meant.
Definition 7 A learner M is said to probabilistically exactly learn a class
L of pattern languages if for every increasing {2, 3, . . .}-valued polynomial pol
with
∞
X
1
≤1
n=0 pol(n)there is a polynomial q such that for all δ and every language L ∈ L, withprobability at least 1 − δ, M halts and outputs a pattern generating L after
reading at most q(|π|, 1δ ) examples from a probabilistic text for L with parameter pol. That is, for all δ and every pattern π generating a language L ∈ L andfor every pol-regular distribution prob on L ∪ {#}, with probability 1 − δ, M
draws at most q(|π|, 1δ ) examples according to prob and then outputs a pattern
π such that L = Lang(π).
It should be noted that learning from pause-free text can be much easier thanlearning from text. For example, the class of all singletons {σ} with σ ∈ Σ∗is learnable from pause-free text: the learner conjectures {σ} for the firstexample σ in the text and is correct. But it is not learnable from informant
since for each length n, the strings σ ∈ Σn satisfy that prob(σ) ≤ |Σ|−n andthe learner sees with high probability exponentially many negative examples of
low information content before (σ, 1) comes up. Furthermore, every informant
can be translated into a text as follows: one replaces (σ, 1) by σ and (σ, 0)
by #. Thus the class of all singletons is not probabilistically exactly learnablefrom text. So permitting pauses satisfies two goals: (a) there is a text for theempty set; (b) it is enforced that learnability from text implies learnability
from informant. The latter also holds in standard inductive inference.
Lange and Wiehagen [15,40] presented an algorithm which learns all nonerasing pattern languages by just analyzing all strings of shortest length generated by the target pattern. From these strings, the pattern can be reconstructed. Similarly, in the case of erasing pattern languages in REGPATc , the8

shortest string is just the concatenation of all terminals. Knowing c, one canreconstruct the whole pattern from this string. But this algorithm does not
succeed for learning REGPATc , even if one is learning from pause-free texts.
The distributions probL given as|Σ|−|σ| /pol(|σ|)
for all σ ∈ L−|τ | /pol(|τ |)τ ∈L |Σ|probL (σ) = P

witness this fact where L ranges over REGPATc . Let m ∗ c be the number ofterminals in the pattern generating L. By Proposition 11 there is a polynomial f such that at least half of the words of length f (m) are in L. So thedenominator is at least 0.5/pol(f (m)). On the other hand, the numerator forthe shortest word in L is exactly |Σ|−m /pol(m). So the probability of this word
is at most 2 ∗ |Σ|−m ∗ pol(f (m))/pol(m) and goes down exponentially in m.

3

Main Result

In this section we show that REGPATc is probabilistically exactly learnable.
First we need some well-known facts which hold for arbitrary distributions,later we only consider pol-regular distributions. The following lemma is basedon Chernoff Bounds (see, for example, [11]). Here, we use e to denote the baseof the natural logarithm.
Lemma 8 Let X, Y ⊆ Σ∗ , let δ, ε ∈ (0, 1/2), and let prob(X) ≥ prob(Y ) + ε.
If one draws at least
2 − log δ
∗
ε2
log e
∗
many examples from Σ according to the probability distribution prob, thenwith probability at least 1 − δ, elements of X show up more frequently thanelements of Y .
log δ. More generally,
Note that the number ε22∗δ is an upper bound for ε22 ∗ −logethe following holds.

Lemma 9 One can define a function r: (0, 1/2) × (0, 1/2) × N −→ N suchthat r(ε, δ, k) is polynomial in k, 1ε , 1δ and for all sets X, Z, Y1 , Y2 , . . . , Yk ⊆ Σ∗ ,the following holds.
If prob(X) − prob(Yi ) ≥ ε, for i = 1, 2, . . . , k, prob(Z) ≥ ε and one draws at
least r(ε, δ, k) many examples from Σ∗ according to the distribution prob, thenwith probability at least 1 − δ(a) there is at least one example from Z;(b) there are strictly more examples in X than in any of the sets Y1 , ..., Yk .

9

Since any regular pattern π has a variable at the end, the following lemma
holds.
Lemma 10 For every regular pattern π and all k ∈ N, |Lang(π) ∩ Σk+1 | ≥|Σ| ∗ |Lang(π) ∩ Σk |.
Proposition 11 For every fixed constant c ∈ N+ and every finite alphabet Σ,|Σ| ≥ 2, there is a polynomial f such that for every π ∈ regm
c , at least half ofthe strings of length f (m) are generated by π.
Proof. Suppose that π = x0 α1 x1 α2 x2 . . . αm xm and α1 , α2 , ..., αm ∈ Σc .
Let d be the least number with (1 − |Σ|−c )d ≤ 21 and consider any τ ∈ Σc .
Thus, a random string of length d ∗ c has τ as substring with probability atleast 1/2, as c successive symbols are equal to τ with probability at least |Σ|−c .
Thus, at least half of the strings in Σd∗c contain τ as a substring, that is, areSkd∗c−k−cin the set d∗c−c.
k=0 Σ τ Σ
Now let f (m) = d ∗ c ∗ m2 . We show that given π as above, at least half of thestrings of length f (m) are generated by π.
2

In order to see this, draw a string σ ∈ Σd∗c∗m according to a fair |Σ|-sided
coin such that all symbols are equally likely. Divide σ into m equal parts oflength d ∗ c ∗ m. The i-th part contains αi with probability at least 1 − 2−m asa substring. Thus by using Bernoulli’s inequality, we see that the whole stringis generated by pattern π with probability at least 1 − m ∗ 2−m . Note that
1 − m ∗ 2−m ≥ 1/2 for all m and thus f (m) meets the specification.
Lemma 12 Consider any pattern π = x0 α1 x1 α2 x2 ...αm xm ∈ regmc and X0 ={λ}. For i ∈ {1, . . . , m} and every h ∈ N, let• πi−1 = x0 α1 x1 ...αi−1 xi−1 ,• Xi be the set of all strings σ such that σ but no proper prefix of σ belongsto Σ∗ α1 Σ∗ . . . Σ∗ αi ,• Yi,β = Xi−1 βΣ∗ ,• C(i, β, h) be the cardinality of Yi,β ∩ Lang(π) ∩ Σh .
Then for h > 0, i ∈ {1, . . . , m} and β ∈ Σc \{αi }, C(i, β, h) ≤ |Σ|∗C(i, αi , h−1) ≤ C(i, αi , h).
Proof. Let σ ∈ Yi,β ∩ Lang(π). Note that σ has a unique prefix σi ∈ Xi−1 .
Furthermore, there exist s ∈ Σ, η, τ ∈ Σ∗ such that(I) σ = σi βsητ and(II) βsη is the shortest possible string such that βsη ∈ Σ∗ αi .
The existence of s is due to the fact that β 6= αi and |β| = |αi | = c. So theposition of αi in σ must be at least one symbol behind the one of β. If thedifference is more than a symbol, η is used to take these additional symbols.
10Now consider the mapping t: Lang(π) ∩ Yi,β −→ Lang(π) ∩ Yi,αi replacing βs
in the above representation (I) of σ by αi – thus t(σ) = σi αi ητ . The mappingt is |Σ|-to-1 since it replaces the terminal string β by αi and erases s (theinformation is lost about which element from Σ the value s is).
Clearly, σi but no proper prefix of σi is in Xi−1 . So σi αi is in Xi−1 αi . The position of αi+1 , . . . , αm in σ are in the part covered by τ , since σi βsη is the shortest
prefix of σ generated by πi−1 αi . Since πi−1 generates σi and xi αi+1 xi+1 ...αm xm
generates ητ , it follows that π generates t(σ). Hence, t(σ) ∈ Lang(π). Furthermore, t(σ) ∈ Σh−1 since the mapping t omits one element. Also, clearlyt(σ) ∈ Xi−1 αi Σ∗ = Yi,αi . Therefore, C(i, β, h) ≤ |Σ| ∗ C(i, αi , h − 1) forβ ∈ Σc \ {αi }. By combining with Lemma 10, C(i, αi , h) ≥ |Σ| ∗ C(i, αi , h − 1)
≥ C(i, β, h).
Lemma 13 Let i ∈ {1, . . . , m} and consider all variables as in statement ofLemma 12. There is a length h ≤ f (m) such that
C(i, αi , h) ≥ C(i, β, h) +|Σ|h2 ∗ |Σ|c ∗ f (m)for all β ∈ Σc \ {αi }. In particular, for every pol-regular distribution withdomain Lang(π) or domain Lang(π) ∪ {#},
prob(Yi,β ) +1
2 ∗ |Σ|c ∗ pol(f (m)) ∗ f (m)≤ prob(Yi,αi ).

, for all h and β ∈ Σc . Lemma 12 implies that
Proof. Let D(i, β, h) = C(i,β,h)|Σ|hD(i, β, h) ≤ D(i, αi , h − 1) ≤ D(i, αi , h) .
Since every string in Lang(π) is in some set Yi,β , using Proposition 11, weconclude that
1
D(i, αi , f (m)) ≥.
2 ∗ |Σ|c
Furthermore, D(i, αi , h) = 0 for all h < c, since m > 0 and π does not generate
the empty string. Thus, since D(i, αi , h) is monotonically increasing in h, there
is an h ∈ {1, 2, ..., f (m)} with
D(i, αi , h) − D(i, αi , h − 1) ≥1.
2 ∗ |Σ|c ∗ f (m)For this h, it holds that
D(i, αi , h) ≥ D(i, β, h) +111
2 ∗ |Σ|c ∗ f (m).

The second part of the claim follows by taking into account that h ≤ f (m)implies pol(h) ≤ pol(f (m)), since pol is monotonically increasing. Thus,prob(σ) ≥

|Σ|−h
|Σ|−h
≥
pol(h)
pol(f (m))

for all σ ∈ Σh ∩ Lang(π).
The previous two lemmas motivate the algorithm LRP 5 below for learning
REGPATc . Essentially, the above lemmas allow us to choose appropriate αi ateach stage by looking at the most frequent β which appears right after πi−1 .
The algorithm has prior knowledge about the function r from Lemma 9 andthe function f from Proposition 11. It takes as input c, δ and knowledge about
the probability distribution by getting pol.
Algorithm LRP: The learner has parameters (Σ, c, δ, pol) and works as follows. The variables A, A0 , A1 , . . . range over multisets.
(1) Read examples until an n is found such that the shortest non-pause example is strictly shorter than c ∗ n and the total number of examples(including repetitions and pause-symbols) is at leastδ1, , |Σ|cn∗rc2 ∗ |Σ| ∗ f (n) ∗ pol(f (n)) n!

.

Let A be the multiset of all positive examples (including pause-symbols)and Aj (j ∈ {1, 2, . . . , n}) be the multiset of examples in A whose index
is j modulo n; so the (k ∗ n + j)-th example from A goes to Aj where kis an integer and j ∈ {1, 2, ..., n}.
Let i = 1, π0 = x0 , X0 = {λ} and go to Step (2).
(2) For β ∈ Σc , let Yi,β = Xi−1 βΣ∗ .
If some string in Xi−1 is also in the multiset A, then let m = i − 1 andgo to Step (3).
Choose αi as the lexicographically first β ∈ Σc , such that the strings
from Yi,β occur in Ai at least as often as the strings from Yi,β 0 for any
β 0 ∈ Σc \ {β}.
Let Xi be the set of all strings σ such that σ is in Σ∗ α1 Σ∗ α2 Σ∗ . . . Σ∗ αi ,but no proper prefix τ of σ is in Σ∗ α1 Σ∗ α2 Σ∗ . . . Σ∗ αi .
Let πi = πi−1 αi xi , let i = i + 1 and go to Step (2).
(3) Output the pattern πm = x0 α1 x1 α2 x2 . . . αm xm and halt.
5

LRP stands for Learner for Regular Patterns.

12

End
Note that since the shortest example is strictly shorter than c ∗ n it holds thatn ≥ 1. Furthermore, if π = x0 , then the probability that a string drawn is λ
is at least 1/pol(0). A lower bound for this is 1/(2 ∗ |Σ|c ∗ f (n) ∗ pol(f (n))),whatever n is, due to the fact that pol is monotonically increasing. Thus λappears with probability 1 − δ/n in the set An and thus in the set A. So thealgorithm is correct for the case that π = x0 .
It remains to consider the case where π is of the form x0 α1 x1 α2 x2 . . . am xm forsome m ≥ 1 where all αi are in Σc .
Theorem 14 Let c ∈ N+ and let Σ be any finite alphabet with |Σ| ≥ 2.
Algorithm LRP probabilistically exactly learns the class of all Lang(π) withπ ∈ regc from text, from pause-free text and from informant.
Proof. Since an informant can be translated into a text, the result is only
shown for learning from text. The proof also covers the case of learning frompause-free text, it is almost identical for both versions. Let prob be a polregular distribution on Lang(π) or Lang(π) ∪ {#}.
, the
A loop invariant (in Step (2)) is that with probability at least 1 − δ∗(i−1)
npattern πi−1 is a prefix of the desired pattern π. This certainly holds before
entering Step (2) for the first time.
Case 1. i ∈ {1, 2, ..., m}.
By assumption, i ≤ m and πi−1 is with probability 1 − δ∗(i−1)
a prefix of π,nthat is, α1 , ..., αi−1 are selected correctly.
Since αi exists and every string generated by π is in Xi−1 Σ∗ αi Σ∗ , no elementof Lang(π) and thus no element of A is in Xi−1 and the algorithm does notstop too early.
If β = αi and β 0 6= αi , thenprob(Yi,β ∩ Lang(π)) ≥prob(Yi,β 0 ∩ Lang(π)) +1
2 ∗ |Σ|c ∗ f (m) ∗ pol(f (m))

by Lemma 13. By Lemma 9, αi is identified correctly with probability atleast 1 − δ/n from the data in Ai . It follows that the body of the loop in
Step (2) is executed correctly with probability at least 1 − δ/n and theloop-invariant is preserved.
Case 2. i = m + 1.
By Step (1) of the algorithm, the shortest example is strictly shorter thanc ∗ n and at least c ∗ m by construction. Thus, we already know m < n.
13With probability 1− δ∗(n−1)
the previous loops in Step (2) have gone throughnsuccessfully and πm = π. Consider the mapping t which omits from every
string the last symbol. Now, σ ∈ Xm iff σ ∈ Lang(π) and t(σ) ∈/ Lang(π).
Let D(π, h) be the weighted number of strings of length h generated by π,h. Since D(π, f (m)) ≥ 12 and D(π, 0) = 0, therethat is, D(π, h) = |Σ ∩Lang(π)||Σ|his an h ∈ {1, 2, . . . , f (m)} such that
D(π, h) − D(π, h − 1) ≥1
1≥.
2 ∗ f (m)2 ∗ |Σ|c ∗ f (n)Note that h ≤ f (n) since f is increasing. It follows thatprob(Xm ) ≥1
2 ∗ |Σ|c ∗ (f (n) ∗ pol(f (n)))

and thus, by Lemma 9, with probability at least 1 − nδ a string from Xm
is in Am and in particular in A. Therefore, the algorithm terminates after
going through Step (2) m times with the correct output with probability atleast 1 − δ.
To get a polynomial time bound for the learner, note the following. It iseasy to show that there is a polynomial q(m, δ10 ) which with sufficiently highprobability (1−δ 0 , for any fixed δ 0 ) bounds the parameter n of algorithm LRP.
Thus, with probability at least 1 − δ 0 − δ algorithm LRP is successful in timeand example-number polynomial in m, 1/δ, 1/δ 0 . Hence, for any given δ 00 , bychoosing δ 0 = δ = δ 00 /2, one can get the desired polynomial time algorithm.
If one permits the pattern to start or end with some terminal parts and theseparts are not too long, then one can learn also this derived class by reading polynomially more data-items and skipping off the common prefixes andsuffixes of all data. Consequently, we have the following result.
Theorem 15 Let c ∈ N+ and let Σ be any finite alphabet with |Σ| ≥ 2.
Then, the class {αLang(π)β | α, β ∈ Σ∗ , |α| ≤ d, |β| ≤ d, π ∈ regc } isprobabilistically exactly learnable from text where the polynomial bound for thenumber of examples has the parameters pol and c, d.

4Experimental Results

Looking at the results proved so far, we see that the theoretical bounds arevery large. Therefore, we are interested in finding possible improvements.
First, we fix the polynomial pol. Linear functions cannot be used, since the sumof their reciprocals diverges, thus pol is taken to be quadratic. More precisely,14

pol is taken such that, for all n ∈ N,
pol(n) = (n + 1) ∗ (n + 2) and

∞
X
1
1
=
.
n + 1 m=n pol(m)Second, we study the special case that Σ = {0, 1} and REGPAT1 is being
learned. For this particular setting, we improve the theoretical bounds, see
Theorem 16 below.
Then, we provide some evidence, that even these bounds are not optimal,
since experiments run for small alphabets Σ and small values of m, c give
much better results. These experiments use Algorithm HLRP 6 which does
not compute the number of examples in advance but monitors its intermediate
results and halts if a hypothesis looks sufficiently reasonable with respect tothe data seen so far. More details will be given below.
Theorem 16 For Σ = {0, 1} and considering only (n + 1)(n + 2)-regular
distributions, Algorithm LRP can be adapted such that it probabilistically exactly learns REGPAT1 . For every L ∈ REGPATm
1 and confidence 1 − δ, forall δ ∈ (0, 1/2), it needs at most8 ∗ (4m − 1)2 ∗ (4m + 1)2 ∗ (4m + 2)2 ∗ (2m + 2) ∗log(2m + 2) − log δ
log epositive examples including pauses.
Proof. We can improve the bounds on the number of examples needed byusing Lemma 8 instead of Lemma 9. We need enough examples to guaranteeδthe following three conditions:with probability 1 − m+2• A data-item of length 2m or less is drawn in Step (1);• For i = 1, 2, . . . , m, the right αi ∈ {0, 1} is selected in Step (2);• For i = m + 1 a data-item in A ∩ Xi−1 is found.
For the first condition, one has to draw an example of length 2m which is
generated by the pattern. The number of strings of length 2m generated by π
is equal to the number of binary strings of the same length containing at least
m 0s. This is at least half of the strings of length 2m. Thus, the probability
that a randomly drawn datum has length 2m and is generated by π is at least1.
2(2m+1)(2m+2)
For the second condition, the bound in Lemma 13 can be improved by considering h = 2m. For this purpose, let us consider the following three regularexpressions, where the third one gives the difference between the choice ofcorrect versus incorrect ai .
• (1−a1 )∗ a1 . . . (1−ai−1 )∗ ai−1 0{0, 1}∗ ai (1−ai )∗ ai+1 (1−ai+1 )∗ . . . am (1−am )∗ ;6

HLRP stands for Heuristic Learner for Regular Patterns.

15• (1−a1 )∗ a1 . . . (1−ai−1 )∗ ai−1 1{0, 1}∗ ai (1−ai )∗ ai+1 (1−ai+1 )∗ . . . am (1−am )∗ ;• (1 − a1 )∗ a1 . . . (1 − ai−1 )∗ ai−1 ai (1 − ai )∗ ai+1 (1 − ai+1 )∗ . . . am (1 − am )∗ .
The number of strings of length 2m generated by the first and generated by thesecond expression is the same. But the one generated by the third expression
is exactly as large as the number of strings of length 2m − 1 which consist of1
22m−1 . Sincem zeros and m − 1 ones. This number has the lower bound 2m−1
1
, one can conclude
the strings of length 2m have the probability (2m+1)(2m+2)that the value ai is favored over the value 1 − ai with probability at least
ε=

22m−1
1
1
∗
=
.
2m
(2m − 1)(2 ) (2m + 1)(2m + 2)2(2m − 1)(2m + 1)(2m + 2)

For the last condition to enforce leaving the loop, one has the same probability ε. One just obtains this value by setting i = m + 1 in the above regularexpressions where of course then the part ai (1 − ai )∗ . . . am (1 − am )∗ has tobe omitted from the expression. Furthermore, ε is a lower bound for the firstprobability.
δ
examples.
Using Lemma 8, it suffices to draw (m + 2) ∗ 2 ∗ ε−2 ∗ log(m+2)−log
log eNote that the algorithm uses the parameter n as a bound for m, that is,n = 2m.
So with probability at least 1 − δ, the algorithm uses at most the following
quantity of data:
8 ∗ (2n − 1)2 ∗ (2n + 1)2 ∗ (2n + 2)2 ∗ (n + 2) ∗log(n + 2) − log δ.
log e

The entry “upper bound” in Figure 1 has the specific values obtained form = 2, 3, . . . , 20 and δ = 1/3.
We have tried to find further improvements of these bounds. These improvements have no longer been verified theoretically, but only be looked up experimentally. For that, we applied the following experimental setting.
Experimental Setting 1 The heuristic used is Algorithm HLRP which ignores pause-symbols. This algorithm reads data and tries in parallel to findthe pattern. It stops reading data when the process has given a pattern with
sufficiently high estimated confidence.
Learning L, the experiments were run for the following two distributions which
are the extreme (n + 1)(n + 2)-regular distributions with respect to having as
many pauses as possible and no pauses at all where σ ∈ L:

probL,# (σ) =|Σ|−|σ|;(|σ| + 1) ∗ (|σ| + 2)
16

probL,# (#) = 1 −X

probL,# (τ );τ ∈LprobL (σ) =probL,# (σ).
1 − probL,# (#)

The probabilities can be obtained from probΣ∗ ,# as follows: In the case ofprobL,# , one draws an example string σ and then provides σ to the learnerin the case that σ ∈ L and provides # to the learner otherwise. In the caseof probL , one draws examples according to probΣ∗ ,# until an example in L isfound which one then provides to the learner.
Since Algorithm HLRP ignores pause-symbols, the experiments were run with
examples drawn according to probL,# . While the algorithm runs, one can countthe number a of non-pause examples drawn and the number b of pauses drawn.
The example complexities with respect to probL and probL,# are a and a + b,
respectively. So the experiments cover both cases at once where only the way
to count the number of drawn examples are different for probL and probL,# .
The two main modifications in Algorithm HLRP to the theoretical model are
the following: The algorithm alternately draws a data item and tries to learn
from the data seen so far until it thinks that the result of the learning-trial givesa sufficiently reasonable hypothesis. Furthermore, only sufficiently short dataitems are considered. The constant 1.4 below was determined experimentallyto be a good one, see further discussion after the algorithm.
Algorithm HLRP (for learning regular patterns):
RepeatInitialize bound by a default constant, g a function determined below and let
A be the empty multiset.
RepeatDraw example σ;
Put σ into A if
• σ is not the pause symbol;• |σ| ≤ bound;• |σ| ≤ 1.4 ∗ |τ | for all τ already in A;
Until Either there are m and ρ = x0 a1 x1 a2 x2 . . . am xm such that• ρ generates all data in A;• for all i ∈ {1, . . . , m} and b ∈ Σ \ {ai }, the number of data-items in A
generated by the regular expression(Σ \ {a1 })∗ a1 . . . (Σ \ {ai−1 })∗ ai−1 ai Σ∗
17minus the number of the data-items in A generated by(Σ \ {a1 })∗ a1 . . . (Σ \ {ai−1 })∗ ai−1 bΣ∗is at least g(m);• the number of data-items in A generated by the regular expression(Σ \ {a1 })∗ a1 . . . (Σ \ {am })∗ am
is at least g(m).
Or default bounds on memory usage and number of examples are exceeded.
Until The previous loop ended in the “either-case” or has been run for ten
times.
If no such pattern ρ has been found Then Halt with error message
Else consider this unique ρ.
If |Σ| ≥ 3 Then For k = 1 to m − 1 Remove the variable xk from the patternwhenever it can be removed without becoming inconsistent with the datastored in A.
(ITF)
Output the resulting pattern ρ and Halt.
End
Note that in the second condition on ρ, the regular expressions for i = 1 area1 Σ∗ and bΣ∗ ; for i = 2 the corresponding expressions are (Σ \ {a1 })∗ a1 a2 Σ∗and (Σ \ {a1 })∗ a1 bΣ∗ .
The For-Loop labeled (ITF) removes variables not needed to generate thedata. It is included for the case considered later where the above algorithm
is adapted to learn regular patterns outside REGPAT1 . Surprisingly, for all
experiments done with the alphabet {0, 1, 2}, there were no errors causedby removing superfluous variables in an otherwise correct pattern. Thus thisroutine was actually always activated when |Σ| ≥ 3, even when learning languages from REGPAT1 where this routine is superfluous. The routine is not
used for Σ = {0, 1} since there the patterns are not unique: Lang(x0 0x1 1x2 ) =Lang(x0 01x2 ).
Algorithm HLRP has been implemented such that at every learning trial it ispermitted to store up to 106 digits belonging to 50000 examples and draw up to
107 examples. The algorithm tries up to 10 times to learn a pattern without
violating the resource-bounds and then gives up. The parameter bound isinitialized to 2000 at each learning trial which is 0.2% of the available memory
to store the data-items in A and g(m) being the constant 10. The existenceof the pattern ρ can be checked effectively by constructing it inductively as in
Algorithm LRP.
18

m correct without pause

with pause% usedupper bound

10

1000

4064.909

81633.997

4.42

3 ∗ 1012

20

999

4184.943

167777.073

5.42447 ∗ 1012

30

993

4909.675

294712.912

7.377999 ∗ 1012

40

970

6439.009

515298.445

9.05

62110 ∗ 1012

50

967

8895.355

889807.785

9.79304901 ∗ 1012

60

946

11980.308 1438119.953

10.53

1119325 ∗ 1012

70

933

15777.699 2209051.668

11.443361797 ∗ 1012

80

927

20792.314 3325566.018

12.038716312 ∗ 1012

90

917

27871.036 5017601.075

12.63 20197744 ∗ 1012

100

897

48742.807 9749833.913

13.24 42832613 ∗ 1012

Fig. 1. Learning REGPATm
1 where Σ = {0, 1}.

Figure 1 gives a table on the outcome of running Algorithm HLRP in order tolearn for each m ∈ {10, 20, 30, 40, 50, 60, 70, 80, 90, 100} exactly 1000 patterns
having m terminals. These patterns have been chosen according to the uniform
distribution over REGPATm
1 . The algorithm itself does not know m. The firstcolumn gives the number m of terminals of the pattern x0 a1 x1 a2 x2 . . . am xm tobe learned. For each m, 1000 patterns were randomly drawn with the parameters a1 , a2 , . . . , am being chosen according to the uniform distribution. The
second column gives how many of these pattern have been learned correctly
and the third and fourth column state the average number of examples needed.
The third column counts the examples drawn excluding the pause-symbols andthe fourth column counts the examples drawn including the pause-symbols.
That is, the third column refers to the distribution probL and the fourth column refers to the distribution probL,# discussed in the Experimental Setting 1.
The fifth column states the percentage of the examples from the third column
which were actually used by the algorithm and not skipped. The other examples were too long and not processed by the learner. The upper boundis the theoretically sufficient number of examples with respect to confidence
90
100
1 − δ = 2/3. Only trials for patterns in REGPAT80
1 , REGPAT1 , REGPAT1
were aborted and rerun, but each of these patterns was learned within the first
10 trials. So the incorrect learning processes are due to incorrect hypotheses
and not due to violating memory or example bounds in each of the 10 trials.
Algorithm HLRP does not use all data different from the pause-symbol but
only the sufficiently short ones. This can be justified as follows: The underlying
1
probability distribution produces with probability n+1
a string which has atleast the length n and the longer the string, the more likely it is in the language
to be learned. Thus if the length is very high, the data reveals almost nothing19

|Σ| correct repetitions

without pause

with pause% used2967

08895.355

889807.785

9.79

3

980

0

22604.453

3366611.336

4.60

4

993

8

44111.067

8735098.330

2.78

5

995

82

80512.278 19891099.233

1.90

Fig. 2. Learning REGPAT50
1 in dependence of the alphabet size.

about the language and might confuse the learner more by being random.
Skipping long examples has been justified experimentally: Algorithm HLRP
was correct on all 1000 random patterns when learning REGPAT10
1 for thealphabet {0, 1}. The algorithm was run for the same class with the factor
in the third condition for the selection of data, namely that |σ| ≤ 1.4 ∗ |τ |for all previously seen data τ , being relaxed to 1.6, 1.8 and 2.0. The numberof correct patterns was 998, 998 and 994 respectively. Larger factors giveeven worse results. Relaxing the third condition and permitting longer strings
reduces the confidence of the algorithm.
The parameter bound itself should not be there if sufficient resources are available since it makes it definitely impossible to learn patterns having more thanbound terminals. But if one has a memory limit of length `, then, on average,
every `-th learning experiment has a first example of length ` or more. Therefore one cannot avoid having such a bound in an environment with a memory
limitation. The choice bound = `/500 looks a bit arbitrary, but this choice is
not severe for the learning problems investigated. For learning much longer
patterns, one would of course have to revise this decision.
Choosing the parameter g(m) = 10 is debatable. If one wants to learn large
patterns with sufficient high confidence, then g has to be a growing function.
Otherwise, as indicated by the experimental data, the confidence goes down forlarge m. More precisely, the larger the parameter m, the less likely the learner
succeeds to learn any given pattern from REGPATm
c . Repairing this by having
larger values for g(m) has the obvious disadvantage that Algorithm HLRP
draws more examples in the learning process. That is, learning is slowed down
by increasing g(m).
Figure 2 shows the result for learning patterns having 50 terminals in dependence of the alphabet size. The larger the alphabet, the more restrictive is thelength bound on the choice of data considered. So, on one hand the number ofincorrect hypotheses went down from 33 to 5. On the other hand, the amountof data needed goes up. Furthermore, for alphabets of size 4 and 5, some repetitions on the inner repeat loop take place and the learning algorithm is rerunon the same pattern. For the alphabet {0, 1, 2, 3, 4}, it was four times needed
to repeat the learning process twice.
20

|Σ|

c

m∗c

correct rptts. without pause

with pause% used

2 1

12

1000

0

5130.285

123529.904

3.58

2 2

12

920

9

23256.913

738004.683

1.08

2 3

12

890

17

37152.843

1542162.670

0.71

3 1

12

1000

15

98571.932

3460717.043

0.36

3 2

12

957

159

268867.961

14615063.504

0.11

3 3

12

922

1034

611210.432

58396686.666

0.06

4 1

12

1000

294

436565.410

20142491.835

0.12

4 2

12

711

3677

1905036.705 171744393.587

0.04

4 3

12

23

8922

1924946.265 396696831.533

0.03

6
4
Fig. 3. Learning REGPAT12
1 , REGPAT2 and REGPAT3 .

An attempt was made to adapt the algorithm for c = 2, 3 and to run it
for larger alphabet sizes. Since the provenly correct algorithm needs a large
quantity of data exceeding any practical bound, the heuristic approach already implemented in Algorithm HLRP was chosen: One uses the learner for
REGPAT1 in order to figure out the terminals in the pattern. For the alphabet {0, 1}, one then interprets this sequence of terminals as being the one for
REGPATc where c = 2, 3. For the alphabets {0, 1, 2} and {0, 1, 2, 3}, the last
three lines of Algorithm HLRP were run and taken into account at the checkfor correctness.
Figure 3 gives a summary of these results obtained from the following experiments: For each of the alphabets {0, 1}, {0, 1, 2}, {0, 1, 2, 3} and each c ∈{1, 2, 3}, 1000 patterns containing 12 terminals were tried to learn where theterminals a1 , a2 , . . . , a12 were chosen independently from the alphabet under
the uniform distribution. Since the distributions of the correct data for patterns from REGPAT1 and REGPATc with c > 1 are not the same, the performance of the algorithm goes down and the patterns to be learned in the data
for Figure 3 had always 12 terminal symbols. It turned out that the data forthe experiments in Figure 3 are much more sensitive to the alphabet size thanthose for the experiments in Figure 2. Algorithm HLRP had its best performance for the alphabet {0, 1, 2}. For the alphabet {0, 1}, the main problem
was errors due to figuring out the sequence of terminals incorrectly.
For the alphabet {0, 1, 2, 3}, the main problem are too excessive usage ofmemory and time, so that many trials were aborted or rerun. For only 23 outof the 1000 languages from REGPAT43 , Algorithm HLRP terminated in anyof the ten trials. But in that case, it always gave the correct pattern. Notethat for REGPAT43 , the average number of examples drawn heavily depends
21

on the choice of parameters: every trial reads at most 4 ∗ 107 examples (withpauses) and the overall number of examples drawn is at most 4 ∗ 108 since
there are at most 10 trials per pattern. The measured average complexity
is 3.96696831533 ∗ 108 , that is, it is only slightly below the maximal upperbound imposed by running-time constraints. Therefore, the main message ofthese entries in the table is just the following one: Learning REGPAT62 and
REGPAT43 for alphabet with four or more symbols is clearly beyond what thecurrent implementation is capable to handle; maybe that on a faster computerwith less severe running time constraints, Algorithm HLRP has a similar
performance for the alphabet {0, 1, 2, 3} as the current implementation has
for the alphabet {0, 1, 2}. The next experiments deal with the case where not
only the terminals but also the exact form of the pattern is selected randomly.
Based on the reasons just outlined, the alphabet {0, 1, 2} was chosen for theseexperiments.
Experimental Setting 2 Figure 4 shows experiments to learn patterns over
the alphabet {0, 1, 2} where the pattern π is chosen by iteratively executing
always the first of the following cases which applies.
• When generating the first symbol of π, this is taken to be a variable.
• If the currently generated part of π contains less than m terminals and ends
with a variable, then the next symbol is a terminal where each digit has theprobability 1/3.
• If the currently generated part of π contains less than m terminals andends with one, two or three terminals following the last variable, then, withprobability 1/2, one adds a further variable and with probability 1/6 the digit
a for a = 0, 1, 2.
• If the currently generated part of π contains less than m terminals and its
last four symbols are all terminals then one adds a variable.
• If the currently generated part contains m terminals, then one adds a variable at the end and terminates the procedure since the pattern is complete.
The first entry in the table of Figure 4 is the parameter m of the above procedure. For m = 5, 6, . . . , 15, this protocol was used to generate 1000 patterns
and run the learning algorithm on these pattern-languages.
The experiments shown in Figure 4 gave that for m ≤ 13 most errors were due
to conjecturing false terminals. Furthermore, for m = 12, 13, 14, 15, the number of learning processes which failed in all 10 trials to give a hypothesis, was
1, 12, 97, 109, respectively, compared to 16, 33, 66, 96 errors due to incorrectly
conjectured patterns.
Note that the probability to draw the smallest string generated by the patternis 3−15 ∗ 16−1 ∗ 17−1 = 1/3902902704 for m = 15. So the expected value for thenumber of examples to be drawn until one has seen this string is approximately
3902902704 which is by a factor of approximately 41.51 above the average
number 94019439.240 of examples drawn by the algorithm. This shows that22

m correct repetitions

without pause

with pause% used5

1000

013666.581

303467.013

2.95

6

1000

0

30471.300

854851.633

1.30

7

1000

0

69797.807

2504307.913

0.59

8

999

1

78186.534

3526912.510

0.47

9

997

13

134352.582

7190948.532

0.25

10

997

71

177112.452 11066283.854

0.19

11

992

244

259912.841 19128675.970

0.13

12

983

351

284064.711 24450019.647

0.11

13

955

568

365624.652 35745664.161

0.10

14

898

974

511091.000 54322939.087

0.09

15

795

1850

779662.091 94019439.240

0.08

Fig. 4. Learning regular patterns with Σ = {0, 1, 2} following Setting 2.

the current algorithm is better than the trivial heuristic to draw sufficiently
many examples such that the shortest example has shown up with sufficiently
high probability and then to run the part of Algorithm HLRP which figuresout the positions of the variables in the pattern.

5

Conclusion

In Theorem 14, it is shown that the class of c-regular pattern languages isprobabilistically exactly learnable from any text drawn from a probability
distribution prob satisfying
prob(σ) =∞X|Σ|−|σ|
1
where
= 1,
pol(|σ|)n=0 pol(n)pol is a {2, 3, . . .}-valued increasing polynomial and prob(#) is chosen accordingly. Actually, Algorithm LRP also works for distributions which are sufficiently near to the just mentioned ones and succeeds on texts as defined in
Definition 5. Proposition 15 extends the learning algorithm to the case where
patterns starting or ending with a constantly bounded number of terminals are
permitted. Algorithm HLRP is a heuristic based on Algorithm LRP, which
has been implemented to learn the class REGPAT1 . Its parameters have been
determined experimentally. This permits to learn the classes REGPATm
1 fasterfor small m but these improved bounds are not theoretically generalized for23

all m. Furthermore, only small alphabets Σ have been considered, all experiments were run for alphabets of sizes 2, 3, 4, 5 only. An interesting observationis that by skipping long examples, Algorithm HLRP has an experimentally
improved performance compared to the version where all non-pause examples
are taken into account. The intuitive reason is that long examples reflect lessabout the pattern to be learned and have more random components whichmight lead the learner to wrong conclusions. While Algorithm HLRP gavevery good results for REGPAT1 , its performance for REGPATc with c > 1
was not so convincing. The difficult part is to figure out the order of the terminals in the string of the pattern while, for alphabet size 3, 4, 5, it was easy
to figure out between which terminals is a variable and between which not. On
one hand, for alphabets having a finite size of 3 or more, future work should
more focus on improving the method determining the sequence of terminals
in a regular pattern than on determining the position of the variables. On
the other hand, this second part needs attention for the special case of thealphabet {0, 1} since there the solution is not unique.
Future research should also address the problem to determine the precise influence of the alphabet size to the difficulty of learning in the setting discussed
within this paper. Such an analysis has been performed for Lange and Wiehagen’s [15] algorithm. In this setting it could be shown that larger alphabets
reduce the minimal number of examples needed for learning (cf. citeZeu:j:98).

Acknowledgements
The authors would like to thank Phil Long for fruitful discussions. Moreover,
we are grateful to the anonymous referees for their careful reading and themany valuable comments made.

References[1] T. Amoth, P. Cull and P. Tadepalli. On exact learning of unordered tree
patterns. Machine Learning, 44(3), 211–243, 2001.
[2] D. Angluin. Finding patterns common to a set of strings. Journal of Computerand System Sciences, 21:46–62, 1980.
[3] S. Arikawa, T. Shinohara and A. Yamamoto. Learning elementary formal
systems. Theoretical Computer Science, 95:97–113, 1992.
[4] I. Bratko and S. Muggleton. Applications of inductive logic programming.
Communications of the ACM, 1995.

24

[5] A. Brāzma, E. Ukkonen and J. Vilo. Discovering unbounded unions ofregular pattern languages from positive examples. In Proceedings of the
7th International Symposium on Algorithms and Computation (ISAAC 1996),
volume 1178 of Lecture Notes in Computer Science, pages 95–104, Springer,
1996.
[6] J. Case, S. Jain, S. Kaufmann, A. Sharma and F. Stephan. Predictive learningmodels for concept drift. Theoretical Computer Science, 268:323–349, 2001.
Special Issue for ALT 1998.
[7] J. Case, S. Jain, S. Lange and T. Zeugmann. Incremental concept learning forbounded data mining. Information and Computation, 152(1):74–110, 1999.
[8] 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. Theoretical Computer Science, 261(1):119-156, 2001.
[9] E.M. Gold. Language identification in the limit. Information and Control,
10:447–474, 1967.
[10] S. Goldman and S. Kwek. On learning unions of pattern languages andtree patterns in the mistake bound model. Theoretical Computer Science,
288(2):237–254, 2002.
[11] T. Hagerup and C. Rüb. A guided tour of Chernoff bounds. Information
Processing Letters, 33(10):305–308, 1990.
[12] H. Ishizaka, H. Arimura and T. Shinohara. Finding tree patterns consistent
with positive and negative examples using queries. Annals of Mathematics andArtificial Intelligence, 23(1–2):101–115, 1998.
[13] 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.), Proceedings of the Second Annual ACM Workshop on Computational
Learning Theory, pages 57–71, Morgan Kaufmann Publishers Inc., 1989.
[14] P. Kilpeläinen, H. Mannila and E. Ukkonen. MDL learning of unions of simple
pattern languages from positive examples. In Paul Vitányi, editor, Second
European Conference on Computational Learning Theory, volume 904 of Lecture
Notes in Artificial Intelligence, pages 252–260. Springer, 1995.
[15] S. Lange and R. Wiehagen. Polynomial time inference of arbitrary patternlanguages. New Generation Computing, 8:361–370, 1991.
[16] N. Lavrač and S. Džeroski. Inductive Logic Programming: Techniques andApplications. Ellis Horwood, 1994.
[17] S. Matsumoto and A. Shinohara. Learnability of subsequence languages.
Information Modeling and Knowledge Bases VIII, pages 335–344, IOS Press,
1997.
[18] T. Mitchell. Machine Learning. McGraw Hill, 1997.

25

[19] S. Miyano, A. Shinohara and T. Shinohara. Polynomial-time learning ofelementary formal systems. New Generation Computing, 18:217–242, 2000.
[20] S. Muggleton and L. De Raedt. Inductive logic programming: Theory andmethods. Journal of Logic Programming, 19/20:669–679, 1994.
[21] R. Nix. Editing by examples. Technical Report 280, Department of Computer
Science, Yale University, New Haven, CT, USA, 1983.
[22] D. Reidenbach. A negative result on inductive inference of extended patternlanguages. In N. Cesa-Bianchi and M. Numao, editors, Algorithmic Learning
Theory, 13th International Conference, ALT 2002, Lübeck, Germany, November
2002, Proceedings, volume 2533 of Lecture Notes in Artificial Intelligence, pages
308–320. Springer, 2002.
[23] D. Reidenbach. A discontinuity in pattern inference. In V. Diekert and
M. Habib, editors, STACS 2004, 21st Annual Symposium on Theoretical Aspectsof Computer Science, Montpellier, France, March 25-27, 2004, Proceedings.
volume 2996 of Lecture Notes in Computer Science, pages 129–140. Springer,
2004.
[24] D. Reidenbach. On the Learnability of E-pattern Languages over Small
Alphabets. In John Shawe-Taylor and Yoram Singer, editors, Proceeedings 17th
Conference on Learning Theory, COLT 2004, volume 3120 of Lecture Notes in
Artificial Intelligence, pages 140–154. Springer, 2004.
[25] R. Reischuk and T. Zeugmann. Learning one-variable pattern languages inlinear average time. In Proceedings of the Eleventh Annual Conference on
Computational Learning Theory, pages 198–208. ACM Press, 1998.
[26] R. Reischuk and T. Zeugmann. An average-case optimal one-variable patternlanguage learner. Journal of Computer and System Sciences 60(2):302-335,
2000.
[27] P. Rossmanith and T. Zeugmann. Stochastic finite learning of the patternlanguages. Machine Learning 44(1/2):67-91, 2001. Special Issue on Automata
Induction, Grammar Inference, and Language Acquisition[28] A. Salomaa. Patterns (The Formal Language Theory Column).
Bulletin, 54:46–62, 1994.

EATCS[29] A. Salomaa. Return to patterns (The Formal Language Theory Column).
EATCS Bulletin, 55:144–157, 1994.
[30] R. Schapire, Pattern languages are not learnable. In M.A. Fulk and J. Case,
editors, Proceedings, 3rd Annual ACM Workshop on Computational Learning
Theory, pages 122–129, Morgan Kaufmann Publishers, Inc., 1990.
[31] S. Shimozono, A. Shinohara, T. Shinohara, S. Miyano, S. Kuhara andS. Arikawa. Knowledge acquisition from amino acid sequences by machinelearning system BONSAI. Transactions of Information Processing Society ofJapan, 35:2009–2018, 1994.

26

[32] T. Shinohara. Polynomial time inference of extended regular pattern languages.
In RIMS Symposia on Software Science and Engineering, Kyoto, Japan, volume
147 of Lecture Notes in Computer Science, pages 115–127. Springer-Verlag,
1982.
[33] T. Shinohara. Inferring unions of two pattern languages. Bulletin of Informatics
and Cybernetics, 20:83–88, 1983.
[34] T. Shinohara and S. Arikawa. Learning data entry systems: An applicationof inductive inference of pattern languages. Research Report 102, ResearchInstitute of Fundamental Information Science, Kyushu University, 1983.
[35] T. Shinohara and S. Arikawa. Pattern inference. In K. P. Jantke and S. Lange,
editors, Algorithmic Learning for Knowledge-Based Systems, volume 961 of
Lecture Notes in Artificial Intelligence, pages 259–291. Springer, 1995.
[36] T. Shinohara and H. Arimura. Inductive inference of unbounded unions ofpattern languages from positive data. Theoretical Computer Science, 241:191–
209, 2000.
[37] R. Smullyan. Theory of Formal Systems, Annals of Mathematical Studies, No.
47. Princeton, NJ, 1961.
[38] L.G. Valiant. A theory of the learnable. Communications of the ACM 27:1134–
1142, 1984.
[39] K. Wright. Identification of unions of languages drawn from an identifiableclass. In R. Rivest, D. Haussler and M.K. Warmuth, editors, Proceedings of theSecond Annual Workshop on Computational Learning Theory, pages 328–333.
Morgan Kaufmann Publishers, Inc., 1989.
[40] T. Zeugmann. Lange and Wiehagen’s pattern language learning algorithm:
An average-case analysis with respect to its total learning time. Annals of
Mathematics and Artificial Intelligence, 23(1-2):117-145, 1998.

27