Learning a Subclass of Regular Patterns in
Polynomial TimeJohn Case1,? , Sanjay Jain2,?? , Rüdiger Reischuk3 , Frank Stephan4 , andThomas Zeugmann3
1

Dept. of Computer and Information Sciences, University of Delaware, Newark, DE
19716-2586, USA
case@cis.udel.edu
2School of Computing, National University of Singapore, Singapore 117543
sanjay@comp.nus.edu.sg
3
Institute for Theoretical Informatics, University at Lübeck, Wallstr. 40, 23560
Lübeck, Germany{reischuk, thomas}@tcs.mu-luebeck.de
4Mathematisches Institut, Universität Heidelberg, Im Neuenheimer Feld 294, 69120
Heidelberg, Germany
fstephan@math.uni-heidelberg.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 of success on extended regular languages generated bypatterns π 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 x0 , . . . , xm are variables and where α1 , ..., αm are each stringsof constants or terminals of length c . This assumes that the algorithm
randomly draws samples with natural and plausible assumptions on the
distribution.
The more general looking case of extended regular patterns which alternate between a variable and fixed length constant strings, beginning andending with either a variable or a constant string is similarly handled.

1

Introduction

The pattern languages were formally introduced by Angluin [1]. A pattern language is (by definition) one generated by all the positive length substitution
instances in a pattern, such as, for example,
abxycbbzxa— where the variables (for substitutions) are x, y, z and the constants/terminals
are a, b, c .
?

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.

2

John Case et al.

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 (cf., e.g., [1, 6, 7, 10, 12, 21, 20, 22, 23, 26, 19, 29] andthe 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, [11, 5, 27, 3, 32]).
Nix [18] as well as Shinohara and Arikawa [28, 29] outline interesting applications of pattern inference algorithms. For example, pattern language learningalgorithms have been successfully applied toward some problems in molecular biology (see [25, 29]). Pattern languages and finite unions of pattern languages turnout to be subclasses of Smullyan’s [30] Elementary Formal Systems (EFSs), andArikawa, Shinohara and Yamamoto [2] show that the EFSs can also be treated asa 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 arealso of relevance for Inductive Logic Programming (ILP) [17, 13, 4, 15]. Miyano
et al. [16] intensively studied the polynomial-time learnability 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, patternlanguages are a prominent example of non-regular languages that can be learnedin the limit from positive data (cf. [1]). Gold [9] has introduced the corresponding learning model. Let L be any language; then a text for L is any infinite
sequence of strings containing eventually all strings of L , and nothing else. The
information given to the learner are successively growing initial segments of atext. 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 a correct description of the target
language.
Angluin [1] 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 π . But noefficient 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 ofa 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. Note that this algorithm is also computing descriptive patterns evenof maximum length.

Learning a Subclass of Regular Patterns in Polynomial Time

3

Another important special case extensively studied are the regular patternlanguages introduced by Shinohara [26]. These are generated by the regular patterns, i.e., patterns in which each variable that appears, appears only once. The
learners designed by Shinohara [26] 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 thelength 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 thelimit to a correct hypothesis for the target language. But the stage of convergence
is not decidable. Thus, a user never knows whether or not the learning process
is already finished. Such an uncertainty may not be tolerable in practice.
Consequently, one has tried to learn the pattern languages within Valiant’s[31] PAC model. Shapire [24] 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, 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 the class of all k -variable pattern languages, i.e., languages generated bypatterns in which at most k different variables occur. Positive examples 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 have k or fewer variables5 .
The overall learning time of their PAC learning algorithm is polynomial in thelength 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, their algorithm becomes rapidly impracticalwhen 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 classof 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 , i.e., the set of all extended regular patternlanguages where the length of constant strings is 1 (see below for a formal
5

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 on substitution strings,
ε and δ are the usual error and confidence parameter, respectively, and ± is thealphabet of constants over which the patterns are defined.

4John Case et al.

definition). The latter result follows from [16] via an equivalence proof to thecommon subsequence languages studied in [14].
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 efficient learnerfor these classes of languages as noted above. Therefore, we aim to design anefficient learner for an interesting 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 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.
We explain it here for the case mainly studied in this paper, learning fromtext (in our above notation). One looks again at the whole learning process as
learning in the limit. So, the data presented to the learner are growing initial
segments of a text. But now, we do not allow any text. Instead every text is
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 the underlying
probability distribution, E can be expressed in terms the learner may use conceptionally to calculate E . Using Markov’s inequality, one easily sees that theprobability 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 (1/δ) · E many 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, andby 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 (cf.
Definition 5 below). Clearly, in order to have an efficient learner one also has toensure that this hypothesis can be computed in time polynomial in the lengthof 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, c (the lengthof substitution strings) and a term describing knowledge about the probability
distribution as such a parameter.
For REGPATc , we have results for three different models of data presentation. The data are drawn according to the distribution prob described below.

