Can Learning in the Limit be Done Efficiently ?
Thomas Zeugmann 1
Institut für Theoretische Informatik, Universität zu Lübeck, Wallstraße 40, 23560
Lübeck, Germany
thomas@tcs.uni-luebeck.de

Abstract. Inductive inference can be considered as one of the fundamental paradigms of algorithmic learning theory. We survey results recently obtained and show their impact to potential applications.
Since the main focus is put on the efficiency of learning, we also deal
with postulates of naturalness and their impact to the efficiency of limit
learners. In particular, we look at the learnability of the class of all
pattern languages and ask whether or not one can design a learner within
the paradigm of learning in the limit that is nevertheless efficient.
For achieving this goal, we deal with iterative learning and its interplay with the hypothesis spaces allowed. This interplay has also a severe
impact to postulates of naturalness satisfiable by any learner.
Finally, since a limit learner is only supposed to converge in the limit, one
never knows at any particular learning stage whether or not the learner
did already succeed. The resulting uncertainty may be prohibitive inmany applications. We survey results to resolve this problem by outlining a new learning model, called stochastic finite learning. Thoughpattern languages can neither be finitely inferred from positive data nor
PAC-learned, our approach can be extended to a stochastic finite learnerthat exactly infers all pattern languages from positive data with highconfidence.

1. Introduction
Inductive inference can be considered as one of the fundamental paradigmsof algorithmic learning theory. In particular, inductive inference of recursivefunctions and of recursively enumerable languages have been studied intensively
within the last four decades (cf., e.g., [3, 4, 30, 16]). The basic model consideredwithin this framework is learning in the limit which can be informally describedas follows. The learner receives more and more data about the target and maps
these data to hypotheses. Of special interest is the investigation of scenarios inwhich the sequence of hypotheses stabilizes to an accurate and finite description(e.g. a grammar, a program) of the target. Clearly, then some form of learning
must have taken place. Here by data we mean either any infinite sequence of pairsargument-value (in case of learning recursive functions) such that all arguments
appear eventually or any infinite sequence of all members of the target language

2Thomas Zeugmann(in case of language learning from positive data). Alternatively, one can also
study language learning from both positive and negative data.
Most of the work done in the field has been aimed at the following goals: showing what general collections of function classes or language classes are learnable,characterizing those collections of classes that can be learned, studying the impact of several postulates on the behavior of learners to their learning power,and dealing with the influence of various parameters to the efficiency of learning.
However, defining an appropriate measure for the complexity of learning in thelimit has turned out to be quite difficult (cf. Pitt [31]). Moreover, whenever learning in the limit is done, in general one never knows whether or not the learnerhas already converged. This is caused by the fact that it is either undecidableat all whether or not convergence already occurred. But even if it is decidable,
it is practically infeasible to do so. Thus, there is always an uncertainty which
may not be tolerable in many applications of learning.
Therefore, different learning models have been proposed. In particular, Valiant’s [46] model of probably approximately correct (abbr. PAC) learning has
been very influential. As a matter of fact, this model puts strong emphasis on
the efficiency of learning and avoids the problem of convergence at all. In the
PAC model, the learner receives a finite labeled sample of the target concepts andoutputs, with high probability, a hypothesis that is approximately correct. The
sample is drawn with respect to an unknown probability distribution and theerror of as well as the confidence in the hypothesis are measured with respect
to this distribution, too. Thus, if a class is PAC learnable, one obtains niceperformance guarantees. Unfortunately, many interesting concept classes are not
PAC learnable.
Consequently, one has to look for other models of learning or one is back tolearning in the limit. So, let us assume that learning in the limit is our methodof choice. What we would like to present in this survey is a rather general way totransform learning in the limit into stochastic finite learning. It should also be
noted that our ideas may be beneficial even in case that the considered concept
class is PAC learnable.
Furthermore, we aim to outline how a thorough study of limit learnabilityof concept classes may nicely contribute to support our new approach. We exemplify the research undertaken by mainly looking at the class of all patternlanguages introduced by Angluin [1]. As Salomaa [37] has put it “Patterns are
everywhere” and thus we believe that our research is worth the effort undertaken.
There are several problems that have to be addressed when dealing withthe learnability of pattern languages. First, the nice thing about patterns is thatthey are very intuitive. Therefore, it seems desirable to design learners outputting
pattern as their hypotheses. Unfortunately, membership is known to be N P complete for the pattern languages (cf. [1]). Thus, many of the usual approaches
used in machine learning will directly lead to infeasible learning algorithms. As
a consequence, we shall ask what kind of appropriate hypothesis spaces can beused at all to learn the pattern languages, and what are the appropriate learning
strategies.

Can Learning in the Limit be Done Efficiently?

3

In particular, we shall deal with the problem of redundancy in the hypothesis space chosen, with consistency, conservativeness, and iterative learning. Hereconsistency means that the intermediate hypotheses output by the learner docorrectly reflect the data seen so far. Conservativeness addresses the problem
to avoid overgeneralization, i.e., preventing the learner from guessing a proper
superset of the target language. These requirements are naturally arising desiderata, but this does not mean that they can be fulfilled. With iterative learning, thelearning machine, in making a conjecture, has access to its previous conjecture
and the latest data item coming in. Iterative learning is also a natural requirement whenever learning in the limit is concerned, since no practical learner canprocess at every learning stage all examples provided so far, it may even not beable to store them.
Finally, we address the question how efficient the overall learning process canbe performed, and how we can get rid of the uncertainty of not knowing whether
or not the learner has already converged.

2. Preliminaries
Unspecified notation follows Rogers [35]. By N = {0, 1, 2, . . .} we denote theset of all natural numbers. We set N+ = N \ {0} . The cardinality of a set S isdenoted by |S| . Let ∅, ∈, ⊂, ⊆ , ⊃ , and ⊇ , denote the empty set, elementof, proper subset, subset, proper superset, and superset, respectively.
Let ϕ0 , ϕ1 , ϕ2 , . . . denote any fixed acceptable programming system for all(and only) the partial recursive functions over N (cf. Rogers [35]). Then ϕk is
the partial recursive function computed by program k .
In the following subsection we define the main learning models consideredwithin this paper.
2.1. Learning in the Limit
Gold’s [12] model of learning in the limit allows one to formalize a rather
general class of learning problems, i.e., learning from examples. For defining
this model we assume any recursively enumerable set X and refer to it as thelearning domain. By ℘(X ) we denote the power set of X . Let C ⊆ ℘(X ) , andlet c ∈ C be non-empty; then we refer to C and c as a concept class and aconcept, respectively. Let c be a concept, and let t = (xj )j∈N be any infinite
sequence of elements xj ∈ c such that range(t) =df {xj j ∈ N} = c . Then t issaid to be a positive presentation or, synonymously, a text for c . By text(c) wedenote the set of all positive presentations for c . Moreover, let t be a positive
presentation, and let y ∈ N . Then, we set ty = x0 , . . . , xy , i.e., ty is the initial+
segment of t of length y + 1 , and t+
y =df {xj j ≤ y} . We refer to ty as thecontent of ty .
Furthermore, let σ = x0 , . . . , xn−1 be any finite sequence. Then we use |σ|to denote the length n of σ , and let content(σ) and σ + , respectively, denote

4

Thomas Zeugmann

