A Polynomial Time Learner for a Subclassof Regular Patterns
John Case∗
Department of Computer and Information Sciences
University of Delaware
Newark, DE 19716-2586, USA
case@cis.udel.edu

Sanjay Jain†

Rüdiger Reischuk

School of Computing

Institute for Theoretical Informatics

National University of Singapore

University at Lübeck

Singapore 117543

Ratzeburger Allee 160

sanjay@comp.nus.edu.sg

23538 Lübeck, Germany
reischuk@tcs.uni-luebeck.de

Frank Stephan‡

Thomas Zeugmann

National ICT Australia Ltd

Institute for Theoretical Informatics

Sydney Research Laboratory at Kensington

University at Lübeck

The University of New South Wales

Ratzeburger Allee 160

Sydney NSW 2052, Australia

23538 Lübeck, Germany

fstephan@cse.unsw.edu.au

thomas@tcs.uni-luebeck.de

Abstract
Presented is an algorithm (for learning a subclass of erasing regular pattern languages) which can be made to run with arbitrarily high probability ofsuccess on extended regular languages generated by patterns π of the formx0 α1 x1 ...αm xm for unknown m but known c , from number of examples polynomial in m (and exponential in c ), where x0 , . . . , xm are variables and where
α1 , ..., αm are each strings of terminals of length c . This assumes that the algorithm randomly draws samples with natural and plausible assumptions on
the distribution. With the aim of finding a better algorithm, we also explore
computer simulations of a heuristic.
∗

Supported in part by NSF grant number CCR-0208616 and USDA IFAFS grant number 01-04145
Supported in part by NUS grant number R252-000-127-112.
‡
National ICT Australia is funded by the Australian 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.
†

1

2

1

J. Case, S. Jain, R. Reischuk, F. Stephan and T. Zeugmann

Introduction

The pattern languages were formally introduced by Angluin [1]. A pattern languageis (by definition) one generated by all the positive length substitution instances in apattern, 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 patternlanguages which also allow empty substitutions as well as on various special cases of
the above, see, for example, [1, 5, 6, 7, 10, 12, 19, 21, 23, 24, 25, 28, 31] and thereferences therein. Furthermore, several authors have also studied finite unions ofpattern languages (or extended pattern languages), unbounded unions thereof andalso of important subclasses of (extended) pattern languages, see, for example, [4, 11,29, 32, 35].
Nix [18] as well as Shinohara and Arikawa [30, 31] outline interesting applicationsof pattern inference algorithms. For example, pattern language learning algorithms
have been successfully applied toward some problems in molecular biology, see [27, 31].
Pattern languages and finite unions of pattern languages turn out to be subclasses of
Smullyan’s [33] Elementary Formal Systems (EFSs), and Arikawa, Shinohara and Yamamoto [2] show that the EFSs can also be treated as a logic programming language
over strings. The investigations of the learnability of subclasses of EFSs are interesting
because they yield corresponding results about the learnability of subclasses of logic
programs. Hence, these results are also of relevance for Inductive Logic Programming (ILP) [3, 13, 15, 17]. Miyano et al. [16] intensively studied the polynomial-timelearnability of EFSs.
In the following we explain the main philosophy behind our research as well as theideas by which it emerged. As far as learning theory is concerned, pattern languages
are a prominent example of non-regular languages that can be learned in the limit frompositive data (cf. Angluin [1]). Gold [8] has introduced the corresponding learningmodel. Let L be any language; then a text for L is any infinite sequence of strings
containing eventually all members of L and nothing else. The information given
to the learner are successively growing initial segments of a text. Processing thesesegments, the learner has to output hypotheses about L . The hypotheses are chosenfrom a prespecified set called hypothesis space. The sequence of hypotheses has toconverge to a correct description of the target language.
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 theset 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 subsetof the language generated by π . But no efficient algorithm is known for computing
descriptive patterns. Thus, unless such an algorithm is found, it is even infeasible tocompute a single hypothesis in practice by using this approach.
Therefore, one has considered restricted versions of pattern language learning inwhich 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. Notethat this algorithm is also based on computing descriptive patterns even of maximum

A Polynomial Time Learner for a Subclass of Regular Patterns