Learning a Subclass of Regular Patterns in Polynomial Time5

The three models are as follows. Thanks to space limitations we present
herein the details and verification of our algorithm for the first model only. The
journal version of this paper will present more details. Σ is the terminal alphabet. For natural numbers c > 0 , Σ c is Σ ∗ restricted to strings of length c .
(1) For drawing of examples according to prob for learning a pattern language generated by π : one draws terminal string σ according to distribution
prob over Σ ∗ until σ ∈ Lang(π) is obtained. Then σ is returned to the learner.
(2) One draws σ according to prob and gives (σ, χLang(π) (σ)) to thelearner.
(3) As in (2), but one gives σ to the learner in the case that σ ∈ Lang(π) ,and gives a pause-symbol to the learner otherwise.
For this paper, the natural and plausible assumptions on prob are the following.
(i) prob(Σ c ) ≥ prob(Σ c+1 ) for all c ;c), where σ ∈ Σ c .
(ii) prob(σ) = prob(Σ|Σ c |
1(iii) there is an increasing polynomial pol such that prob(Σ c ) ≥ pol(c)forall c .

Our algorithm is presented in detail in Section 3 below. The complexity
bounds are described more exactly there, but, basically, the algorithm can bemade 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 .
N.B. Having our patterns defined as starting and ending with variables is not
crucial (since one can handle patterns starting or ending with constants easily byjust 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
constant 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 easeof presentation of proof.

2

Preliminaries

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 .
Let Σ be any non-empty finite set of constants such that |Σ| ≥ 2 and let V
be a countably infinite set of variables such that Σ ∩ V = ∅ . By Σ ∗ we denotethe free monoid over Σ . The set of all finite non-null strings of symbols fromΣ is denoted by Σ + , i.e., Σ + = Σ ∗ \ {λ} , where λ denotes the empty string.
As above, Σ c denotes the set of strings over Σ with length c . We let a, b, . . .

6John Case et al.

range over constant symbols. x, y, z, x1 , x2 , . . . range over variables. 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 symbol a ∈ Σ 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 are considering extended (or erasing) pattern languages, i.e., 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 considered within this paper thanlearning non-erasing ones. For the general case of arbitrary pattern languages,
already Angluin [1] showed the non-erasing pattern languages to be learnablefrom positive data. However, the erasing pattern languages are not learnablefrom positive data if |Σ| = 2 (cf. Reidenbach [19]).
Definition 3 (Shinohara[26]). 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 regc .

(c) REGPATc = {Lang(π) | π ∈ regc } .
Next, we define the learning model considered in this paper. As alreadyexplained in the Introduction, our model differs to a certain extent from the
PAC model introduced by Valiant [31] which is distribution independent. In ourmodel, a bit of background 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 regularpattern languages is known not to be PAC learnable (cf. [16] and the discussion
within the Introduction).

Learning a Subclass of Regular Patterns in Polynomial Time

7

Definition 5. A learner M is said to probabilistically exactly learn a class
L of pattern languages according to probability distribution prob , if for allδ , 0 < δ < 1 , for some polynomial q , when learning a Lang(π) ∈ L , withprobability at least 1 − δ , M draws at most q(|π|, 1δ ) examples according to
the probability distribution prob , and then outputs a pattern π 0 , such that
Lang(π) = Lang(π 0 ) .
As far as drawing of examples according to prob for learning a patternlanguage generated by π is concerned, we assume the following model (the firstmodel discussed in the Introduction): one draws σ according to distribution
prob over Σ ∗ , until σ ∈ Lang(π) is obtained. Then σ is returned to thelearner. (Note: prob is thus defined over Σ ∗ .)The other two models we mentioned in the Introduction are:(2) There is a basic distribution prob and one draws σ according to prob
and gives (σ, χLang(π) (σ)) to the learner.
(3) As in (2), but one gives σ to the learner in the case that σ ∈ Lang(π) ,and gives a pause-symbol to the learner otherwise.
We note that our proof works for models (2) and (3) above too.
For this paper, the assumptions on prob are (as in the Introduction) the
following.
(i) prob(Σ c ) ≥ prob(Σ c+1 ) for all c ∈ N ;c), where σ ∈ Σ c .
(ii) prob(σ) = prob(Σ|Σ c |(iii) there is an increasing polynomial pol with prob(Σ c ) ≥pol(c) 6= 0 for all c ∈ N .

3

1
pol(c)

andMain Result

In this section we will show that REGPATc is probabilistically exactly learnableaccording to probability distributions prob satisfying the constraints describedabove.
Lemma 1. (based on Chernoff Bounds) Suppose X, Y ⊆ Σ ∗ , δ,  are properly
between 0 and 1/2 , and prob(X) ≥ prob(Y ) +  . Let e be the base of natural
logarithm. Then, if one draws at least
2 − log(δ)
∗
2
log e
many examples from Σ ∗ according to the probability distribution prob , thenwith probability at least 1 − δ , more elements of X than of Y show up. The
number 22∗δ is an upper bound for this number.

8John Case et al.

More generally, the following holds.
Lemma 2. One can define a function r(, δ, k) which is polynomial in k, 1 , 1δsuch that for all sets X, Z, Y1 , Y2 , . . . , Yk ⊆ Σ ∗ , the following holds.
If prob(X) − prob(Yi ) ≥  , for i = 1, 2, . . . , k , and prob(Z) ≥  , and one
draws ≥ r(, δ, k) many examples from Σ ∗ according to the distribution prob ,then with 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 .
Proposition 1. For every regular pattern π and all m ∈ N , Lang(π)∩Σ m+1 ≥|Σ| ∗ (Lang(π) ∩ Σ m ) .
Proof. Since any regular pattern π has a variable at the end, the proposition
follows.
Proposition 2. For any fixed constant c ∈ N+ and any alphabet Σ , there is apolynomial f such that for every π ∈ regm
c , at least half of the strings of length
f (m) are generated by π .
Proof. Suppose that π = x0 α1 x1 α2 x2 . . . αm xm , and α1 , α2 , ..., αm ∈ Σ c .
Clearly, there is a length d ≥ c such that for every τ ∈ Σ c S, at least half of thed−cstrings in Σ d contain τ as a substring, that is, are in the set k=0 Σ k τ Σ 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
coin such that all symbols are equally likely. Divide σ into m equal parts oflength d ∗ m . The i -th part contains αi with probability at least 1 − 2−m as a
substring, and 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) meetsthe specification.
We now present our algorithm for learning REGPATc . The algorithm hasprior knowledge about the function r from Lemma 2 and the function f from
Proposition 2. It takes as input c , δ and knowledge about the probability
distribution by getting pol .
Learner (c, δ, pol)(1) Read examples until an n is found such that the shortest example is strictly
shorter than c ∗ n and the total number of examples (including repetitions)is at least


1
n
c
n∗r
,
,
|Σ|
.
2 ∗ |Σ|c ∗ f (n) ∗ pol(f (n)) δLearning a Subclass of Regular Patterns in Polynomial Time

9

Let A be the set of all examples and Aj (j ∈ {1, 2, . . . , n}) , be the examples
whose index is j modulo n ; so the (k ∗ n + j) -th example from A goes to
Aj where k is 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 A ∩ Xi−1 6= ∅ , then let m = i − 1 and go to Step (3).
Choose αi as the β ∈ Σ c , such that |Ai ∩ Yi,β | > |Ai ∩ Yi,β 0 | , for β 0 ∈Σ c − {β} (if there is no such β , then abort the algorithm).
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
Note that since the shortest example is strictly shorter than c ∗ n it holds
that n ≥ 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
for some m ≥ 1 where all αi are in Σ c .
Claim. 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 as defined in the algorithm
and let C(i, β, h) be the cardinality of Yi,β ∩ Lang(π) ∩ Σ h .
Then, for all h > 0 and all β ∈ Σ c \ {αi } , we have C(i, β, h) ≤ |Σ| ∗C(i, αi , h − 1) ≤ C(i, αi , h) .
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 have boththe length c . So the position of αi in σ must be at least one symbol behindthe one of β . If the difference is more than a symbol, η is used to take these
additional symbols.
Now consider the mapping t from Lang(π) ∩ Yi,β to Lang(π) ∩ Yi,αi which
replaces βs in the above representation of σ by αi – thus t(σ) = σi αi ητ . The
mapping t is |Σ| -to- 1 since it replaces the constant β 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η10John Case et al.

is the shortest prefix of σ generated by πi αi . Since πi generates σi andxi α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 . Thus, for β 6= αi , β ∈ Σ c , itholds that C(i, β, h) ≤ |Σ| ∗ C(i, αi , h − 1) . By combining with Proposition 1,
C(i, αi , h) ≥ |Σ| ∗ C(i, αi , h − 1) ≥ C(i, β, h) .
Claim. 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,prob(Yi,β ∩ Lang(π)) +1≤ prob(Yi,αi ∩ Lang(π)).
2 ∗ |Σ|c ∗ pol(f (m)) ∗ f (m), for all h and β ∈ Σ c . Proposition 1 andProof. Let D(i, β, h) = C(i,β,h)|Σ|hClaim 3 give that
D(i, β, h) ≤ D(i, αi , h − 1) ≤ D(i, αi , h).
Since every string in Lang(π) is in some set Yi,β , it holds 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 noting thatprob(Σ h ) ≥11≥.
pol(h)
pol(f (m))

We now show that the learner presented above indeed probabilistically exactly learns Lang(π) , for π ∈ regc .
A loop (Step (2)) invariant 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} .