the content of σ . Additionally, let t be a text and let τ be a finite sequence;then we use σ  t and σ  τ to denote the sequence obtained by concatenating σ
onto the front of t and τ , respectively.
Alternatively, one can also consider complete presentations or, synonymously,
informants. Let c be a concept; then any sequence i = (xj , bj )j∈N of labeled examples, where bj ∈ {+, −} such that {xj j ∈ N} = X and i+ ={xj (xj , bj ) = (xj , +), j ∈ N} = c and i− = {xj (xj , bj ) = (xj , −), j ∈ N} =X \ c is called an informant for c . For the sake of presentation, the following
definitions are only given for the text case, the generalization to the informant
case should be obvious. We sometimes use the term data sequence to refer toboth text and informant, respectively.
An inductive inference machine (abbr. IIM) is an algorithm that takes as
input larger and larger initial segments of a text and outputs, after each input, ahypothesis from a prespecified hypothesis space H = (hj )j∈N . The indices j are
regarded as suitable finite encodings of the concepts described by the hypotheses.
A hypothesis is said to describe a concept c iff c = h .
Definition 1. Let C be any concept class, and let H = (hj )j∈N be ahypothesis space for it. C is called learnable in the limit from text iff there is an
IIM M such that for every c ∈ X and every text t for c ,(1) for all n ∈ N+ , M (tn ) is defined,(2) there is a j such that c = hj and for all but finitely many n ∈ N+ ,M (tn ) = j .
By LimTxt we denote the collection of all concepts classes C that are learnable in the limit from text1 . Note that instead of LimTxt sometimes TxtEx is
used.
Note that Definition 1 does not contain any requirement concerning efficiency.
Before we are going to deal with efficiency, we want to point to another crucial
parameter of our learning model, i.e., the hypothesis space H . Since our goalis algorithmic learning, we can consider the special case that X = N and let C
be any subset of the collection of all recursively enumerable sets over N . Let
Wi = domainϕi . In this case, (Wj )j∈N is the most general hypothesis space.
Within this setting many learning problems can be described. Moreover,this setting has been used to study the general capabilities of different learningmodels which can be obtained by suitable modifications of Definition 1. There are
numerous papers performing studies along this line of research (cf., e.g., [16, 30]
and the references therein). On the one hand, the results obtained considerably
broaden our general understanding of algorithmic learning. On the other hand,
one has also to ask what kind of consequences one may derive from these resultsfor practical learning problems. This is a non-trivial question, since the settingof learning recursively enumerable languages is very rich. Thus, it is conceivable1

If learning from informant is considered we use LimInf to denote the collection of
all concepts classes C that are learnable in the limit from informant.

Can Learning in the Limit be Done Efficiently?

5

that several of the phenomena observed hold in this setting due to the fact too
many sets are recursively enumerable and there are no counterparts within theworld of efficient computability.
As a first step to address this question we mainly consider the scenariothat indexable concept classes with uniformly decidable membership have tobe learned (cf. Angluin [2]). A class of non-empty concepts C is said to be
an indexable class with uniformly decidable membership provided there arean effective enumeration c0 , c1 , c2 , ... of all and only the concepts in C and arecursive function f such that for all j ∈ N and all elements x ∈ X we have
1, if x ∈ cj ,f (j, x) =0, otherwise.
In the following we refer to indexable classes with uniformly decidable membership as to indexable classes for short. Furthermore, we call any enumeration(cj )j∈N of C with uniformly decidable membership problem an indexed family.
Since the paper of Angluin [2] learning of indexable concept classes has attracted much attention (cf., e.g., Zeugmann and Lange [51]). Let us shortly provide some-well known indexable classes. Let Σ be any finite alphabet of symbols,
and let X be the free monoid over Σ , i.e., X = Σ ∗ . We set Σ + = Σ ∗ \ {λ} ,where λ denotes the empty string. As usual, we refer to subsets L ⊆ X as
languages. Then the set of all regular languages, context-free languages, andcontext-sensitive languages are indexable classes.
n
Next,
S let Xn = {0, 1} be the set of all n -bit Boolean vectors. We consider
X = n≥1 Xn as learning domain. Then, the set of all concepts expressible asa monomial, a k -CNF, a k -DNF, and a k -decision list form indexable classes.

When learning indexable classes C , it is generally assumed that the hypothesis space H has to be an indexed family, too. We distinguish class preserving learning and class comprising learning defined by C = range(H) andC ⊆ range(H) , respectively. When dealing with class preserving learning, one
has the freedom to choose as hypothesis space a possibly different enumeration of
the target class C . In contrast, when class comprising learning is concerned, thehypothesis space may enumerate, additionally, languages not belonging to C .
Note that, in general, one has to allow class comprising hypothesis spaces toobtain the maximum possible learning power (cf. Lange and Zeugmann [20, 22]).
Finally, we call an hypothesis space redundant if it is larger than necessary, i.e.,there is at least one hypothesis in H not describing any concept from the target
class or one concept possesses at least two different descriptions in H . Thus,
non-redundant hypothesis spaces are as small as possible.
Formally, a hypothesis space H = (hj )j∈N is non-redundant for some target
concept class C iff range(H) = C and hi 6= hj for all i, j ∈ N with i 6= j .
Otherwise, H is a redundant hypothesis space for C .
Next, let us come back to the issue of efficiency. Looking at Definition 1
we see that an IIM M has always access to the whole history of the learning
process, i.e., in order to compute its actual guess M is fed all examples seen so6Thomas Zeugmannfar. In contrast to that, next we define iterative IIMs. An iterative IIM is only
allowed to use its last guess and the next element in the positive presentation of
the target concept for computing its actual guess. Conceptionally, an iterative
IIM M defines a sequence (Mn )n∈N of machines each of which takes as its input
the output of its predecessor.
Definition 2 (Wiehagen [47]). Let C be a concept class, let c be a concept,
let H = (hj )j∈N be a hypothesis space, and let a ∈ N ∪ {∗} . An IIM M
ItLimTxt H -infers c iff for every t = (xj )j∈N ∈ text(c) the following conditions
are satisfied:(1) for all n ∈ N , Mn (T ) is defined, where M0 (T ) =df M (x0 ) and for alln ≥ 0 : Mn+1 (T ) =df M (Mn (T ), xn+1 ) ,(2) the sequence (Mn (T ))n∈N converges to a number j such that c = hj .
Finally, M ItLimTxt H -infers C iff, for each c ∈ C , M ItLimTxt H -infers c .
In the latter definition Mn (t) denotes the (n+1) th hypothesis output by M
when successively fed the text t . Thus, it is justified to make the following
convention. Let σ = x0 , . . . , xn be any finite sequence of elements over the
relevant learning domain. Moreover, let C be any concept class over X , andlet M be any IIM that iteratively learns C . Then we denote by My (σ) the(y + 1) th hypothesis output by M when successively fed σ provided y ≤ n ,and there exists a concept c ∈ C with σ + ⊆ c . Furthermore, we let M∗ (σ)
denote M|σ|−1 (σ) .
Moreover, whenever learning a concept class from text, a major problem
one has to deal with is avoiding or detecting overgeneralization. An overgeneralization occurs if the learner is guessing a superconcept of the target concept.
Clearly, such an overgeneralized guess cannot be detected by using the incoming
positive data only. Therefore, one may be tempted to disallow overgeneralized
guesses at all. Learners behaving thus are called conservative. Intuitively speaking a conservative IIM maintains its actual hypothesis at least as long as it has
not seen data contradicting it. More formally, an IIM M is said to be conservative iff for all concepts c in the target class C and all texts t for c thecondition M (ty ) 6= M (ty+z ) then t+
y+z 6⊆ hM (ty ) is fulfilled.
Another property of learners quite often found in the literature is consistency.
Informally, a learner is called consistent if all its intermediate hypotheses docorrectly reflect the data seen so far. More formally, an IIM M is said to beconsistent iff t+
x ⊆ hM (tx ) for all x ∈ N and every text t for every concept cin the target class C .
Whenever one talks about the efficiency of learning besides the storage neededby the learner one has also to consider the time complexity of the learner. When
talking about the time complexity of learning, it does not suffice to consider thetime needed to compute the actual guess. What really counts in applications is
the overall time needed until successful learning. Therefore, following Daley andSmith [10] we define the total learning time as follows.