3length. Giving up the idea to find descriptive patterns of maximum length but still
computing descriptive patterns, Erlebach et al. [7] arrived at a one variable patternlanguage learner having update time O(`2 log `) , where ` is as above. Moreover, theyalso studied the expected total learning time of a variant of their learner and showedan O(|π|2 log |π|) upper bound for it, where π is the target pattern. Subsequently,
Reischuk and Zeugmann [21] designed a one-variable pattern language learner achieving the optimal expected total learning time of O(|π|) for every target pattern π
and for almost all meaningful distributions. Note that the latter algorithm does notcompute descriptive patterns.
Another important special case extensively studied are the regular pattern languages introduced by Shinohara [28]. These are generated by the regular patterns,
i.e., patterns in which each variable that appears, appears only once. The learners
designed by Shinohara [28] for regular pattern languages and extended regular pattern languages are also computing descriptive patterns for the data seen so far. These
descriptive patterns are computable in time polynomial in the length of all examples
seen so far.
But when applying these algorithms in practice, another problem comes into play,i.e., all the learners mentioned above are only known to converge in the limit toa correct hypothesis for the target language. But the stage of convergence is notdecidable. Thus, a user never knows whether or not the learning process is alreadyfinished. Such an uncertainty may not be tolerable in practice.
Consequently, one has tried to learn the pattern languages within Valiant’s [34]
PAC model. Shapire [26] could show that the whole class of pattern languages is
not learnable within the PAC model unless P/poly = N P /poly for any 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 ofall pattern languages in an extended PAC model, i.e., a model in which one is allowed
to use the set of all patterns as hypothesis space.
However, Kearns and Pitt [10] have established a PAC learning algorithm for theclass of all k -variable pattern languages, i.e., languages generated by patterns in which
at most k different variables occur. Positive examples are generated with respect toarbitrary 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 have k 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 thelength on substitution strings, ε and δ are the usual error and confidence parameter,
respectively, and Σ is the alphabet of terminals over which the patterns are defined.
The overall learning time of their PAC learning algorithm is polynomial in the lengthof 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, their algorithm becomes rapidly impractical when k increases.
As far as the class of extended regular pattern languages is concerned, Miyano
et al. [16] showed the consistency problem to be N P -complete. Thus, the class 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.

4

J. Case, S. Jain, R. Reischuk, F. Stephan and T. Zeugmann

This is even true for REGPAT1 , i.e., 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 [16] via an equivalence proof to the common subsequence
languages studied in [14].
In the present paper we also study the special cases of learning the extended regularpattern languages. On the one hand, they already allow non-trivial applications. On
the other hand, it is by no means easy to design an efficient learner for these classesof languages as noted above. Therefore, we aim to design an efficient learner for aninteresting subclass of the extended regular pattern 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 c andx0 , 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 (cf. [21, 22, 23]).
We explain it here for the case mainly studied in this paper, learning from text
(in our above notation). One looks again at the whole learning process as learningin the limit. So, the data presented to the learner are growing initial segments of atext. But now, we do not allow arbitrary text. Instead every text is drawn according
to some fixed probability distribution. Next, one determines the expected number ofexamples needed by the learner until convergence. Let E denote this expectation.
Assuming prior knowledge about the underlying 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 bounded by 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 andthen it computes just one hypothesis from it. This hypothesis is output, and byconstruction we know it to be correct with probability at least 1 − δ . Thus, we arrive
at a learning model which we call probabilistically exact learning1 , cf. Definition 7
below. Clearly, in order to have an efficient learner, one also has to ensure that
this hypothesis can be computed in time polynomial in the length of all strings seen.
For arriving at an overall polynomial-time learner, it must be also ensured that E
is polynomially bounded in a suitable parameter. We use the number of variables
occurring in the regular target pattern, the maximal length of a terminal string in thepattern and a term describing knowledge about the probability distribution as such aparameter.
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,
1

This model has also been called stochastic finite learning (cf. [21, 22, 23]).

A Polynomial Time Learner for a Subclass of Regular Patterns

5also the condition∞X|Σ|−|σ|1
prob(σ) ≥for σ ∈ L where≤1.
pol(|σ|)pol(n)
n=0

Here, pol is a {2, 3,P. . .} -valued increasing polynomial and the pause-symbol # has
the probability 1 − σ∈L prob(σ) . This condition guarantees that long examples arestill 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 and informants
P where pause-free texts are those generated by probability distributions satisfyingσ∈L prob(σ) = 1 .
Our algorithm is presented in detail in Section 3 below and runs with all threemodels of data presentation in a uniform way. The complexity bounds are described
more exactly there, but, basically, the algorithm can be made to 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 but known c , from number of examples
polynomial in m (and exponential in c ), where α1 , ..., αm ∈ Σc . Here Σc denotes
the set of all strings over Σ of length 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 bylooking at the data and seeing if they have a common suffix or prefix. Our results moregenerally 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 is more for ease of presentation of proof.
While the main goal of the paper is to establish some polynomial bound for thelearning 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(#) is chosen accordingly. Although the bounds for this basic caseare much better than in the general case, it seems that the current implementationof the algorithm is even more efficient than the improved theoretical bounds suggest.
Experiments have also been run for alphabets of size 3, 4, 5 and the pattern languages
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 , i.e., (s, t) = {r | r is real 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,

6

J. Case, S. Jain, R. Reischuk, F. Stephan and T. Zeugmann

the elements of Σ are called terminals. By Σ∗ we denote the free monoid over Σ ,and we set Σ+ = Σ∗ \ {λ} , where λ is the empty string. As above, Σc denotes theset 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 overvariables. Following Angluin [1], 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.
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, i.e., a variable may
be substituted with the empty string λ . Though allowing empty substitutions may
seem a minor generalization, it is not. Learning erasing pattern languages is moredifficult for the case studied within this paper than learning non-erasing ones. For thegeneral case of arbitrary pattern languages, already Angluin [1] showed the non-erasing
pattern languages to be learnable from positive data. However, Reidenbach [19] provedthat even the terminal-free erasing pattern languages are not learnable from positive
data if |Σ| = 2 . On the other hand, the terminal-free erasing pattern languages arelearnable from positive data if |Σ| ≥ 3 (cf. Reidenbach [20]).
Definition 3 [Shinohara[28]]. A pattern π is said to be regular if it is of theform 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 definec(a) regmc = {π | π = x0 α1 x1 α2 x2 . . . αm xm , where each αi ∈ Σ } .
S(b) regc = m regmc .

(c) REGPATc = {Lang(π) | π ∈ regc } .
Next, we define the learning model considered in this paper. As already explainedin the Introduction, our model differs to a certain extent from the PAC model introduced by Valiant [34] which is distribution independent. In our model, a bit ofbackground knowledge concerning the class of allowed probability distributions is allowed. So, we have a stronger assumption, but also a stronger requirement, i.e.,
instead of learning an approximation for the target concept, our learner is required
to learn it exactly. Moreover, the class of erasing regular pattern languages is known
not to be PAC learnable, cf. [16] 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 |σ| ≥ |τ | .

A Polynomial Time Learner for a Subclass of Regular Patterns

7

Note that a distribution prob on D generates only elements from D . The second
item in the definition of the pol -regular probability distribution enforces that in D
strings of the same length have the same probability.
Next, we define the different sources of information for the learners considered inthis paper.
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 sequence of pairs (σ, L(σ)) where σ is drawn according to a pol -regular distribution prob on D = Σ∗ .
In the following, we shall frequently omit the words “probabilistic” and “withparameter pol ” when referring to these types of text, pause-free text and informant,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
pol(n)
n=0

there is a polynomial q such that for all δ and every language L ∈ L , with probability
at least 1 − δ , M halts and outputs a pattern generating L after reading at mostq(|π|, 1δ ) examples from a probabilistic text for L with parameter pol . That is, forall δ and every pattern π generating a language L ∈ L and for 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 σ ∈ Σ∗ islearnable from pause-free text: the learner conjectures {σ} for the first example σin the text and is correct. But it is not learnable from informant since for eachlength n , the strings σ ∈ Σn satisfy that prob(σ) ≤ |Σ|−n and the learner sees withhigh 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 learnable from text. So permitting pauses satisfies twogoals: (a) there is a text for the empty set; (b) it is enforced that learnability fromtext implies learnability from informant. The latter also holds in standard inductive
inference.
Lange and Wiehagen [12, 36] presented an algorithm which learns all non-erasing
pattern languages by just analyzing all strings of shortest length generated by the

8

J. Case, S. Jain, R. Reischuk, F. Stephan and T. Zeugmanntarget pattern. From these strings, the pattern can be reconstructed. Similarly, inthe case of erasing pattern languages in REGPATc , the shortest string is just the
concatenation of all terminals. Knowing c , one can reconstruct the whole patternfrom 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
probL (σ) =|Σ|−|σ| /pol(|σ|)
P
for all σ ∈ L
1 − τ ∈L |Σ|−|τ | /pol(|τ |)witness this fact where L ranges over REGPATc . Let m ∗ c be the number ofterminals in the pattern generating L . By Proposition 1 there is a polynomial fsuch that at least half of the words of length f (m) are in L . So the denominatoris at least 0.5/pol(f (m)) . On the other hand, the numerator for the shortest wordin L is exactly |Σ|−m /pol(m) . So the probability of this word is at most |Σ|−m ∗pol(f (m))/pol(m) and goes down exponentially in m .

3Main 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 based on Chernoff Bounds(cf., e.g., [9]). Here, we use e to denote the base of the natural logarithm.
Lemma 1. 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 , then withprobability at least 1 − δ , elements of X show up more frequently than elementsof Y .
log δ. More generally, theNote that the number ε22∗δ is an upper bound for ε22 ∗ −logefollowing holds.

Lemma 2. 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 ⊆ Σ∗ , thefollowing 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 , then withprobability 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 .
Since any regular pattern π has a variable at the end, the following lemma holds.
Lemma 3. For every regular pattern π and all m ∈ N , |Lang(π) ∩ Σm+1 | ≥|Σ| ∗ |Lang(π) ∩ Σm | .

A Polynomial Time Learner for a Subclass of Regular Patterns

9

Proposition 1. 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 of thestrings of length f (m) are generated by π .
Proof. Suppose that π = x0 α1 x1 α2 x2 . . . αm xm and α1 , α2 , ..., αm ∈ Σc .
c
Clearly, there is a length d ≥ c such that for every τ ∈ ΣS
, at least half of thed−c kdstrings in Σ contain τ as a substring, that is, are in the set k=0Σ τ Σd−k−c .

Now let f (m) = d ∗ m2 . We show that given π as above, at least half of thestrings of length f (m) are generated by π .
2In order to see this, draw a string σ ∈ Σd∗m according to a fair |Σ| -sided coinsuch that all symbols are equally likely. Divide σ into m equal parts of length d ∗ m .
The i -th part contains αi with probability at least 1 − 2−m as a substring. Thus
the whole string is generated by π 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.
Next we present our algorithm LRP 2 for learning REGPATc . The algorithm
has prior knowledge about the function r from Lemma 2 and the function f from
Proposition 1. 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


n
1
c
, , |Σ|.
n∗r
2 ∗ |Σ|c ∗ f (n) ∗ pol(f (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 k is an integer andj ∈ {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 and go 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.
End
2

LRP stands for Learner for Regular Patterns.

10

J. Case, S. Jain, R. Reischuk, F. Stephan and T. Zeugmann

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 atleast 1/pol(0) . A lower bound for this is 1/(2 ∗ |Σ|c ∗ f (n) ∗ pol(f (n))) , whatevern is, due to the fact that pol is monotonically increasing. Thus λ appears withprobability 1 − δ/n in the set An and thus in the set A . So the algorithm 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 .
Claim 1 Suppose any pattern π = x0 α1 x1 α2 x2 ...αm xm ∈ regmc . Furthermore, let
πi−1 = x0 α1 x1 ...αi−1 xi−1 . Let the sets Yi,β , Xi be defined as in the algorithm andlet C(i, β, h) be the cardinality of Yi,β ∩ Lang(π) ∩ Σh . Then we have C(i, β, h) ≤|Σ| ∗ C(i, αi , h − 1) ≤ C(i, αi , h) for all h > 0 and all β ∈ Σc \ {αi } .
Proof. Let σ ∈ Yi,β ∩ Lang(π) . Note that σ has a unique prefix σi ∈ Xi . 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 the positionof αi in σ must be at least one symbol behind the one of β . If the difference is morethan a symbol, η is used to take these additional symbols.
Now consider the mapping t: Lang(π) ∩ Yi,β −→ Lang(π) ∩ Yi,αi replacing βs inthe above representation (I) of σ by αi – thus t(σ) = σi αi ητ . The mapping t is
|Σ| -to- 1 since it replaces the terminal string β by αi and erases s (the information
is lost about which element from Σ the value s is).
Clearly, σi but no proper prefix of σi is in Xi . So σi αi is in Xi αi . The
position of αi+1 , . . . , αm in σ are in the part covered by τ , since σi βsη is theshortest prefix of σ generated by πi αi . Since πi 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, clearly t(σ) ∈ Xi αi Σ∗= Yi,αi . Therefore, C(i, β, h) ≤ |Σ| ∗ C(i, αi , h − 1) for β ∈ Σc \ {αi } . By combining
with Lemma 3, C(i, αi , h) ≥ |Σ| ∗ C(i, αi , h − 1) ≥ C(i, β, h) .
Claim 2 If m > i then 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 with domainLang(π) or domain Lang(π) ∪ {#} ,prob(Yi,β ) +1
2 ∗ |Σ|c ∗ pol(f (m)) ∗ f (m)≤ prob(Yi,αi ).

11A Polynomial Time Learner for a Subclass of Regular Patterns

Proof. Let D(i, β, h) = C(i,β,h), for all h and β ∈ Σc . Lemma 3 and Claim 1 imply
|Σ|h
that
D(i, β, h) ≤ D(i, αi , h − 1) ≤ D(i, αi , h) .
Since every string in Lang(π) is in some set Yi,β , we conclude that
D(i, αi , f (m)) ≥1.
2 ∗ |Σ|c

Furthermore, D(i, αi , h) = 0 for all h < c , since m > 0 and π does not generate
the empty string. Thus 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) +1
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(π) .
We now show that the learner presented above indeed probabilistically exactly
learns Lang(π) , for π ∈ regc .
Theorem 1. 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 forlearning from text. The proof also covers the case of learning from pause-free text,
it is almost identical for both versions. Let prob be a pol -regular distribution on
Lang(π) or Lang(π) ∪ {#} .
A loop invariant (in Step (2)) is that with probability at least 1 − δ∗(i−1), thenpattern π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 prefixnof π , that is, α1 , ..., αi−1 are selected correctly.
Since αi exists and every string generated by π is in Xi Σ∗ αi Σ∗ , no element of Lang(π) and thus no element of A is in Xi−1 and the algorithm
does not stop too early.

12

J. Case, S. Jain, R. Reischuk, F. Stephan and T. Zeugmann

If β = αi and β 0 6= αi , thenprob(Yi,β ∩ Lang(π)) ≥prob(Yi,β 0 ∩ Lang(π)) +1
2 ∗ |Σ|c ∗ f (m) ∗ pol(f (m))

by Claim 2. By Lemma 2, α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 .
the previous loops in Step (2) have goneWith probability 1 − δ∗(n−1)
nthrough successfully and πm = π . Consider the mapping t which omits
from every string the last symbol. Now, σ ∈ Xm iff σ ∈ Lang(π) andt(σ) ∈/ Lang(π) . Let D(π, h) be the weighted number of strings generatedh. Since D(π, f (m)) ≥ 12
by π of length h , that is, D(π, h) = |Σ ∩Lang(π)||Σ|hand D(π, 0) = 0 , there is an h ∈ {1, 2, . . . , f (m)} such that
D(π, h) − D(π, h − 1) ≥

1
1
≥
.
c
2 ∗ f (m)2 ∗ |Σ| ∗ 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 with probability at least 1− nδ a string from Xm is in Am and inparticular in A (by Lemma 2). Therefore, the algorithm terminates after
going through Step (2) m times with the correct output with probability
at least 1 − δ .
To get a polynomial time bound for the learner, note the following. It is easy
to show that there is a polynomial q(m, δ10 ) which with sufficiently high probability( 1 − δ 0 , for any fixed δ 0 ) bounds the parameter n of algorithm LRP. Thus, withprobability at least 1−δ 0 −δ algorithm LRP is successful in time and example-number
polynomial in m, 1/δ, 1/δ 0 . Hence, for any given δ 00 , by choosing δ 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 and suffixes of all data.
Consequently, we have the following result.
Theorem 2. Let c ∈ N+ and let Σ be any finite alphabet with |Σ| ≥ 2 . Then,the class {αLang(π)β | α, β ∈ Σ∗ , |α| ≤ d, |β| ≤ d, π ∈ regc } is probabilisticallyexactly learnable from text where the polynomial bound for the number of examples
has the parameters pol and c, d .

A Polynomial Time Learner for a Subclass of Regular Patterns

4

13

Experimental Results

Looking at the results proved so far, we see that the theoretical bounds are very 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, polis taken such that, for all n ∈ N ,∞X
1
1
pol(n) = (n + 1) ∗ (n + 2) and=.
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 3 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 3 which does not compute thenumber of examples in advance but monitors its intermediate results and halts if ahypothesis looks sufficiently reasonable with respect to the data seen so far. Moredetails will be given below.
Theorem 3. For Σ = {0, 1} and considering only (n + 1)(n + 2) -regular distributions, Algorithm LRP can be adapted such that it probabilistically exactly learns
REGPAT1 and needs for any L ∈ REGPATm
1 and confidence 1 − δ at most8 ∗ (4m − 1)2 ∗ (4m + 1)2 ∗ (4m + 2)2 ∗ (2m + 2) ∗log(2m + 2) − log(δ)
log(e)

positive examples including pauses.
Proof. We can improve the bounds on the number of examples needed by using
Lemma 1 instead of Lemma 2. We need enough examples to guarantee with probability 1 − (δ/(m + 2)) :(1) A data-item of length 2m or less is drawn in Step (1);(2) For i = 1, 2, . . . , m , the right αi ∈ {0, 1}∗ is selected in Step (2);(3) For i = m + 1 a data-item in A ∩ Xi−1 is found.
In the first case, one has to draw an example of length 2m which is generated
by the pattern. Since at least half of the strings of this length are generated by thepattern, the probability that a randomly drawn datum has this property is at least1.
2(2m+1)(2m+2)
For the second case, one counts the number of strings of length 2m which are in
one of the following three regular expressions.
• (1 − a0 )∗ a0 . . . (1 − ai−1 )∗ ai−1 0{0, 1}∗ ai (1 − ai )∗ ai+1 (1 − ai+1 )∗ . . . am (1 − am )∗ ;• (1 − a0 )∗ a0 . . . (1 − ai−1 )∗ ai−1 1{0, 1}∗ ai (1 − ai )∗ ai+1 (1 − ai+1 )∗ . . . am (1 − am )∗ ;• (1 − a0 )∗ a0 . . . (1 − ai−1 )∗ ai−1 ai (1 − ai )∗ ai+1 (1 − ai+1 )∗ . . . am (1 − am )∗ .
3

HLRP stands for Heuristic Learner for Regular Patterns.

14

J. Case, S. Jain, R. Reischuk, F. Stephan and T. Zeugmann

The number of strings of length 2m generated by the first and generated by the second
expression is the same. But the one generated by the third expression is exactly aslarge as the number of strings of length 2m − 1 which consist of m zeros and m − 1
1
22m−1 . This permits to conclude that
ones. This number has the lower bound 2m−1
the value ai is favored over the value 1 − ai at least with probabilityε=1.
2(2m − 1)(2m + 1)(2m + 2)

The last event for leaving the loop has the same probability ε , one just obtains
it by i = m + 1 in the above regular expressions where of course then the partai (1 − ai )∗ . . . am (1 − am )∗ has to be omitted from the expression. Furthermore, ε isa lower bound for the first probability.
δ
examples.
Using Lemma 1, it suffices to draw (m + 2) times 2 ∗ ε−2 ∗ log(m+2)−log
log eNote that the algorithm uses the parameter n as a bound for m , i.e., n = 2m .
So with probability at least 1−δ , the algorithm uses at most the following quantityof 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 for m =2, 3, . . . , 20 and δ = 1/3 .
We have tried to find further improvements for 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 ignorespause-symbols. This algorithm reads data and tries in parallel to find the 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 :|Σ|−|σ|;(|σ| + 1) ∗ (|σ + 2|)
X
probL,# (#) = 1 −probL,# (τ );probL,# (σ) =τ ∈LprobL (σ) =probL,# (σ).
1 − probL,# (#)

The probabilities can be obtained from probΣ∗ ,# as follows: In the case of probL,# , one
draws an example string σ and then provides σ to the learner in the case that σ ∈ L
and provides # to the learner otherwise. In the case of probL , one draws examples
according to probΣ∗ ,# until an example in L is found which one then provides to thelearner.

A Polynomial Time Learner for a Subclass of Regular Patterns

15

Since Algorithm HLRP ignores pause-symbols, the experiments were run with
examples drawn according to probL,# . While the algorithm runs, one can count the
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 numberof drawn examples are different for probL and probL,# .
The used heuristic is Algorithm HLRP. The two main modifications to the theoretical model are the following: The algorithm alternately draws a data item andtries to learn from the data seen so far until it thinks that the result of the learningtrial gives a sufficiently reasonable hypothesis. Furthermore, only sufficiently short
data-items are considered.
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 ≤ m , the number of data-items in A generated by the regular expression(Σ \ {a0 })∗ a0 . . . (Σ \ {ai−1 })∗ ai−1 ai Σ∗
minus the number of the data-items in A generated by(Σ \ {a0 })∗ a0 . . . (Σ \ {ai−1 })∗ ai−1 bΣ∗is at least g(m) for any b ∈ Σ \ {ai } ;• the number of data-items in A generated by the regular expression(Σ \ {a0 })∗ a0 . . . (Σ \ {am })∗ am
is at least g(m) .

16

J. Case, S. Jain, R. Reischuk, F. Stephan and T. Zeugmann

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 data stored in A .
(ITF)
Output the resulting pattern ρ and Halt.
End
Note that in the second condition on ρ , the regular expressions for i = 0 are
a0 Σ∗ and bΣ∗ ; for i = 1 the corresponding expressions are (Σ \ {a0 })∗ a0 a1 Σ∗ and(Σ \ {a0 })∗ a0 bΣ∗ .
The For-Loop labeled (ITF) removes variables not needed to generate the data.
It is included for the later considered case where the above algorithm is adapted tolearn regular patterns outside REGPAT1 . Surprisingly, for all experiments done withthe alphabet {0, 1, 2} , there were no errors caused by removing superfluous variables
in an otherwise correct pattern. Thus this routine was actually always activatedwhen |Σ| ≥ 3 , even when learning languages from REGPAT1 where this routine issuperfluous. The routine is not used for Σ = {0, 1} since there the patterns are notunique: 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 theresource-bounds and then gives up. The parameter bound is initialized 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 existence of the pattern ρ can be checked
effectively by constructing it inductively as in Algorithm LRP.
m correct without pause
101000
4064.909
20
9994184.943
30
993
4909.675
40
970
6439.009
50
967
8895.355
60
946
11980.308
70933
15777.6998092720792.314
90917
27871.036
100
89748742.807

with pause % used
upper bound81633.997
4.42
3 ∗ 1012
167777.073
5.42447 ∗ 1012
294712.912
7.377999 ∗ 1012
515298.445
9.05
62110 ∗ 1012
889807.785
9.79304901 ∗ 1012
1438119.953
10.53 1119325 ∗ 1012
2209051.668
11.44 3361797 ∗ 1012
3325566.018
12.03 8716312 ∗ 1012
5017601.075
12.63 20197744 ∗ 1012
9749833.913
13.24 42832613 ∗ 1012

Figure 1: Learning REGPATm
1 where Σ = {0, 1} .
Figure 1 gives a table on the outcome of running Algorithm HLRP in orderto learn 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A Polynomial Time Learner for a Subclass of Regular Patterns

17

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 to belearned. 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 fourthcolumn state the average number of examples needed. The third column counts
the examples drawn excluding the pause-symbols and the fourth column counts theexamples 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 upperbound is the theoretically sufficient number of examples with respect to confidence
90
100
1 − δ = 2/3 . Only trials for patterns in REGPAT80
were
1 , REGPAT1 , REGPAT1
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 toviolating 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 probability
1
distribution produces with probability n+1
a string which has at least the length nand 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 nothing about the language andmight 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 the alphabet {0, 1} . The algorithm was run for thesame 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
number of correct patterns was 998 , 998 and 994 respectively. Larger factors giveeven worse results. Relaxing the third condition and permitting more long 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 than boundterminals. But if one has a memory limit of length ` , then, in average, every ` -thlearning 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 choicebound = `/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 haveto 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 is going down for large m .
More precisely, the larger the parameter m , the less likely the learner succeeds tolearn any given pattern from REGPATm
c . Repairing this by having larger values forg(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 dependenceof the alphabet size. The larger the alphabet, the more restrictive is the length bound18

J. Case, S. Jain, R. Reischuk, F. Stephan and T. Zeugmann|Σ| correct repetitions without pause
with pause % used
2967
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
Figure 2: Learning REGPAT50
1 in dependence of the alphabet size.
|Σ|
2
2
2
3
3
3
4
4
4

c m∗c correct rptts. without pause
with pause % used
1
12
1000
0
5130.285
123529.904
3.58
2
12
920
9
23256.913
738004.683
1.08
3
12
890
17
37152.843
1542162.670
0.71
1
12
1000
15
98571.932
3460717.043
0.36
2
12
957
159
268867.961 14615063.504
0.11
3
12
922 1034
611210.432 58396686.666
0.06
1
12
1000
294
436565.410 20142491.835
0.12
2
12
711 3677
1905036.705 171744393.587
0.04
3
12
23 8922
1924946.265 396696831.533
0.03
6
4
Figure 3: Learning REGPAT12
1 , REGPAT2 and REGPAT3 .

on the choice of data considered. So, on one hand the number of incorrect hypotheses
went down from 33 to 5 . On the other hand, the amount of 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 rerun on the same pattern. For the alphabet{0, 1, 2, 3, 4} , it was four times needed to repeat the learning process twice.
An attempt was made to adapt the algorithm for c = 2, 3 and to run it forlarger alphabet sizes. Since the provenly correct algorithm needs a large quantityof data exceeding any practical bound, the heuristic approach already implemented
in Algorithm HLRP was chosen: One uses the learner for REGPAT1 in order tofigure 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 thealphabets {0, 1, 2} and {0, 1, 2, 3} , the last three lines of Algorithm HLRP wererun and taken into account at the check for 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 the terminals a1 , a2 , . . . , a12were 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 thepatterns to be learned in the data for Figure 3 had always 12 terminal symbols. It
turned out that the data for the experiments in Figure 3 are much more sensitive tothe alphabet size than those 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.

A Polynomial Time Learner for a Subclass of Regular Patterns

19

For the alphabet {0, 1, 2, 3} , the main problem are too excessive usage of memory
and time, so that many trials were aborted or rerun. For only 23 out of the 1000
languages from REGPAT43 , Algorithm HLRP terminated in any of the ten trials.
But in that case, it always gave the correct pattern. Note that for REGPAT43 , theaverage number of examples drawn heavily depends on the choice of parameters:
every trial reads at most 4 ∗ 107 examples (with pauses) and the overall number ofexamples 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 upper bound imposed by running-time constraints. Therefore, the main
message of these 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 computer withless severe running time constraints, Algorithm HLRP has a similar performance forthe 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 theexact form of the pattern is selected randomly. Based on the reasons just outlined,
the alphabet {0, 1, 2} was chosen for these experiments.
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 firstof 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 and ends
with one, two or three terminals following the last variable, then one adds withprobability 1/2 a further variable and with probability 1/6 the digit a for a =1, 2, 3 .
• 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 thelearning 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 oflearning 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 pattern is3−15 ∗ 16−1 ∗ 17−1 = 1/3902902704 for m = 15 . So the expected value for the number

20

J. Case, S. Jain, R. Reischuk, F. Stephan and T. Zeugmann

m correct repetitions without pause
51000
0
13666.581
61000
030471.300
71000
069797.8078999178186.534
9997
13134352.582
10
997
71
177112.452
11
992
244
259912.841
12
983
351
284064.711
13
955
568
365624.652
14
898
974
511091.000
15
795
1850
779662.091

with pause % used
303467.013
2.95854851.633
1.302504307.913
0.593526912.510
0.477190948.532
0.25
11066283.854
0.1919128675.970
0.1324450019.647
0.1135745664.161
0.1054322939.087
0.0994019439.240
0.08

Figure 4: Learning regular patterns with Σ = {0, 1, 2} following Setting 2.
of example 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 that 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 ofAlgorithm HLRP which figures out the positions of the variables in the pattern.

5

Conclusion

In Theorem 1, it is shown that the class of c -regular pattern languages is probabilistically exactly learnable from any text drawn from a probability distribution prob
satisfying∞X1|Σ|−|σ|where= 1,
prob(σ) =pol(|σ|)pol(n)
n=0
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 2 extends the learning algorithm to the case where patterns starting or ending
with a constantly bounded number of terminals is permitted. Algorithm HLRP
is a heuristic based on Algorithm LRP, which has been implemented to learn theclass REGPAT1 . Its parameters have been determined experimentally. This permits
to learn the classes REGPATm
1 faster for small m but these improved bounds are
not theoretically generalized for all m . Furthermore, only small alphabets Σ havebeen considered, all experiments were run for alphabets of sizes 2, 3, 4, 5 only. Aninteresting observation is that by skipping long examples, Algorithm HLRP has anexperimentally 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 which might leadthe learner to wrong conclusions. While Algorithm HLRP gave very good results for
REGPAT1 , its performance for REGPATc with c > 1 was not so convincing. The

A Polynomial Time Learner for a Subclass of Regular Patterns

21

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 isa variable and between which not. On one hand, for alphabets having a finite sizeof 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 thevariables. On the other hand, this second part needs attention for the special case of
the alphabet {0, 1} since there the solution is not unique.

Acknowledgment
The authors would like to thank Phil Long for fruitful discussions.

References[1] D. Angluin. Finding patterns common to a set of strings. Journal of Computerand System Sciences, 21:46–62, 1980.
[2] S. Arikawa, T. Shinohara and A. Yamamoto. Learning elementary formal systems. Theoretical Computer Science, 95:97–113, 1992.
[3] I. Bratko and S. Muggleton. Applications of inductive logic programming. Communications of the ACM, 1995.
[4] A. Brāzma, E. Ukkonen and J. Vilo. Discovering unbounded unions of regularpattern 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.
[5] J. Case, S. Jain, S. Kaufmann, A. Sharma and F. Stephan. Predictive learning models for concept drift. Theoretical Computer Science, 268:323–349, 2001.
Special Issue for ALT 1998.
[6] J. Case, S. Jain, S. Lange and T. Zeugmann. Incremental concept learning forbounded data mining. Information and Computation, 152(1):74–110, 1999.
[7] T. Erlebach, P. Rossmanith, H. Stadtherr, A. Steger and T. Zeugmann. Learning
one-variable pattern languages very efficiently on average, in parallel, and byasking queries. Theoretical Computer Science, 261(1):119-156, 2001.
[8] E.M. Gold. Language identification in the limit. Information and Control, 10:447–
474, 1967.
[9] T. Hagerup and C. Rüb. A guided tour of Chernoff bounds. Information Processing Letters, 33(10):305–308, 1990.
[10] 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.

22

J. Case, S. Jain, R. Reischuk, F. Stephan and T. Zeugmann[11] 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.
[12] S. Lange and R. Wiehagen. Polynomial time inference of arbitrary pattern languages. New Generation Computing, 8:361–370, 1991.
[13] N. Lavrač and S. Džeroski. Inductive Logic Programming: Techniques and Applications. Ellis Horwood, 1994.
[14] S. Matsumoto and A. Shinohara. Learnability of subsequence languages. Information Modeling and Knowledge Bases VIII, pages 335–344, IOS Press, 1997.
[15] T. Mitchell. Machine Learning. McGraw Hill, 1997.
[16] S. Miyano, A. Shinohara and T. Shinohara. Polynomial-time learning of elementary formal systems. New Generation Computing, 18:217–242, 2000.
[17] S. Muggleton and L. De Raedt. Inductive logic programming: Theory and methods. Journal of Logic Programming, 19/20:669–679, 1994.
[18] R. Nix. Editing by examples. Technical Report 280, Department of Computer
Science, Yale University, New Haven, CT, USA, 1983.
[19] 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.
[20] D. Reidenbach. A discontinuity in pattern inference. In V. Diekert and M. Habib,
editors, STACS 2004, 21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004, Proceedings. volume 2996
of Lecture Notes in Computer Science, pages 129140. Springer, 2004.
[21] R. Reischuk and T. Zeugmann. Learning one-variable pattern languages in linear
average time. In Proceedings of the Eleventh Annual Conference on Computational Learning Theory, pages 198–208. ACM Press, 1998.
[22] R. Reischuk and T. Zeugmann. An average-case optimal one-variable patternlanguage learner. Journal of Computer and System Sciences 60(2):302-335, 2000.
[23] P. Rossmanith and T. Zeugmann. Stochastic finite learning of the pattern languages. Machine Learning 44(1/2):67-91, 2001. Special Issue on Automata Induction, Grammar Inference, and Language Acquisition[24] A. Salomaa. Patterns (The Formal Language Theory Column). EATCS Bulletin,
54:46–62, 1994.
[25] A. Salomaa. Return to patterns (The Formal Language Theory Column). EATCS
Bulletin, 55:144–157, 1994.

A Polynomial Time Learner for a Subclass of Regular Patterns

23[26] 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.
[27] S. Shimozono, A. Shinohara, T. Shinohara, S. Miyano, S. Kuhara and S. Arikawa.
Knowledge acquisition from amino acid sequences by machine learning system
BONSAI. Transactions of Information Processing Society of Japan, 35:2009–2018, 1994.
[28] 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.
[29] T. Shinohara. Inferring unions of two pattern languages. Bulletin of Informatics
and Cybernetics, 20:83–88, 1983.
[30] T. Shinohara and S. Arikawa. Learning data entry systems: An application of
inductive inference of pattern languages. Research Report 102, Research Instituteof Fundamental Information Science, Kyushu University, 1983.
[31] 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.
[32] T. Shinohara and H. Arimura. Inductive inference of unbounded unions of patternlanguages from positive data. Theoretical Computer Science, 241:191–209, 2000.
[33] R. Smullyan. Theory of Formal Systems, Annals of Mathematical Studies, No.
47. Princeton, NJ, 1961.
[34] L.G. Valiant. A theory of the learnable. Communications of the ACM 27:1134–
1142, 1984.
[35] K. Wright. Identification of unions of languages drawn from an identifiable class.
In R. Rivest, D. Haussler and M.K. Warmuth, editors, Proceedings of the Second
Annual Workshop on Computational Learning Theory, pages 328–333. Morgan
Kaufmann Publishers, Inc., 1989.
[36] 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.