Learning a Subclass of Regular Patterns in Polynomial Time11

By assumption, i ≤ m and πi−1 is with probability 1 − δ∗(i−1)
anprefix of π , 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 thealgorithm does not stop too early.
If β = αi and β 0 6= αi , thenprob(Yi,β ∩ Lang(π))≥ prob(Yi,β 0 ∩ Lang(π)) +1
2 ∗ |Σ|c ∗ f (m) ∗ pol(f (m)),

by Claim 3. 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 andthe loop-invariant is preserved.
Case 2. i = m + 1 .
By Step (1) of the algorithm, the shortest example is strictly shorter
than c ∗ n and at least c ∗ m by construction. Thus, we already know
m < n.
the previous loops in Step (2) haveWith probability 1 − δ∗(n−1)
ngone through successfully and πm = π . Consider the mapping t whichomits from every string the last symbol. Now σ ∈ Xm iff σ ∈ Lang(π)
and t(σ) ∈/ Lang(π) . Let D(π, h) be the weighted number of strings|Σ h ∩Lang(π)|
generated by π of length h , that is, D(π, h) =. Since|Σ|h1
D(π, f (m)) ≥ 2 and D(π, 0) = 0 , there is a h ∈ {1, 2, . . . , f (m)} such
that
1
1
≥
.
D(π, h) − D(π, h − 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 with probability at least 1 − nδ a string from Xm is in Am ,and in particular in A (by Lemma 2). Thus the algorithm terminates
after going through the step (2) m times with the correct output withprobability at least 1 − δ .
To get polynomial time bound for the learner, we 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 the learningalgorithm. Thus, with probability at least 1 − δ 0 − δ the whole algorithm issuccessful in time and example-number polynomial in m, 1/δ, 1/δ 0 . Thus, for12John Case et al.

any given δ 00 , by choosing δ 0 = δ = δ 00 /2 , one can get the desired polynomial
time algorithm.
We are hoping in the future (not as part of the present paper) to run ouralgorithm on molecular biology data to see if it can quickly provide useful answers.

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. T. Shinohara and H. Arimura. Inductive inference of unbounded unions of patternlanguages from positive data. Theoretical Computer Science, 241:191–209, 2000.
4. I. Bratko and S. Muggleton. Applications of inductive logic programming. Communications of the ACM, 1995.
5. 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’96), 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’98.
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 & Control, 10:447–
474, 1967.
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.
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.