Can Learning in the Limit be Done Efficiently?

7

Let C be any concept class, and let M be any IIM that learns C in thelimit. Then, for every c ∈ C and every text t for c , let
Conv (M, t) =df the least number m ∈ N+
such that for all n ≥ m, M (tn ) = M (tm )denote the stage of convergence of M on t (cf. [12]). Note that Conv (M, t) = ∞if M does not learn the target concept from its text t . Moreover, by TM (tn )we denote the time to compute M (tn ) . We measure this time as a function of
the length of the input and call it the update time. Finally, the total learning
time taken by the IIM M on successive input t is defined as
Conv (M,t)

T T (M, t) =df

X

TM (tn ).

n=1

Clearly, if M does not learn the target concept from text t then the total
learning time is infinite.
Two more remarks are in order here. First, it has been argued elsewhere thatwithin the learning in the limit paradigm a learning algorithm is invoked only
when the current hypothesis has some problem with the latest observed data.
However, such a viewpoint implicitly assumes that membership in the target
concept is decidable in time polynomial in the length of the actual input. Thismay be not case. Thus, directly testing consistency would immediately lead toa non-polynomial update time provided membership is not known to be in P .
Second, Pitt [31] addresses the question with respect to what parameter one
should measure the total learning time. In the definition given above this parameter is the length of all examples seen so far. Clearly, now one could try to playwith this parameter by waiting for a large enough input before declaring success. However, when dealing with the learnability of non-trivial concept classes,
in the worst-case the total learning time will be anyhow unbounded. Thus, itdoes not make much sense to deal with the worst-case. Instead, we shall study
the expected total learning time. In such a setting one cannot simply wait forlong enough inputs. Therefore, using the definition of total learning time given
above seems to be reasonable.
Next, we define important concept classes which we are going to consider
throughout this survey.
2.2. The Pattern Languages
Following Angluin [1] we define patterns and pattern languages as follows.
Let A = {0, 1, . . .} be any non-empty finite alphabet containing at least twoelements. By A∗ we denote the free monoid over A . The set of all finite nonnull strings of symbols from A is denoted by A+ , i.e., A+ = A∗ \ {λ} , where
λ denotes the empty string. Let X = {xi i ∈ N} be an infinite set of variables such that A ∩ X = ∅ . Patterns are non-empty strings over A ∪ X , e.g.,8Thomas Zeugmann

01, 0x0 111, 1x0 x0 0x1 x2 x0 are patterns. The length of a string s ∈ A∗ and ofa pattern π is denoted by |s| and |π| , respectively. A pattern π is in canonical form provided that if k is the number of different variables in π then thevariables occurring in π are precisely x0 , . . . , xk−1 . Moreover, for every j with0 ≤ j < k − 1 , the leftmost occurrence of xj in π is left to the leftmost occurrence of xj+1 . The examples given above are patterns in canonical form. In thesequel we assume, without loss of generality, that all patterns are in canonicalform. By Pat we denote the set of all patterns in canonical form.
If k is the number of different variables in π then we refer to π as toa k -variable pattern. By Pat k we denote the set of all k -variable patterns.
Furthermore, let π ∈ Pat k , and let u0 , . . . , uk−1 ∈ A+ ; then we denote byπ[x0 /u0 , . . . , xk−1 /uk−1 ] the string w ∈ A+ obtained by substituting uj foreach occurrence of xj , j = 0, . . . , k − 1 , in the pattern π . For example, let
π = 0x0 1x1 x0 . Then π[x0 /10, x1 /01] = 01010110 . The tuple (u0 , . . . , uk−1 ) is
called a substitution. Furthermore, if |u0 | = · · · = |uk−1 | = 1 , then we refer to(u0 , . . . , uk−1 ) as to a shortest substitution. Let π ∈ Pat k ; we define the language
generated by pattern π by L(π) = {π[x0 /u0 , . . . , xk−1 /uk−1 ] u0 , . . . , uk−1 ∈A+ } . By
S PAT k we denote the set of all k -variable pattern languages. Finally,
PAT = k∈N PAT k denotes the set of all pattern languages over A .
S Furthermore, we let Q range over finite sets of patterns and define L(Q) =π∈Q L(π) , i.e., the union of all pattern languages generated by patterns from
Q . Moreover, we use Pat(k) and PAT (k) to denote the family of all unionsof at most k canonical patterns and the family of all unions of at most kpattern languages, respectively. That is, Pat(k) = {Q Q ⊆ Pat, |Q| ≤ k} andPAT (k) = {L (∃Q ∈ Pat(k))[L = L(Q)]} . Finally, let L ⊆ A+ be a language,and let k ∈ N+ ; we define Club(L, k) = {Q |Q| ≤ k, L ⊆ L(Q), (∀Q0 )[Q0 ⊂Q ⇒ L 6⊆ L(Q0 )]} . Club stands for consistent least upper bounds.
The pattern languages have been intensively investigated (cf., e.g., Salomaa [37, 38], and Shinohara and Arikawa [43] for an overview). Nix [29] as well as
Shinohara and Arikawa [43] outlined interesting applications of pattern inference
algorithms. For example, pattern language learning algorithms have been successfully applied for solving problems in molecular biology (cf., e.g., Shimozono
et al. [39], Shinohara and Arikawa [43]).
As it turned out, pattern languages and finite unions of pattern languages aresubclasses of Smullyan’s [45] elementary formal systems (Abbr. EFS). Arikawa etal. [5] have shown that EFS can also be treated as a logic programming language
over strings. Recently, the techniques for learning finite unions of pattern languages have been extended to show the learnability of various subclasses of EFS(cf. Shinohara [42]). The investigations of the learnability of subclasses of EFSs
are interesting because they yield corresponding results about the learnabilityof subclasses of logic programs. Hence, these results are also of relevance forInductive Logic Programming (ILP) [28, 23, 8, 24]. Miyano et al. [26] intensively
studied the polynomial-time learnability of EFSs.
Therefore, we may consider the learnability of pattern languages and ofunions thereof as a nice test bed for seeing what kind of results one may ob-

Can Learning in the Limit be Done Efficiently?

9tain by considering the corresponding learning problems within the setting oflearning in the limit.

3. Results
Within this section we ask whether or not the pattern languages and finite
unions thereof can be learned efficiently. The principal learnability of the patternlanguages from text with respect to the hypothesis space Pat has been established by Angluin [1]. However, her algorithm is based on computing descriptive
patterns for the data seen so far. Here a pattern π is said to be descriptive (forthe set S of strings contained in the input provided so far) if π can generate
all strings contained in S and no other pattern with this property generates aproper subset of the language generated by π . Since no efficient algorithm isknown for computing descriptive patterns, and finding a descriptive pattern of
maximum length is N P -hard, its update time is practically intractable.
There are also serious difficulties when trying to learn the pattern languages
within the PAC model introduced by Valiant [46]. In the original model, the sample complexity depends exclusively on the VC dimension of the target concept
class and the error and confidence parameters ε and δ , respectively. Recently,
Mitchell et al. [25] have shown that even the class of all one-variable patternlanguages has infinite VC dimension. Consequently, even this special subclassof PAT is not uniformly PAC learnable. Moreover, Schapire [40] has shownthat pattern languages are not PAC learnable in the generalized model provided
P/poly 6= N P/poly with respect to every hypothesis space for PAT that is
uniformly polynomially evaluable. Though this result highlights the difficulty of
PAC learning PAT it has no clear application to the setting considered in thispaper, since we aim to learn PAT with respect to the hypothesis space Pat .
Since the membership problem for this hypothesis space is N P -complete, it is
not polynomially evaluable (cf. [1]).
In contrast, Kearns and Pitt [18] have established a PAC learning algorithm
for the class of all k -variable pattern languages. Positive examples are generated with respect to arbitrary product distributions while negative examples areallowed to be generated with respect to any distribution. In their algorithm thelength of substitution strings is required to be polynomially related to the lengthof the target pattern. Finally, they use as hypothesis space all unions of polynomially many patterns that have k or fewer variables2 . The overall learning
time of their PAC learning algorithm is polynomial in the length of the target
pattern, the bound for the maximum length of substitution strings, 1/ε , 1/δ ,and |A| . The constant in the running time achieved depends doubly exponential
on k , and thus, their algorithm becomes rapidly impractical when k increases.
2

More precisely, the number of allowed unions is at most poly(|π|, s, 1/ε, 1/δ, |A|) ,where π is the target pattern, s the bound on the length on substitution strings,
ε and δ are the usual error and confidence parameter, respectively, and A is thealphabet of constants over which the patterns are defined.

10

Thomas Zeugmann

Finally, Lange and Wiehagen [19] have proposed an inconsistent but iterativeand conservative algorithm that learns PAT with respect to Pat . We shallstudy this algorithm below in much more detail.
But before doing it, we aim to figure out under which circumstances iterative
learning of PAT is possible at all. A first answer is given by the following
theorems from Case et al. [9]. Note that Pat is a non-redundant hypothesis
space for PAT .
Theorem 1 (Case et al. [9]). Let C be any concept class, and let H =(hj )j∈N be any non-redundant hypothesis space for C . Then, every IIM M that
ItLimTxt H -infers C is conservative.
Proof. Suppose the converse, i.e., there are a concept c ∈ C , a text t =(xj )j∈N ∈ text(c) , and a y ∈ N such that, for j = M∗ (ty ) and k = M∗ (ty+1 ) =M (j, xy+1 ) , both j 6= k and t+y+1 ⊆ hj are satisfied. The latter implies xy+1 ∈hj , and thus we may consider the following text t̃ ∈ text(hj ) . Let t̂ = (x̂j )j∈N
be any text for hj and let t̃ = x̂0 , xy+1 , x̂1 , xy+1 , x̂2 , . . . Since M has to learn
hj from t̃ there must be a z ∈ N such that M∗ (t̃z+r ) = j for all r ≥ 0 . But
M∗ (t̃2z+1 ) = M (j, xy+1 ) = k , a contradiction.
tu
Next, we point to another peculiarity of PAT , i.e., it meets the superset
condition defined as follows. Let C be any indexable class. C meets the superset
condition if, for all c, c0 ∈ C , there is some ĉ ∈ C being a superset of both c
and c0 .
Theorem 2. (Case et al. [9]). Let C be any indexable class meeting thesuperset condition, and let H = (hj )j∈N be any non-redundant hypothesis spacefor C . Then, every consistent IIM M that ItLimTxt H -infers C may be used
to decide the inclusion problem for H .
Proof. Let X be the underlying learning domain, and let (wj )j∈N be aneffective enumeration of all elements in X . Then, for every i ∈ N , ti = (xij )j∈N
is the following computable text for hi . Let z be the least index such thatwz ∈ hi . Recall that, by definition, hi 6= ∅ , since H is an indexed family, andthus wz must exist. Then, for all j ∈ N , we set xij = wj , if wj ∈ hi , andxij = wz , otherwise.
We claim that the following algorithm Inc decides, for all i, k ∈ N , whether
or not hi ⊆ hk .
Algorithm Inc: “On input i, k ∈ N do the following:
Determine the least y ∈ N with i = M∗ (tiy ) . Test whether or not ti,+
⊆ hk .
yIn case it is, output ‘Yes,’ and stop. Otherwise, output ‘No,’ and stop.”
Clearly, since H is an indexed family and ti is a computable text, Inc is
an algorithm. Moreover, M learns hi on every text for it, and H is a nonredundant hypothesis space. Hence, M has to converge on text ti to i , andtherefore Inc has to terminate.
It remains to verify the correctness of Inc . Let i, k ∈ N .

Can Learning in the Limit be Done Efficiently?

11