Learning a Subclass of Regular Patterns in Polynomial Time

13

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 Pattern
Languages. In N. Cesa-Bianchi and M. Numao, editors, Algorithmic Learning
Theory, 13th International Conference, ALT 2002, Lübeck, Germany, November
2002, Proceedings, pages 308–320. Springer, 2002.
20. 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.
21. 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
22. A. Salomaa. Patterns (The Formal Language Theory Column). EATCS Bulletin,
54:46–62, 1994.
23. A. Salomaa. Return to patterns (The Formal Language Theory Column). EATCS
Bulletin, 55:144–157, 1994.
24. 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.
25. S. Shimozono, A. Shinohara, T. Shinohara, S. Miyano, S. Kuhara, and S. Arikawa.
Knowledge acquisition from amino acid sequences by machine learning system
BONSAI. Trans. Information Processing Society of Japan, 35:2009–2018, 1994.
26. 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.
27. T. Shinohara. Inferring unions of two pattern languages. Bulletin of Informatics
and Cybernetics, 20:83–88., 1983.
28. 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.
29. T. Shinohara and S. Arikawa. Pattern inference. In Klaus P. Jantke and Steffen
Lange, editors, Algorithmic Learning for Knowledge-Based Systems, volume 961 of
Lecture Notes in Artificial Intelligence, pages 259–291. Springer, 1995.
30. R. Smullyan. Theory of Formal Systems, Annals of Mathematical Studies, No. 47.
Princeton, NJ, 1961.
31. L.G. Valiant. A theory of the learnable. Communications of the ACM 27:1134–
1142, 1984.
32. 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.
33. 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.