Clearly, if Inc outputs ‘No,’ a string s ∈ hi \hk has been found, and hi 6⊆ hk
follows.
Next, consider the case that Inc outputs ‘Yes.’ Suppose to the contrary thathi 6⊆ hk . Then, there is some s ∈ hi \ hk . Now, consider M when fed the textt = tiy  tk . Since ti,+
⊆ hk , t is a text for hk . Since M learns hk , there isysome r ∈ N such that k = M∗ (tiy  tkr ) . By assumption, there are some ĉ ∈ Cwith hi ∪ hk ⊆ ĉ , and some text t̂ for ĉ having the initial segment tiy  s  tkr .
By Theorem 1, M is conservative. Since s ∈ hi and i = M∗ (t̂y ) , we obtainM∗ (t̂y+1 ) = M (i, s) = i . Consequently, M∗ (tiy  s  tkr ) = M∗ (tiy  tkr ) . Finally,iksince s ∈ t̂+/ hk , M fails to consistently learn
y+r+2 , k = M∗ (ty  tr ) , and s ∈ĉ from text t̂ , a contradiction. This proves the theorem.
tuTaking into account that the inclusion problem for Pat is undecidable (cf.
Jiang et al. [17] and that PAT meets the superset condition, since L(x0 ) = A+ ,by Theorem 2, we immediately arrive at the following corollary.
Corollary 3 (Case et al. [9]). If an IIM M ItLimTxt Pat -learns PAT
then M is inconsistent.
As a matter of fact, the latter corollary generalizes to all non-redundant hypothesis spaces for PAT . All the ingredients to prove this can be found in Zeugmann et al. [52]. Consequently, if one wishes to learn the pattern languages orunions of pattern languages iteratively, then either redundant hypothesis spaces
or inconsistent learners cannot be avoided.
As for unions, the first result goes back to Shinohara [41] who proved theclass of all unions of at most two pattern languages to be in LimTxt Pat(2) .
Wright [49] extended this result to PAT (k) ∈ LimTxt Pat(k) for all k ≥ 1 .
Moreover, Theorem 4.2 in Shinohara andS Arimura’s [44] together with a lemma
from Blum and Blum [6] shows that k∈N PAT (k) is not LimTxt H -inferable
for every hypothesis space H .
The iterative learnability of PAT (k) has been established by Case et al. [9].
Our learner is also consistent. Thus, the hypothesis space used had to be designed
to be redundant. We only sketch the proof here.
Theorem 4.
(1) Club(L, k) is finite for all L ⊆ A+ and all k ∈ N+ ,(2) If L ∈ PAT (k) , then Club(L, k) is non-empty and contains a set Q , suchthat L(Q) = L .
Proof. Part (2) is obvious. Part (1) is easy for finite L . For infinite L , itfollows from the lemma below.
Lemma 1. Let k ∈ N+ , let L ⊆ A+ be any language, and suppose t =(sj )j∈N ∈ text(L). Then,+(1) Club(t+0 , k) can be obtained effectively from s0 , and Club(tn+1 , k) is effec+
tively obtainable from Club(tn , k) and sn+1 (* note the iterative nature *).

12Thomas Zeugmann+(2) The sequence Club(t+0 , k), Club(t1 , k), . . . converges to Club(L, k).

Putting it all together, one directly gets the following theorem.
Theorem 5. For all k ≥ 1 , PAT (k) ∈ ItLimTxt .
Proof. Let can(·) , be some computable bijection from finite classes of finite
sets of patterns onto N . Let pad be a 1–1 padding function such that, for all
x, y ∈ N , Wpadx,y = Wx . For a finite class S of T
sets of patterns, let g(S)denote a grammar obtained, effectively from S , for Q∈S L(Q) .
Let L ∈ PAT (k) , and let t = (sj )j∈N ∈ text(L) . The desired IIM M is de+fined as follows. We set M0 (t) = M (s0 ) = padg(Club(t+0 , k)), can(Club(t0 , k)) ,and for all n > 0 , let
Mn+1 (t) = M (Mn (t), sn+1 )+= padg(Club(t+n+1 , k)), can(Club(tn+1 , k))Using Lemma 1 it is easy to verify that Mn+1 (t) = M (Mn (t), sn+1 ) can beobtained effectively from Mn (t) and sn+1 . Therefore, M ItLimTxt -identifies
PAT (k) .
tu
So far, the general theory provided substantial insight into the iterative learnability of the pattern languages. But still, we do not know anything about the
number of examples needed until successful learning and the total amount of timeto process them. Therefore, we address this problem in the following subsection.
3.1. Stochastic Finite Learning
As we have already mentioned, it does not make much sense to study theworst-case behavior of learning algorithms with respect to their total learning
time. The reason for this phenomenon should be clear, since an arbitrary text
may provide the information needed for learning very late. Therefore, in the following we always assume a class D of admissible probability distributions over
the relevant learning domain. Ideally, this class should be parameterized. Then,the data fed to learner are generated randomly with respect to one of the probability distributions from the class D of underlying probability distributions.
Furthermore, we introduce a random variable CONV for the stage of convergence. Note that CONV can be also interpreted as the total number of examples
read by the IIM M until convergence. The first major step to be performed consists now in determining the expectation E[CONV ] . Clearly, E[CONV ] should
be finite for all concepts c ∈ C and all distributions D ∈ D . Second, one has todeal with tail bounds for E[CONV ] . The easiest way to perform this step is touse Markov’s inequality, i.e., we always know that
Pr(CONV ≥ t · E[CONV ]) ≤1
for all t ∈ N+ .
t

However, quite often one can obtain much better tail bounds. If the underlying learner is known to be conservative and rearrangement-independent we always

Can Learning in the Limit be Done Efficiently?

13

get exponentially shrinking tail bounds. A learner is said to be rearrangementindependent if its output depends exclusively on the range and length of its
input (cf. [21] and the references therein). These tail bounds are established by
the following theorem.
Theorem 6. (Rossmanith and Zeugmann [36].) Let CONV be the sample complexity of a conservative and rearrangement-independent learning algorithm. Then
Pr(CONV ) ≥ 2t · E[CONV ]) ≤ 2 −t for all t ∈ N .
Theorem 6 puts the importance of rearrangement-independent and conservative learners into the right perspective. As long as the learnability of indexedfamilies is concerned, these results have a wide range of potential applications,since every conservative learner can be transformed into a learner that is bothconservative and rearrangement-independent provided the hypothesis space isappropriately chosen (cf. Lange and Zeugmann [21]).
Furthermore, since the distribution of CONV decreases geometrically for
all conservative and rearrangement-independent learning algorithms, all higher
moments of CONV exist in this case, too. Thus, instead of applying Theorem
6 directly, one can hope for further improvements by applying even sharper tailbounds using for example Chebyshev’s inequality.
Additionally, the learner takes a confidence parameter δ as input. But incontrast to learning in the limit, the learner itself decides how many examples
it wants to read. Then it computes a hypothesis, outputs it and stops. The
hypothesis output is correct for the target with probability at least 1 − δ .
The explanation given so far explains how it works, but not why it does.
Intuitively, the stochastic finite learner simulates the limit learner until an upperbound for twice the expected total number of examples needed until convergencehas been met. Assuming this to be true, by Markov’s inequality the limit learnerhas now converged with probability 1/2 . All what is left, is to decrease theprobability of failure. This is done by using the tail bounds for CONV . Applying
Theorem 6, one easily sees that increasing the sample complexity by a factorof O(log 1δ ) results in a probability of 1 − δ for having reached the stage of
convergence. If Theorem 6 is not applicable, one can still use Markov’s inequality
but then the sample complexity needed will increase by a factor of 1/δ .
It remains to explain how the stochastic finite learner can calculate the upperbound for E[CONV ] . This is precisely the point where we need the parameterization of the class D of underlying probability distributions. Since in general,
it is not known which distribution from D has been chosen, one has to assume
a bit of prior knowledge or domain knowledge provided by suitable upper and/or
lower bounds for the parameters involved. A more serious difficulty is to incorporate the unknown target concept into this estimate. This step depends onthe concrete learning problem on hand, and requires some extra effort. We shallexemplify it below.

14

Thomas Zeugmann

Now we are ready to formally define stochastic finite learning.
Definition 3 ([33, 34, 36]). Let D be a set of probability distributions on
the learning domain, C a concept class, H a hypothesis space for C , andδ ∈ (0, 1) . (C, D) is said to be stochastically finitely learnable with δ -confidencewith respect to H iff there is an IIM M that for every c ∈ C and every
D ∈ D performs as follows. Given any random data sequence θ for c generated
according to D , M stops after having seen a finite number of examples andoutputs a single hypothesis h ∈ H . With probability at least 1−δ (with respect
to distribution D ) h has to be correct, that is c = h .
If stochastic finite learning can be achieved with δ -confidence for every δ > 0then we say that (C, D) can be learned stochastically finite with high confidence.
Note that there are subtle differences between our model and PAC learning.
By its definition, stochastic finite learning is not completely distribution independent. A bit of additional knowledge concerning the underlying probability
distributions is required. Thus, from that perspective, stochastic finite learning
is weaker than the PAC-model. On the other hand, we do not measure the quality of the hypothesis with respect to the underlying probability distribution.
Instead, we require the hypothesis computed to be exactly correct with highprobability. Note that exact identification with high confidence has been considered within the PAC paradigm, too (cf., e.g., Goldman et al. [13]). Conversely,
we also can easily relax the requirement to learn probably exactly correct but
whenever possible we shall not do it.
Furthermore, in the uniform PAC model as introduced in Valiant [46] thesample complexity depends exclusively on the VC dimension of the target concept class and the error and confidence parameters ε and δ , respectively. Thismodel has been generalized by allowing the sample size to depend on the concept
complexity, too (cf., e.g., Blumer et al. [7] and Haussler et al. [15]). Provided
no upper bound for the concept complexity of the target concept is given, such
PAC learners decide themselves how many examples they wish to read (cf. [15]).
This feature is also adopted to our setting of stochastic finite learning. However,all variants of PAC learning we are aware of require that all hypotheses from therelevant hypothesis space are uniformly polynomially evaluable. Though this requirement may be necessary in some cases to achieve (efficient) stochastic finite
learning, it is not necessary in general as we shall see below.
Next, let us exemplify our model by looking at the concept class of all patternlanguages. The results presented below have been obtained by Zeugmann [50]and Rossmanith and Zeugmann [36]. Our stochastic finite learner uses Lange
and Wiehagen’s [19] pattern language learner as a main ingredient. We consider
here learning from positive data only.
Recall that every string of a particular pattern language is generated by atleast one substitution. Therefore, it is convenient to consider probability distributions over the set of all possible substitutions. That is, if π ∈ Pat k , thenit suffices to consider any probability distribution D over A+ × · · · × A+ . For{z}|k−timesCan Learning in the Limit be Done Efficiently?

15(u0 , . . . , uk−1 ) ∈ A+ × · · · × A+ we denote by D(u0 , . . . , uk−1 ) the probability
that variable x0 is substituted by u0 , variable x1 is substituted by u1 , . . . ,and variable xk−1 is substituted by uk−1 .
In particular, we mainly consider a special class of distributions, i.e., product distributions. Let k ∈ N+ , then the class of all product distributions for
Pat k is defined as follows. For each variable xj , 0 ≤ j ≤ k − 1 , we assume an
arbitrary probability distribution Dj over A+ on substitution strings. Then
we call D = D0 × · · · × Dk−1 product distribution over A+ × · · · × A+ , i.e.,
Qk−1
D(u0 , . . . , uk−1 ) = j=0 Dj (uj ) . Moreover, we call a product distribution regular if D0 = · · · = Dk−1 . Throughout this paper, we restrict ourselves to deal
with regular distributions. We therefore use d to denote
Qk−1 the distribution overA+ on substitution strings, i.e, D(u0 , . . . , uk−1 ) = j=0 d(uj ) . We call a regular distribution admissible if d(a) > 0 for at least two different elements a ∈ A .
As a special case of an admissible distribution we consider the uniform distribution over A+ , i.e., d(u) = 1/(2 · |A|)` for all strings u ∈ A+ with |u| = ` .
We will express all estimates with the help of the following parameters: E[Λ] ,α and β , where Λ is a random variable for the length of the examples drawn. α
and β are defined below. To get concrete bounds for a concrete implementation
one has to obtain c from the algorithm and has to compute E[Λ] , α , and βfrom the admissible probability distribution D . Let u0 , . . . , uk−1 be independent random variables with distribution d for substitution strings. Whenever
the index i of ui does not matter, we simply write u or u0 .
The two parameters α and β are now defined via d . First, α is simply theprobability that u has length 1, i.e.,X
α = Pr(|u| = 1) =
d(a).
a∈A

Second, β is the conditional probability that two random strings that get substituted into π are identical under the condition that both have length 1 , i.e.,
2
. X
X

β = Pr u = u0 |u| = |u0 | = 1 =d(a)2d(a) .
a∈calAa∈A

Note that we have omitted the assumption of a text to exhaust the target language. Instead, we only demand the data sequence fed to the learner to contain“enough” information to recognize the target pattern. The meaning of “enough”
is mainly expressed by the parameter α .
The model of computation as well as the representation of patterns we assume
is the same as in Angluin [1]. In particular, we assume a random access machinethat performs a reasonable menu of operations each in unit time on registers oflength O(log n) bits, where n is the input length.
Lange and Wiehagen’s [19] algorithm (abbr. LWA) works as follows. Let hn
be the hypothesis computed after reading s1 , . . . , sn , i.e., hn = M (s1 , . . . , sn ) .

16Thomas Zeugmann

Then h1 = s1 and for all n > 1 :
if |hn−1 | < |sn | hn−1 ,if |hn−1 | > |sn |hn = sn ,
hn−1 ∪ sn , if |hn−1 | = |sn |The algorithm computes the new hypothesis only from the latest example
and the old hypothesis. If the latest example is longer than the old hypothesis,
the example is ignored, i.e., the hypothesis does not change. If the latest example is shorter than the old hypothesis, the old hypothesis is ignored and the
new example becomes the new hypothesis. If, however, |hn−1 | = |sn | the new
hypothesis is the union of hn−1 and sn . The union % = π ∪ s of a canonicalpattern π and a string s of the same length is defined asπ(i), if π(i) = s(i)xj , if π(i) 6= s(i) & ∃k < i : [%(k) = xj , s(k) = s(i),%(i) =
π(k) = π(i)]xm , otherwise, where m = #var(%(1) . . . %(i − 1))
where %(0) = λ for notational convenience. Note that the resulting patternis again canonical.
If the target pattern does not contain any variable then the LWA converges
after having read the first example. Hence, this case is trivial and we therefore
assume in the following always k ≥ 1 , i.e., the target pattern has to containat least one variable. Our next theorem analyzes the complexity of the union
operation.
Theorem 7 (Rossmanith and Zeugmann [36]). The union operation can becomputed in linear time.
Furthermore, the following bound for the stage of convergence for every target
pattern from Pat k can be shown.
Theorem 8(Rossmanith and Zeugmann [36]).
1· log1/β (k) for all k ≥ 2 .
E[CONV ] = O
αkHence, bytotal learning time can be estimated by
 Theorem 7, the expected1
E[T T ] = O
E[Λ] log1/β (k) for all k ≥ 2 .
αk
For a better understanding of the bound obtained we evaluate it for theuniform distribution and compare it to the minimum number of examples needed
for learning a pattern language via the LWA.
Theorem 9 (Rossmanith and Zeugmann [36]). E[T T ] = O(2k |π| log|A| (k))
for the uniform distribution and all k ≥ 2 .

Can Learning in the Limit be Done Efficiently?

17

Theorem 10 (Zeugmann [50]). To learn a pattern π ∈ Pat k the LWA needs
exactly blog|A| (|A| + k − 1)c + 1 examples in the best case.
The main difference between the two bounds just given is the factor 2k
which precisely reflects the time the LWA has to wait until it has seen the firstshortest string from the target pattern language. Moreover, in the best-case the
LWA is processing shortest examples only. Thus, we introduce MC to denotethe number of minimum length examples read until convergence. Then, one canshow that
2 ln(k) + 3+2 .
E[MC ] ≤ln(1/β)Note that Theorem 8 is shown by using the bound for E[MC ] just given.
More precisely, we have E[CONV ] = (1/αk )E[MC ] . Now, we are ready totransform the LWA into a stochastic finite learner.
Theorem 11 (Rossmanith and Zeugmann [36]). Let α∗ , β∗ ∈ (0, 1) . Assume
D to be a class of admissible probability distributions over A+ such that α ≥α∗ , β ≤ β∗ and E[Λ] finite for all distributions D ∈ D . Then (PAT , D) is
stochastically finitely learnable with high confidence from text.
Proof. Let D ∈ D , and let δ ∈ (0, 1) be arbitrarily fixed. Furthermore, lett = s1 , s2 , s3 , . . . be any randomly generated text with respect to D for thetarget pattern language. The wanted learner M uses the LWA as a subroutine.
Additionally, it has a counter for memorizing the number of examples alreadyseen. Now, we exploit the fact that the LWA produces a sequence (τn )n∈N+ of
hypotheses such that |τn | ≥ |τn+1 | for all n ∈ N+ .
The learner runs the LWA until for the first time C many examples havebeen processed, where |τ |  2 ln(|τ |) + 3·+2(A)
C = α1∗ln(1/β∗ )and τ is the actual output made by the LWA.
Finally, in order to achieve the desired confidence, the learner sets γ = dlog 1δ e
and runs the LWA for a total of 2 · γ · C examples. This is the reason we need
the counter for the number of examples processed. Now, it outputs the lasthypothesis τ produced by the LWA, and stops thereafter.
Clearly, the learner described above is finite. Let L be the target language
and let π ∈ Pat k be the unique pattern such that L = L(π) . It remains toargue that L(π) = L(τ ) with probability at least 1 − δ .
First, the bound in (A) is an upper bound for the expected number of examples needed for convergence by the LWA that has been established in Theorem 8(via the reformulation using E[MC ] given above). On the one hand, this follows
from our assumptions about the allowed α and β as well as from the fact that|τ | ≥ |π| for every hypothesis output. On the other hand, the learner does notknow k , but the estimate #var (π) ≤ |π| is sufficient. Note that we have to use

18

Thomas Zeugmannin (A) the bound for E[MC ] given above, since the target pattern may contain
zero or one different variables.
Therefore, after having processed C many examples the LWA has alreadyconverged on average. The desired confidence is then an immediate consequenceof Corollary 6.
tu
The latter theorem allows a nice corollary which we state next. Making thesame assumption as done by Kearns and Pitt [18], i.e., assuming the additional
prior knowledge that the target pattern belongs to Pat k , the complexity of thestochastic finite learner given above can be considerably improved. The resulting
learning time is linear in the expected string length, and the constant depending
on k grows only exponentially in k in contrast to the doubly exponentiallygrowing constant in Kearns and Pitt’s [18] algorithm. Moreover, in contrast
to their learner, our algorithm learns from positive data only, and outputs ahypothesis that is correct for the target language with high probability.
Again, for the sake of presentation we shall assume k ≥ 2 . Moreover, if theprior knowledge k = 1 is available, then there is also a much better stochastic
finite learner for PAT 1 (cf. [34]).
Corollary 12. Let α∗ , β∗ ∈ (0, 1) . Assume D to be a class of admissible
probability distributions over A+ such that α ≥ α∗ , β ≤ β∗ and E[Λ] finite
for all distributions D ∈ D . Furthermore, let k ≥ 2 be arbitrarily fixed. Then
there exists a learner M such that
(1) M learns (PAT k , D) stochastically finitely with high confidence from text,and(2) The running time of M is O α̂∗k E[Λ] log1/β∗ (k) log2 (1/δ) .
(* Note that α̂∗k and log1/β∗ (k) now are constants. *)4. Conclusions
The present paper surveyed results recently obtained concerning the iterative
learnability of the class of all pattern languages and finite unions thereof. In
particular, it could be shown that there are strong dependencies between iterative
learning, the class of admissible hypothesis spaces and additional requirements
to the learner such as consistency, conservativeness and the decidability of the
inclusion problem for the hypothesis space chosen. Looking at these results, wehave seen that the LWA is in some sense optimal.
Moreover, by analyzing the average-case behavior of Lange and Wiehagen’s
pattern language learning algorithm with respect to its total learning time andby establishing exponentially shrinking tail bounds for a rather rich class oflimit learners, we have been able to transform the LWA into a stochastic finite
learner. The price paid is the incorporation of a bit prior knowledge concerning
the class of underlying probability distributions. When applied to the class ofCan Learning in the Limit be Done Efficiently?

19

all k -variable pattern languages, where k is a priori known, the resulting total
learning time is linear in the expected string length.
Thus, the present paper provides evidence that analyzing the average-casebehavior of limit learners with respect to their total learning time may be considered as a promising path towards a new theory of efficient algorithmic learning.
Recently obtained results along the same path as outlined in Erlebach et al.[11]as well as in Reischuk and Zeugmann [32, 34] provide further support for the
fruitfulness of this approach.
In particular, in Reischuk and Zeugmann [32, 34] we have shown that onevariable pattern languages are learnable for basically all meaningful distributions
within an optimal linear total learning time on the average. Furthermore, thislearner can also be modified to maintain the incremental behavior of Lange andWiehagen’s [19] algorithm. Instead of memorizing the pair (PRE, SUF) , it canalso store just the two or three examples from which the prefix PRE and the suffix
SUF of the target pattern has been computed. While it is no longer iterative, it
is still a bounded example memory learner. A bounded example memory learneris essentially an iterative learner that is additionally allowed to memorize an apriori bounded number of examples (cf. [9] for a formal definition).
While the one-variable pattern language learner from [34] is highly practical,
our stochastic finite learner for the class of all pattern languages is still not goodenough for practical purposes. But our results surveyed point to possible directions for potential improvements. However, much more effort seems necessary todesign a stochastic finite learner for PAT (k) .
Additionally, we have applied our techniques to design a stochastic finite
learner for the class of all concepts describable by a monomial which is basedon Haussler’s [14] Wholist algorithm. Here we have assumed the examples to bebinomially distributed. The sample size of our stochastic finite learner is mainly
bounded by log(1/δ) log n , where δ is again the confidence parameter and n
is the dimension of the underlying Boolean learning domain. Thus, the boundobtained is exponentially better than the bound provided within the PAC model.
Our approach also differs from U-learnability introduced by Muggleton [27].
First of all, our learner is fed with positive examples only, while in Muggleton’s [27] model examples labeled with respect to their containment in the target
language are provided. Next, we do not make any assumption concerning the distribution of the target patterns. Furthermore, we do not measure the expected
total learning time with respect to a given class of distributions over the targets
and a given class of distributions for the sampling process, but exclusively independence on the length of the target. Finally, we require exact learning and
not approximately correct learning.

References
1. D. Angluin, Finding Patterns common to a Set of Strings, Journal of Computerand System Sciences 21, 1980, 46–62.

20

Thomas Zeugmann

2. D. Angluin, Inductive inference of formal languages from positive data, Information and Control 45, 1980, 117–135.
3. D. Angluin and C.H. Smith. Inductive inference: Theory and methods. Computing
Surveys 15, No. 3, 1983, 237 - 269.
4. D. Angluin and C.H. Smith. Formal inductive inference. “Encyclopedia of Artificial Intelligence” (St.C. Shapiro, Ed.), Vol. 1, pp. 409 - 418, Wiley-Interscience
Publication, New York.
5. S. Arikawa, T. Shinohara and A. Yamamoto, Learning elementary formal systems,
Theoretical Computer Science 95, 97–113, 1992.
6. L. Blum and M. Blum, Toward a mathematical theory of inductive inference,
Information and Control 28, 125–155, 1975.
7. A. Blumer, A. Ehrenfeucht, D. Haussler and M. Warmuth, Learnability and the
Vapnik-Chervonenkis Dimension, Journal of the ACM 36 (1989), 929–965.
8. I. Bratko and S. Muggleton, Applications of inductive logic programming, Communications of the ACM, 1995.
9. J. Case, S. Jain, S. Lange and T. Zeugmann, Incremental Concept Learning for
Bounded Data Mining, Information and Computation 152, No. 1, 1999, 74–110.
10. R. Daley and C.H. Smith. On the Complexity of Inductive Inference. Information
and Control 69 (1986), 12–40.
11. 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, No. 1-2, 2001, 119–156.
12. E.M. Gold, Language identification in the limit, Information and Control 10(1967), 447–474.
13. S.A. Goldman, M.J. Kearns and R.E. Schapire, Exact identification of circuits
using fixed points of amplification functions. SIAM Journal of Computing 22,
1993, 705–726.
14. D. Haussler, Bias, version spaces and Valiant’s learning framework, “Proc. 8th National Conference on Artificial Intelligence,” pp. 564–569, San Mateo, CA: Morgan
Kaufmann, 1987.
15. D. Haussler, M. Kearns, N. Littlestone and M.K. Warmuth, Equivalence of models
for polynomial learnability. Information and Computation 95 (1991), 129–161.
16. S. Jain, D. Osherson, J.S. Royer and A. Sharma, “Systems That Learn: An Introduction to Learning Theory,” MIT-Press, Boston, Massachusetts, 1999.
17. T. Jiang, A. Salomaa, K. Salomaa and S. Yu, Inclusion is undecidable for pattern languages, in “Proceedings 20th International Colloquium on Automata,
Languages and Programming,” (A. Lingas, R. Karlsson, and S. Carlsson, Eds.),
Lecture Notes in Computer Science, Vol. 700, pp. 301–312, Springer-Verlag, Berlin,
1993.
18. M. Kearns L. Pitt, A polynomial-time algorithm for learning k –variable patternlanguages from examples. in “Proc. Second Annual ACM Workshop on Computational Learning Theory” (pp. 57–71). San Mateo, CA: Morgan Kaufmann, 1989.
19. S. Lange and R. Wiehagen, Polynomial-time inference of arbitrary pattern languages. New Generation Computing 8 (1991), 361–370.
20. S. Lange and T. Zeugmann, Language learning in dependence on the space of
hypotheses. in “Proc. of the 6th Annual ACM Conference on Computational
Learning Theory,” (L. Pitt, Ed.), pp. 127–136, ACM Press, New York, 1993.
21. S. Lange and T. Zeugmann, Set-driven and Rearrangement-independent Learningof Recursive Languages, Mathematical Systems Theory 29 (1996), 599–634.
22. S. Lange and T. Zeugmann, Incremental Learning from Positive Data, Journal ofComputer and System Sciences 53(1996), 88–103.

Can Learning in the Limit be Done Efficiently?

21

23. N. Lavrač and S. Džeroski, “Inductive Logic Programming: Techniques and Applications,” Ellis Horwood, 1994.
24. T. Mitchell. “Machine Learning,” McGraw Hill, 1997.
25. A. Mitchell, A. Sharma, T. Scheffer and F. Stephan, The VC-dimension of Subclasses of Pattern Languages, in “Proc. 10th International Conference on Algorithmic Learning Theory,” (O. Watanabe and T. Yokomori, Eds.), Lecture Notes in
Artificial Intelligence, Vol. 1720, pp. 93 - 105, Springer-Verlag, Berlin, 1999.
26. S. Miyano, A. Shinohara and T. Shinohara, Polynomial-time learning of elementary
formal systems, New Generation Computing, 18:217–242, 2000.
27. S. Muggleton, Bayesian Inductive Logic Programming, in “Proc. 7th Annual ACM
Conference on Computational Learning Theory” (M. Warmuth, Ed.), pp. 3–11,
ACM Press, New York, 1994.
28. S. Muggleton and L. De Raedt, Inductive logic programming: Theory and methods,
Journal of Logic Programming, 19/20:669–679, 1994.
29. R.P. Nix, Editing by examples, Yale University, Dept. Computer Science, Technical
Report 280, 1983.
30. D.N. Osherson, M. Stob and S. Weinstein, “Systems that Learn, An Introduction to
Learning Theory for Cognitive and Computer Scientists,” MIT-Press, Cambridge,
Massachusetts, 1986.
31. L. Pitt, Inductive Inference, DFAs and Computational Complexity, in “Proc. 2ndInt. Workshop on Analogical and Inductive Inference” (K.P. Jantke, Ed.), Lecture
Notes in Artificial Intelligence, Vol. 397, pp. 18–44, Springer-Verlag, Berlin, 1989.
32. R. Reischuk and T. Zeugmann, Learning One- Variable Pattern Languages in Linear Average Time, in “Proc. 11th Annual Conference on Computational Learning
Theory - COLT’98,” July 24th - 26th, Madison, pp. 198–208, ACM Press 1998.
33. R. Reischuk and T. Zeugmann, A Complete and Tight Average-Case Analysis
of Learning Monomials, in “Proc. 16th International Symposium on Theoretical
Aspects of Computer Science,” (C. Meinel and S. Tison, Eds.), Lecture Notes in
Computer Science, Vol. 1563, pp. 414–423, Springer-Verlag , Berlin 1999.
34. R. Reischuk and T. Zeugmann, An Average-Case Optimal One-Variable Pattern
Language Learner, Journal of Computer and System Sciences 60, No. 2, 2000,
302–335.
35. H. Rogers, Jr., “Theory of Recursive Functions and Effective Computability,”
McGraw–Hill, New York, 1967.
36. P. Rossmanith and T. Zeugmann. Stochastic Finite Learning of the Pattern Languages, Machine Learning 44, No. 1-2, 2001, 67–91.
37. Patterns (The Formal Language Theory Column), EATCS Bulletin 54, 46–62,
1994.
38. Return to patterns (The Formal Language Theory Column), EATCS Bulletin 55,
144–157, 1994.
39. 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.
40. R.E. Schapire, Pattern languages are not learnable, In M.A. Fulk & J. Case
(Eds.), Proceedings of the Third Annual ACM Workshop on Computational Learning Theory, (pp. 122–129). San Mateo, CA: Morgan Kaufmann, (1990).
41. T. Shinohara, Inferring unions of two pattern languages, Bulletin of Informatics
and Cybernetics 20, 83–88, 1983.
42. T. Shinohara, Inductive inference of monotonic formal systems from positive data,
New Generation Computing 8, 371–384, 1991.

22

Thomas Zeugmann

43. T.Shinohara and S. Arikawa, Pattern inference, in “Algorithmic Learning forKnowledge-Based Systems,” (K.P. Jantke and S. Lange, Eds.), Lecture Notes in
Artificial Intelligence, Vol. 961, pp. 259–291, Springer-Verlag, Berlin, 1995.
44. T. Shinohara and H. Arimura, Inductive inference of unbounded unions of patternlanguages from positive data, in “Proceedings 7th International Workshop on
Algorithmic Learning Theory,” (S. Arikawa and A.K. Sharma, Eds.), Lecture Notes
in Artificial Intelligence, Vol. 1160, pp. 256–271, Springer-Verlag, Berlin, 1996.
45. R. Smullyan, “Theory of Formal Systems,” Annals of Mathematical Studies,No. 47. Princeton, NJ, 1961.
46. L.G. Valiant, A Theory of the Learnable, Communications of the ACM 27 (1984),
1134–1142.
47. R. Wiehagen. Limes-Erkennung rekursiver Funktionen durch spezielle Strategien.
Journal of Information Processing and Cybernetics (EIK) 12, 1976, 93–99.
48. R. Wiehagen and T. Zeugmann, Ignoring Data may be the only Way to Learn
Efficiently, Journal of Experimental and Theoretical Artificial Intelligence 6 (1994),
131–144.
49. K. Wright, Identification of unions of languages drawn from an identifiableclass, in “Proceedings of the 2nd Workshop on Computational Learning Theory,” (R. Rivest, D. Haussler, and M. Warmuth, Eds.), pp. 328–333, San Mateo,
CA: Morgan Kaufmann, 1989.
50. 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, No. 1-2, 1998, 117–145.
51. T. Zeugmann and S. Lange, A guided tour across the boundaries of learning
recursive languages, in “Algorithmic Learning for Knowledge-Based Systems,”(K.P. Jantke and S. Lange, Eds.), Lecture Notes in Artificial Intelligence, Vol. 961,
pp. 190–258, Springer-Verlag, Berlin, 1995.
52. T. Zeugmann, S. Lange and S. Kapur, Characterizations of monotonic and dual
monotonic language learning, Information and Computation 120, 155–173, 1995.