A Guided Tour Across the Boundaries ofLearning Recursive Languages
Thomas Zeugmann

Steffen Lange

Research Institute of

HTWK Leipzig

Fundamental Information Science

FB Mathematik und Informatik

Kyushu University 33

PF 66

Fukuoka 812, Japan04251 Leipzig

thomas@rifis.kyushu-u.ac.jp

steffen@informatik.th-leipzig.de

Abstract
The present paper deals with the learnability of indexed families of uniformly recursive languages from positive data as well as from both, positive andnegative data. We consider the influence of various monotonicity constraints
to the learning process, and provide a thorough study concerning the influenceof several parameters. In particular, we present examples pointing to typicalproblems and solutions in the field. Then we provide a unifying framework forlearning. Furthermore, we survey results concerning learnability in dependence
on the hypothesis space, and concerning order independence. Moreover, newresults dealing with the efficiency of learning are provided. First, we investigate
the power of iterative learning algorithms. The second measure of efficiency
studied is the number of mind changes a learning algorithm is allowed to perform. In this setting we consider the problem whether or not the monotonicity
constraints introduced do influence the efficiency of learning algorithms.
The paper mainly emphasis to provide a comprehensive summary of resultsrecently obtained, and of proof techniques developed. Finally, throughout ourguided tour we discuss the question of what a natural language learning algorithm might look like.

1. Introduction
Humans have the ability to learn and to adapt. During the long evolution of
mankind humans have developed the particular ability to acquire their maternal language as well as other languages. Since these abilities have always been considered
the hallmark of intelligence, the challenge to design an “intelligent” computer has
led to considerable interest in learning in the computer science community. Hence,
it would be very nice if we could start our guided tour with a satisfying definition ofwhat learning really is. But our understanding of learning is still too limited. Hence,answering the question what learning is has to be considered to be one of the major
goals of algorithmic learning theory (cf. Angluin (1992)). On the other hand, there isa broad consensus that induction constitutes an important feature of learning. The
corresponding theory is called inductive inference. Inductive inference of formal languages may be characterized as the study of systems that map evidence on a language
into hypotheses about it. Of special interest is the investigation of scenarios in which
the sequence of hypotheses stabilizes to an accurate and finite description (a grammar)of the target language. If evidence is understood as reasonable information, then allthese scenarios model at least a certain aspect of learning. This can be seen as follows.
Up to the unknown point of stabilization only finitely many data concerning the target language have been provided. Nevertheless, more information about the language
to be learned does not lead to a new, and different hypothesis. Hence, some formof generalization must have taken place, i.e., of a grammar that accurately generates
the target language. The precise definitions of the concepts “evidence,” “stabilization,” and “accuracy” go back to Gold (1965, 1967) who introduced the model oflearning in the limit. Gold-style formal language learning has been intensively studied (cf., e.g., Angluin and Smith (1983, 1987), Osherson, Stob and Weinstein (1986)
and the references therein). For more information concerning recent developments in
inductive inference, the reader is referred to the annual Workshops on Computational
Learning Theory, COLT (cf., e.g., Rivest, Haussler and Warmuth (1989), Fulk andCase (1990), Haussler (1992)), the International Workshops on Algorithmic Learning
Theory, ALT (cf., e.g., Arikawa et al. (1990, 1991)) and the workshops on Analogicaland Inductive Inference, AII (cf., e.g., Jantke (1989, 1992)).
Most of the work done in the field has been aimed at two goals: the characterizationof those collections of languages that can be learned, and to study the impact ofseveral postulates on the behavior of learners to their learning power. Moreover, aconsiderable amount of interest has been devoted to the learnability of recursively
enumerable languages. In this particular setting many interesting and sometimes
surprising results have been obtained (cf., e.g., Wiehagen (1978), Case and Lynes(1982), Schäfer-Richter (1984), Case (1988), Jain and Sharma (1989) and Fulk (1990)).
The present paper surveys results that deal with the learnability of recursive languages. Looking at potential applications, Angluin (1980a, 1980b) started the systematic study of learning enumerable families of uniformly recursive languages, henceforthcalled indexed families. A sequence L0 , L1 , L2 , ... is said to be an indexed family provided all languages Lj are non-empty and membership in Lj is uniformly decidable
for all numbers j. Note that the definition of an indexed families includes both, adescription for every language Lj , and a particular enumeration of all the languages.
Well-known examples of indexed families are the set of all context sensitive languages
in canonical enumeration (cf. Hopcroft and Ullman (1969)) or the set of all patternlanguages in canonical enumeration (cf. Angluin (1980a)).
Next we specify the information from which the target languages have to be learned.
A text of a language L is an infinite sequence of strings that eventually contains
all strings of L. Alternatively, we consider learning from informant. An informant ofa language L is an infinite sequence of all strings over the underlying alphabet thatare classified with respect to their containment in L.
An algorithmic learner, henceforth called inductive inference machine (abbr. IIM),
takes as input initial segments of a text (an informant), and outputs, from time totime, a hypothesis about the target language. The set G of all admissible hypotheses2

is called hypothesis space. Furthermore, the sequence of hypotheses has to converge
to a hypothesis correctly describing the language to be learned, i.e., after some point,
the IIM stabilizes to an accurate hypothesis. If there is an IIM that learns a language
L from all texts (informants) for it, then L is said to be learnable from text (learnablefrom informant) in the limit with respect to the hypothesis space G (cf. Definition 1).

Having reached that point of precision a question naturally arising is how a “natural” learning algorithm may be designed. A thorough answer to this question, if
ever possible, requires a systematic study of the various aspects that might influence the learnability. Our guided tour aims to summarize results obtained in thisregard. We continue with some notations that are needed to motivate and to discussthese investigations. The starting point of our studies goes back to different learning
strategies that have been discussed controversially in the machine learning community. Clearly, whenever one learns inductively from examples one has to perform ageneralization. On the other hand, it is by no means obvious whether one should
generalize only as little as necessary or as much as possible. In the first case, thelearning algorithm might achieve the learning goal by producing a sequence of betterand better generalizations. The second approach might lead to an algorithm that
initially outputs a most general hypothesis. Afterwards, the learning algorithm might
specialize its actual hypotheses until it eventually reaches a correct guess. Finally, itis plausible to combine the two strategies, i.e., to learn by a suitable interplay between
generalization and specialization. There has been an extensive debate in the machinelearning community for and against each of these learning modes (cf., e.g., Michalski,
Carbonell and Mitchell (1984, 1986) or Kodratoff and Michalski (1990)). Inspiredby recent results in non-monotonic reasoning Jantke (1991a, 1991b) proposed several
sound formalizations of “generalization.” Moreover, he studied the problem to what
extend non-monotonic reasoning has to be incorporated into the learning process.
Subsequently, Wiehagen (1991) refined Jantke’s (1991a) approach, and Kapur (1992)
introduced the dual versions of it. This led to the following learning models:Interpreting generalization and specialization in their strongest sense means that
we are forced to produce an augmenting (descending) chain of languages, i.e., Li ⊆ Lj
(Li ⊇ Lj ) in case Lj is hypothesized later than Li (cf. Definitions 5 and 7, Part (A)).
The resulting learning types are called strong-monotonic and dual strong-monotonic
learning, respectively.
Subsequently, Wiehagen (1991) refined this definition by restricting “better generalization” to the language L that has to be learned, and required Li ∩ L ⊆ Lj ∩ Lprovided Lj appears later in the sequence of guesses than Li does (cf. Definition 5(B)). This means that a new hypothesis is never allowed to reject some string that apreviously generated guess already correctly includes.
The dual version of the latter requirement directly yields the demand that thelearner is never allowed to hypothesize a grammar that can generate a string thata previously guessed hypothesis correctly excluded (cf. Definition 7 (B)). Learning
devices behaving thus are called monotonic and dual monotonic, respectively.
Weakening the (dual) strong-monotonicity constraint in the same way as the monotonicity principle of classical logic is generalized to cumulativity (cf., e.g., Brewka(1991)) directly yields (dual) weak-monotonic learning, i.e., now the learner is required
to behave (dual) strong-monotonic as long as it does not receive data contradicting
3

its actual hypothesis (cf. Definitions 5 and 7, Part (C)).
Another serious problem one has to deal with when learning from text, is to avoid
or to detect overgeneralizations (also called the subset problem), i.e., hypotheses that
describe proper supersets of the target language. Several authors proposed the socalled subset principle to handle the subset problem (cf., e.g., Berwick (1985), Wexler(1992)). Informally, the subset principle requires the learner to guess the “least” language from the hypothesis space with respect to set inclusion that fits with the data
the learner has seen so far. Clearly, each of the monotonicity constraints describedabove can be regarded as a sound formalization of “least,” and therefore, as a realization of the subset principle. But there is another important aspect that we havenot touched yet, i.e., the choice of the hypothesis space. Obviously, the hypothesis
space must contain at least one description for each target language. Hence, we might
be tempted to take the indexed family itself as hypothesis space. And indeed, mostauthors did (cf. eg. Angluin (1980a, 1980b), Shinohara (1982), Jantke (1991b), Mukouchi (1992)). Moreover, looking at potential applications of a learning system, usersof such a system might even be highly interested in getting as hypotheses just thedescriptions they proposed. That means they might formulate their learning problems
just by specifying a particular indexed family. If an indexed family L can be learned
with respect to L itself, then we call it exactly learnable.

On the other hand, it is only natural to ask whether the requirement to learn
exactly may lead to a decrease of the learning power. Results obtained in the settingof PAC-learning impressively show that at least the efficiency of learning can beheavily affected if one insists to learn with respect to a particular hypothesis space(cf., e.g., Pitt and Valiant (1988), Blum and Singh (1990)). Similar effects have been
observed in Gold-style language learning, too (cf. Lange and Zeugmann (1993b)).
Therefore, we also consider the following options to choose a suitable hypothesis
space. An indexed family L is said to be class preservingly inferable, if there is ahypothesis space G = G0 , G1 , G2 , ... such that every grammar Gj generates a language
contained in L, and the learning algorithm infers L with respect to G. Note that
this in particular means that range(L) and {L(Gj ) j ∈ IN} have to coincide (INis the set of all natural numbers). That means, when dealing with class preserving
language learning we are free to choose a possibly different enumeration of L andpossibly different descriptions for the target languages L ∈ L. Or in other words,
class preserving learning just means that there is at least one suitable hypothesis
space having the same range as L with respect to which L is inferable.

Finally, we consider class comprising learning. In this setting a learning algorithm
is allowed to use any hypothesis space G = G0 , G1 , ... such that every L ∈ L possesses
a description Gj but G may additionally contain elements Gk not describing any language from L. Although we might be tempted to exclude class comprising hypothesis
spaces, since any grammar not generating a language from L cannot be correct, thislearning model has its peculiarities as we shall see.
Moreover, we study the question what all the described learning models have incommon and what their differences are. As we shall see, characterizations are a very
useful tool to answer this question (cf. Section 4). In particular, we outline a unifying
framework for learning from informant as well as from text.
Next we describe some further requirements that correspond to desirable properties4

a “natural” learning algorithm should have. For example, can we require an IIM to besemantically finite? An IIM is called semantically finite if the hypothesis it converges
to is the first correct one in the sequence of all its guesses. Again, this seems to bea very reasonable demand. As we have already mentioned, inductive learning has
its peculiarities. There has been a long debate in the philosophy of science for andagainst induction as a legitimate form of reasoning. As far as learning is concerned,
Poper’s (1968) falsification theory, and his refutation principle are of special interest.
While finite sequences of data can never prove a hypothesis to be correct, single
data can falsify it. Therefore, Popper (1968) considered induction as a legitimate
form of drawing conclusions as long as they are built up in such a way that theirrefutation is possible as long as they are wrong. Adapting that approach to learning
we directly arrive at semantical finite learners, since any wrong hypothesis is rejected
sometimes, and the sequence of all generated guesses stabilizes to the first correctone. Note that other authors have interpreted Poper’s (1968) refutation principle ina different, and much more restrictive way (cf., e.g., Case and Smith (1983), Gasarch
and Velauthapillai (1992)).
Furthermore, we deal with the question whether or not the order of information
presentation does really influence the capabilities of inductive inference machines.
Since an IIM is required to learn the target languages from all texts (informants),
one might conjecture that they just extract the strings provided. While this is true
for learning from informant, the situation with respect to text is completely different.
This phenomenon has been first observed by Schäfer-Richter (1984), and later independently by Fulk (1990). However, they proved their results in a setting allowing
self-referential arguments. Since self-referential arguments are mainly applicable insettings where the membership problem for languages is algorithmically undecidable,
it worth to study the problem of order independence in our more realistic setting.
Finally, we consider different aspects dealing with the efficiency of learning. Looking at the definition of learning in the limit, we see that in any learning step an IIM
has access to the whole initial segment of a text (informant) it has been fed. Clearly,
such a learning mode requires a huge amount of storage. Therefore, we consider iterative learning introduced by Wiehagen (1976). An iteratively learning IIM exclusively
uses its last hypothesis and the next input string to compute its actual guess (cf. Definition 8). Hence that model of learning takes into account the limitation of space inall realistic computations.
The second measure of efficiency we deal with is the number of mind changes an
IIM M is allowed to perform. We say that M changes its mind, or synonymously, M
performs a mind change iff two consecutively hypotheses output by M are different(cf. Definition 3). This measure of efficiency has been introduced by Barzdin and
Freivalds (1972). Subsequently, various authors used the number of mind changes
to characterize the complexity of learning (cf., e.g., Barzdin and Freivalds (1974),
Barzdin, Kinber and Podnieks (1974), Case and Smith (1983), Wiehagen, Freivalds
and Kinber (1984), Mukouchi (1992, 1994)). Gasarch and Velauthapillai (1992) studied active learning in dependence on the number of mind changes.
The paper is organized as follows. Section 2 presents preliminaries, i.e., notations
and definitions. In Section 3 we exemplify several basic concepts and ideas of language learning. We continue with characterizations of the learning models introduced5

(cf. Section 4). Then, we survey results showing that the learnability of indexedfamilies is sensitive with respect to an appropriate choice of the relevant hypothesis
space (cf. Section 5). Fundamental results concerning iterative learning are outlined
in Section 6. Subsequently, we present results dealing with the efficiency of learning
measured in the number of allowed mind changes (cf. Section 7). A comprehensive
summary of recently obtained results dealing with different degrees of order independence is provided in Section 8. Finally, we discuss problems that remain open andoutline further questions that might lead to interesting results (cf. Section 9). All
references are given in Section 10.

2. Preliminaries
Let IN = {0, 1, 2, ...} be the set of all natural numbers. We set IN+ = IN \ {0}. Let
ϕ0 , ϕ1 , ϕ2 , ... denote any fixed programming system of all (and only all) partial
recursive functions over IN, and let Φ0 , Φ1 , Φ2 , ... be any associated complexity
measure (cf. Machtey and Young (1978)). Then ϕk is the partial recursive function
computed by program k in the programming system. Furthermore, let k, x ∈ IN. If
ϕk (x) is defined (abbr. ϕk (x) ↓) then we also say that ϕk (x) converges; otherwise,
ϕk (x) diverges (abbr. ϕk (x) ↑). By h·, ·i: IN × IN → IN we denote Cantor’s pairing
function, i.e., hx, yi = ((x + y)2 + 3x + y)/2 for all x, y ∈ IN. In the sequel we assume
familiarity with formal language theory (cf., e.g., Hopcroft and Ullman (1969)). By
Σ we denote any fixed finite alphabet of symbols. Let Σ∗ be the free monoid overΣ, and let Σ+ = Σ∗ \ {ε}, where ε denotes the empty string. The length of a strings ∈ Σ∗ is denoted by |s|. Any subset L ⊆ Σ∗ is called a language. By co−L we denotethe complement of L, i.e., co−L = Σ∗ \ L. Let L be a language and t = s0 , s1 , s2 , ...
an infinite sequence of strings from Σ∗ such that range(t) = {sk k ∈ IN} = L. Thent is said to be a text for L or, synonymously, a positive presentation. Let L be alanguage. By text(L) we denote the set of all positive presentations of L. Furthermore,
let i = (s0 , b0 ), (s1 , b1 ), ... be an infinite sequence of elements of Σ∗ × {+, −} suchthat range(i) = {sk k ∈ IN} = Σ∗ , i+ = {sk (sk , bk ) = (sk , +), k ∈ IN} = L
and i− = {sk (sk , bk ) = (sk , −), k ∈ IN} = co − L. Then we refer to i as an
informant. If L is classified via an informant then we also say that L is represented
by positive and negative data. Let L be a language. By info(L) we denote theset of all informants for L. Moreover, let t, i be a text and an informant, respectively,
and let x be a number. Then tx , ix denote the initial segment of t and i of lengthx + 1, respectively, e.g., i2 = (s0 , b0 ), (s1 , b1 ), (s2 , b2 ). Let t be a text and let x ∈ IN.
−+
Then we define t+
x = {sk k ≤ x}. Furthermore, by ix and ix we denote the sets{sk (sk , +) ∈ i, k ≤ x} and {sk (sk , −) ∈ i, k ≤ x}, respectively. Finally, we write
tx v ty (tx < ty ), iff tx is a (proper) prefix of ty .
Next we introduce the notion of the canonical text that will be very helpfulin proving several theorems. Let L be any non-empty recursive language, and let
s0 , s1 , ... be the lexicographically ordered text of Σ∗ . Test sequentially whether sz ∈ L,
for z = 0, 1, 2, ..., until the first z is found such that sz ∈ L. Since L 6= ∅, there mustbe at least one z fulfilling the test. Set t0 = sz . We proceed inductively, x ≥ 0,(tx · sz+x+1 ,if sz+x+1 ∈ L,
tx+1 =
tx · s,otherwise, where s is the last string in tx .
6

Following Angluin (1980b), we restrict ourselves to deal exclusively with indexedfamilies of uniformly recursive languages defined as follows: A sequence L0 , L1 , L2 , ...
is said to be an indexed family L of uniformly recursive languages provided all Lj
are non-empty and there is a recursive function f such that for all numbers j and all
strings s ∈ Σ∗ we have
1,
if s ∈ Lj ,f (j, s) =0,otherwise.

In the following we refer to indexed families of uniformly recursive languages as indexed families for short. Moreover, we sometimes denote an indexed family and its
range by the same symbol L. The meaning will be clear from the context.

As in Gold (1967), we define an inductive inference machine (abbr. IIM) to
be an algorithmic device which works as follows: The IIM takes as its input larger andlarger initial segments of a text t (or an informant i) and it either requests the next
input, or it first outputs a hypothesis, i.e., a number encoding a certain computer
program, and then it requests the next input (cf., e.g., Angluin (1980b)).

At this point we have to clarify what space of hypotheses we should choose, thereby
also specifying the goal of the learning process. Gold (1967) and Wiehagen (1977)
pointed out that there is a difference in what can be inferred depending on whether
we want to synthesize in the limit grammars (i.e., procedures generating languages) or
decision procedures, i.e., programs of characteristic functions. Case and Lynes (1982)
investigated this phenomenon in detail. As it turns out, IIMs synthesizing grammars
can be more powerful than those ones which are requested to output decision procedures. However, in the context of identification of indexed families, both concepts areof equal power. Nevertheless, we decided to require the IIMs to output grammars.
This decision has been caused by the fact that there is a big difference between thepossible monotonicity requirements. A straightforward adaptation of the approaches
made in inductive inference of recursive functions directly yields analogous requirements with respect to the corresponding characteristic functions of the languages to beinferred. On the other hand, it is only natural to interpret monotonicity with respect
to the language to be learned, i.e., to require containment of languages as describedin the introduction. It turns out that the latter approach considerably increases thepower of all types of monotonic and dual monotonic language learning. Furthermore,since we exclusively deal with the learnability of indexed families L = (Lj )j∈IN wealways take as hypothesis space an enumerable family of grammars G = G0 , G1 , G2 , ...
over the terminal alphabet Σ satisfying L ⊆ {L(Gj ) j ∈ IN}. Moreover, we requirethat membership in L(Gj ) is uniformly decidable for all j ∈ IN and all strings s ∈ Σ∗ .
As it turns out, it is sometimes very important to choose the space of hypotheses
appropriately in order to achieve the desired learning goal (cf., e.g., Section 5 and
8). When an IIM outputs a number j, we interpret it to mean that the machine
is hypothesizing the grammar Gj . Furthermore, let G = (Gj )j∈IN be any hypothesis
space. Then we set L(G) = {L(Gj ) j ∈ IN}. Note that L(G) constitutes itself anindexed family for all hypothesis spaces G = (Gj )j∈IN .

Let σ be a text or informant, respectively, and x ∈ IN. Then we use M (σx ) todenote the last hypothesis produced by M when successively fed σx . The sequence(M (σx ))x∈IN is said to converge in the limit to the number j if and only if either (M (σx ))x∈IN is infinite and all but finitely many terms of it are equal to j, or7(M (σx ))x∈IN is non-empty and finite, and its last term is j. Now we are ready todefine learning in the limit.
Definition 1. (Gold, 1967) Let L be an indexed family, let L be a language,and let G = (Gj )j∈IN be a hypothesis space. An IIM M CLIM–TXT [CLIM–
INF ]–identifies L from text [ informant ] with respect to G iff for every
text t [informant i ] for L, there exists a j ∈ IN such that the sequence (M (tx ))x∈IN[(M (ix ))x∈IN ] converges in the limit to j and L = L(Gj ).
Furthermore, M CLIM −T XT [CLIM −IN F ]–identifies L with respect to G iff,
for each L ∈ L, M CLIM −T XT [CLIM −IN F ]–identifies L with respect to G.
Finally, let CLIM − T XT [CLIM − IN F ] denote the collection of all indexedfamilies L for which there are an IIM M and a hypothesis space G such that M
CLIM −T XT [CLIM −IN F ]–identifies L with respect to G.

Since, by the definition of convergence, only finitely many data of L were seen by
the IIM upto the (unknown) point of convergence, whenever an IIM identifies thelanguage L, some form of learning must have taken place. For this reason, hereinafter
the terms infer, learn, and identify are used interchangeably.

In the above Definition LIM stands for “limit.” Furthermore, the prefix C is used
to indicate class comprising learning, i.e., the fact that L may be learned withrespect to some hypothesis space comprising range(L). The restriction of CLIM toclass preserving inference is denoted by LIM . That means LIM is the collectionof all indexed families L that can be learned in the limit with respect to a hypothesis
space G = (Gj )j∈IN such that range(L) = {L(Gj ) j ∈ IN}. Moreover, if a target
indexed family L has to be inferred with respect to the hypothesis space L itself, thenwe replace the prefix C by E, i.e., ELIM is the collection of indexed families thatcan be exactly learned in the limit. Finally, we adopt this convention in defining all
the learning types below.
Note that, in general, it is not decidable whether or not M has already inferred
L. With the next definition, we consider a special case where it has to be decidable
whether or not an IIM has successfully finished the learning task.
Definition 2. (Gold, 1967; Trakhtenbrot and Barzdin, 1970) Let L be anindexed family, let L be a language, and let G = (Gj )j∈IN be a hypothesis space. An
IIM M CFIN–TXT [CFIN–INF ]–identifies L from text [informant ] withrespect to G iff for every text t [informant i ] for L, there exists a j ∈ IN such that
M, when successively fed t [ i ], outputs the single hypothesis j, L = L(G j ), and stops
thereafter.
Furthermore, M CF IN −T XT [ CF IN −IN F ]–identifies L with respect to G iff,
for each L ∈ L, M CF IN −T XT [ CF IN −IN F ]–identifies L with respect to G.
The resulting learning type is denoted by CF IN −T XT[CF IN −IN F ].

The next definition shows a natural way of weakening the requirement of finite
identification. Here, the number of mind changes which an IIM M may perform wheninferring a target language is bounded by a number a priori fixed. When dealing withmind changes it is technically much more convenient to require the IIMs to behave as
follows. Let t be any text (i be any informant), and x ∈ IN. If M on tx (ix ) outputs
for the first time a guess, then it has to output at any subsequent step a hypothesis.
It is easy to see that any IIM M may be straightforwardly converted into an IIM M̂
8behaving as required such that both machines produce the same sequence of mindchanges.
Definition 3. (Barzdin and Freivalds, 1974) Let L be an indexed family,
let L be a language, and let G = (Gj )j∈IN be a hypothesis space, k ∈ IN ∪ {∗}. An
IIM CLIMk –TXT [CLIMk –INF ]–identifies L from text [informant ] withrespect to G iff(1) M CLIM − T XT
respect to G,[CLIM − IN F ]–identifies L from text [informant ] with

(2) for every text t [informant i ] for L the IIM M performs, when fed t [i], at mostk (k = ∗ means at most finitely many) mind changes, i.e., card({x | M (tx ) 6=
M (tx+1 )}) ≤ k [card({x | M (ix ) 6= M (ix+1 )}) ≤ k ].
Moreover, M CLIMk −T XT [ CLIMk −IN F ]–identifies L with respect to G iff, foreach L ∈ L, M CLIMk −T XT [ CLIMk −IN F ]–identifies L with respect to G.
CLIMk −T XT and CLIMk −IN F are defined in the same way as above.

Obviously, λF IN −T XT = λLIM0 −T XT and λF IN −IN F = λLIM0 −IN F for
all λ ∈ {E, ε, C}. Moreover, it is easy to see that λLIM∗ −T XT = λLIM −T XT as
well as λLIM∗ −IN F = λLIM −IN F for all λ ∈ {E, ε, C}.

Next, we want to formally define strong-monotonic, monotonic and weak-monotonic inference. But before doing this, we first define consistent identification. Consistent learning devices have been introduced by Barzdin (1974). Intuitively, consistency
means that the IIM has to correctly reflect the information it has already been fed.

Definition 4. (Barzdin, 1974) Let L be an indexed family, let L be a language,and let G = (Gj )j∈IN be a hypothesis space. An IIM M CCONS–TXT [CCONS–INF ]–identifies L from text [informant ] with respect to G iff(1) M CLIM − T XT
respect to G,[CLIM − IN F ]–identifies L from text [informant ] with

(2) for every text t [informant i ] for L the following condition is satisfied:+
whenever M on tx [on ix ] produces a hypothesis jx , then t+x ⊆ L(Gjx ) [ix ⊆−L(Gjx ) and ix ⊆ co−L(Gjx )].
Moreover, M CCON S−T XT [CCON S−IN F ]–identifies L with respect to G iff, foreach L ∈ L, M CCON S −T XT [CCON S −IN F ]–identifies L with respect to G.
CCON S −T XT and CCON S −IN F are analogously defined as above.

Now we are ready to formally define the three types of monotonic language learning
introduced in Section 1.
Definition 5. (Jantke, 1991a; Wiehagen, 1991) Let L be a language, and let
G = (Gj )j∈IN be a hypothesis space. An IIM M is said to identify the language
L from text [informant ] with respect to G(A) strong-monotonically(B) monotonically(C) weak-monotonically9iff
M CLIM − T XT [CLIM − IN F ]–identifies L with respect to G and for every
text t [informant i] of L as well as for any two consecutive hypotheses j x , jx+k which
M has produced when fed tx and tx+k [ix and ix+k ], where k ≥ 1, k ∈ IN, the following
conditions are satisfied:(A) L(Gjx ) ⊆ L(Gjx+k )(B) L(Gjx ) ∩ L ⊆ L(Gjx+k ) ∩ L+−(C) if t+
x+k ⊆ L(Gjx ), then L(Gjx ) ⊆ L(Gjx+k ) [if ix+k ⊆ L(Gjx ) and ix+k ⊆ co −L(Gjx ), then L(Gjx ) ⊆ L(Gjx+k )].

In particular, requirement (C) means that M behaves strong-monotonically as longas its guess jx is consistent with all the data fed to M both before and after M has
output jx .
We denote by CSM ON −T XT, CSM ON −IN F, CM ON −T XT, CM ON −IN F ,CWM ON −T XT , CWM ON −IN F the collection of all those indexed families L for
which there are a hypothesis space G and an IIM inferring them strong-monotonically,
monotonically, and weak-monotonically from text or informant with respect to G,
respectively.
With the following figure we summarize the known results concerning monotonic
language learning (cf. Lange and Zeugmann (1992, 1993a)). We restrict ourselves tothe class preserving case, since this case already reflects the characteristic relations
between the monotonic learning models defined above. Each learning type is represented as a vertex in a directed graph. A directed edge from vertex A to vertex B
indicates that A is a proper subset of B, a bidirectional edge represents A = B, andno edge between vertices not connected by a directed path implies that A and B are
incomparable.
Monotonic Learning from Text versus Monotonic Learningfrom Informant- SMON–INF- MON–INF- WMON–INF  - LIM–INF
XXX
*

6
6
Y
HH
6
 6
*
*
6
XX *

HH 
X
XX


XXX 
H



H


XXXX

HH




XX



H
z
X
- SMON–TXT - MON–TXT- WMON–TXT- LIM–TXT
FIN–TXTFIN–INF

Figure 1
Next, we define conservative IIMs. Intuitively speaking, conservative IIMs maintain their actual hypothesis at least as long as they have not seen data contradicting
it. Hence, whenever a conservative IIM performs a mind change it is because it hasperceived clear inconsistency between its guess and the input.
Definition 6. (Angluin, 1980b) Let L be an indexed family, let L be a language,and let G = (Gj )j∈IN be a hypothesis space. An IIM M CCONSERVATIVE–
TXT [CCONSERVATIVE–INF ]–identifies L from text [informant ] withrespect to G iff
10(1) M CLIM −T XT[CLIM −IN F ]–identifies L with respect to G,(2) for every text t [informant i ] for L the following condition is satisfied:
whenever M on input tx [on ix ] makes the guess jx and then makes the guess
jx+k 6= jx at some subsequent step, then L(Gjx ) must fail to contain some string+from t+x+k [L(Gjx ) must either fail to contain some string s ∈ ix+k or it generates−
some string s ∈ ix+k ].
Finally, M CCONSERVATIVE–TXT [CCONSERVATIVE–INF ]–identifies Lwith respect to G if and only if, for each L ∈ L, M CCONSERVATIVE–TXT [CCONSERVATIVE–INF ]–identifies L with respect to G.
The collection of sets CCONSERVATIVE–TXT and CCONSERVATIVE–INF aredefined in a manner analogous to that above.

Note that λWM ON−T XT = λCONSERVATIVE–TXT as well as λWM ON−IN F= λCONSERVATIVE–INF for all λ ∈ {C, ε, E} (cf. Lange and Zeugmann (1993a)).
Hence, looking at Figure 1 we may conclude that conservative IIMs are less powerfulthan unrestricted IIMs, in case one deals with the inferability of indexed families.
Note that the latter assertion is not true if one deals with the learnability of arbitrary
recursively enumerable languages (cf. Osherson, Stob and Weinstein (1986), pp. 75).
We continue in formally defining the three types of dual monotonic language learning introduced in Section 1.
Definition 7. (Kapur, 1992) Let L be a language, and let G = (Gj )j∈IN bea hypothesis space. An IIM M is said to identify a language L from text
[informant ] with respect to G(A) dual strong-monotonically(B) dual monotonically(C) dual weak-monotonicallyiff
M CLIM −T XT [CLIM −IN F ]–identifies L with respect to G and for any text
t [informant i] of L as well as for any two consecutive hypotheses jx , jx+k which M
has produced when fed tx and tx+k [ix and ix+k ], for some k ≥ 1, k ∈ IN, the following
conditions are satisfied:(A) co−L(Gjx ) ⊆ co−L(Gjx+k )(B) co−L(Gjx ) ∩ co−L ⊆ co−L(Gjx+k ) ∩ co−L−+(C) if t+
x+k ⊆ L(Gjx ), then co−L(Gjx ) ⊆ co−L(Gjx+k ) [if ix+k ⊆ L(Gjx ) and ix+k ⊆co−L(Gjx ), then co−L(Gjx ) ⊆ co−L(Gjx+k )].

By CSM ON d−T XT , CSM ON d−IN F , CM ON d−T XT , CM ON d−IN F , CWM ON d−
T XT , and CWM ON d − IN F we denote the collections of all those indexed families L for which there are a hypothesis space G and an IIM identifying them dual
strong-monotonically, dual monotonically and dual weak-monotonically from text andinformant with respect to G, respectively.
11

The next figure shows the relations between the defined modes of class preserving
dual monotonic inference (cf. Lange, Zeugmann and Kapur (1992), and Lange andZeugmann (1994)). The semantics of Figure 2 is analogous to that of Figure 1. On
comparing with Figure 1, the similarities as well as the differences between the various
types of monotonic and dual monotonic inference are clearly illustrated.
Dual Monotonic Learning from Text versus Dual Monotonic
Inference from Informant- SMONd –INF - MONd –INF - WMONd –INF  - LIM–INF
H
*

*
Y
*

6
*
 6
 6HH
 6

HH
HH





 HH

 HH


HH
HH 



d
d
d

FIN–TXTSMON –TXT
MON –TXTWMON –TXT
LIM–TXTFIN–INF

Y
H
6HH

Figure 2
Note that the notions of monotonicity and of dual monotonicity are truly duals ofeach other.
Finally, we define iterative IIMs. An iterative IIM is only allowed to use its lastguess and the next string of the text and informant, respectively, of the language it
is supposed to learn. Conceptionally, an iterative IIM M defines a sequence (Mn )n∈Nof machines each of which takes as its input the output of its predecessor. Hence, theIIM M has always to produce a hypothesis.
Definition 8. (Wiehagen, 1976) Let L be an indexed family, let L be a language,and let G = (Gj )j∈IN be a hypothesis space. An IIM M CIT–TXT [CIT–INF ]–identifies L from text [informant ] with respect to G iff for every text t =(sj )j∈IN [informant i = ((wj , bj ))j∈IN ] the following conditions are satisfied:(1) for all n ∈ IN, Mn (t) [Mn (i) ] is defined, where M0 (t) =df M (s0 ) [M0 (i) =df
M ((w0 , b0 )) ] and for all n ≥ 0: Mn+1 (t) =df M (Mn (t), sn+1 ) [Mn+1 (i) =df
M (Mn (i), (wn+1 , bn+1 )) ],(2) the sequence (Mn (t))n∈IN [(Mn (i))n∈IN ] converges in the limit to a number j suchthat L = L(Gj ).
Finally, M CIT − T XT [CIT − IN F ]–identifies L with respect to G iff, for eachL ∈ L, M CIT −T XT [CIT −IN F ]–identifies L with respect to G.

The resulting identification types CIT − T XT and CIT − IN F are analogously
defined as above.
The combination of iterative and monotonic inference is denoted by λM ON−IT −T XT (λM ON −IT −IN F ), where λ ∈ {S, W, ε}.

The next section starts our guided tour across the boundaries of learning recursive
languages. We begin with several examples pointing to typical problems, ideas, andsolutions in the field.

123. Examples
One of the first discovered learning algorithms has been identification by enumeration (cf. Solomonoff (1964), Gold (1965)). Nowadays, this learning algorithm is usuallyreferred to as Gold’s identification by enumeration principle. The main idea behind
this algorithm is as follows. Choose a suitable enumeration of all the objects to belearned. Then, after having seen the data d0 , ..., dx , search for the first enumerated
object that is consistent with the data read so far. However, at first glance it seemedthat this learning procedure has a severely restricted domain of applicability, at least
as long as its effective computability is required. Clearly, as it stands, its effective
computability can only be assured as long as the corresponding consistency problem
remains effectively decidable. Moreover, it turned out that consistency itself constitutes a severe restriction of learnability (cf. e.g. Wiehagen and Zeugmann (1994),
and the references therein). Nevertheless, suitable modifications of the identification
by enumeration principle have been discovered that turned out to be very powerful.
Nowadays, for the setting of inductive inference of recursive functions the following
thesis is widely accepted (cf. Wiehagen (1991), pp. 184):“Any class of recursive functions which is identifiable at all can always be identified
by an enumeratively working learning device. Moreover, the identification canalways be realized with respect to a suitable non-standard (i.e., non-Gödel) numberingof the target class of functions.”
Thus, the question arises whether or not enumeratively working IIMs are of thesame importance in language learning, too.
We start our guided tour with a series of examples pointing to major problems
in answering the latter question. Furthermore, we exemplify fundamental ideas thathave been developed to handle the arising difficulties. Thereby we restrict ourselvesto the learnability of indexed families. Let us start with the easiest case, i.e., with thelearnability of indexed families from positive and negative data. Inference from informant may be understood, at least conceptually, as inductive inference of enumerable
classes of recursive predicates. Therefore, it is easy to see that Gold’s (1967) identification by enumeration principle serves as a universal learning method. Moreover, we
may even use any hypothesis space comprising all the target languages. In particular,
successful inference can be always achieved, if we choose the target indexed family
itself as the underlying hypothesis space. For the sake of completeness, let us continue
with the definition of an IIM that realizes the identification by enumeration principle.
Let L be any indexed family, L ∈ L, let i ∈ info(L), and x ∈ IN. The wanted IIM
M works as follows. When fed ix it searches for the least index j satisfying i+x ⊆ Lj−and ix ∩ Lj = ∅, i.e., the first enumerated language that is consistent with all dataread so far. Then, M outputs the hypothesis j.
Some remarks are mandatory. Since membership is uniformly decidable for all languages enumerated in L, the consistency test can be effectively performed. Moreover,since i ∈ info(L) and L ∈ L, the described search has to terminate. Hence, M isindeed an IIM. Furthermore, M converges to the least number j satisfying L = Lj ,and performs at most j mind changes. But still, this is not the whole story. The described IIM M possesses some further advantages that we are going to describe. First,
any mind change performed by M is justified by a “provable misclassification” of its
13

previous guess. Therefore, M will never reject a guess that is correct for the language
to be learned. Hence, M is semantical finite. Second, M is set-driven, too, i.e., its
output exclusively depends on the range of its input. Next, identification by enumeration is the most efficient learning method with respect to learning time, i.e., the firsttime such that M outputs a correct guess that will be repeated in every subsequent
learning step (cf. Gold (1967)). More precisely, Gold proved that there is no IIM M̂
inferring L which is uniformly faster than the IIM M described above with respect
to learning time. Hence, in the setting of learning indexed families identification by
enumeration is particularly tailored for learning from informant.
However, the situation remarkably changes when learning from positive data isconcerned. There are several reasons for that phenomenon. The first one is a topological one, and has been discovered by Gold (1967). In particular, he proved thefollowing theorem.
Proposition 1. (Gold, 1967) Let L be any class of languages containing all
finite languages and at least one infinite language. Then L ∈/ CLIM −T XT .

Note that Proposition 1 remains true, even in case one restricts itself to learningfrom recursive text (cf. Gold (1967)). Moreover, a closer look to Gold’s proof directly
implies that even quite simple indexed families are not identifiable from text as our
first example shows.
Example 1. Nonlearnability of simple indexed families
Consider the following indexed family L = (Lj )j∈IN where L0 = {a}+ and Lj ={am 1 ≤ m ≤ j} for all j ∈ IN+ . We show that L is not learnable in the limit
from positive data. Suppose the converse, i.e., there is an IIM M which witnesses
L ∈ ELIM − T XT . Then, M in particular has to identify the language L1 on its
uniquely defined text t. Hence, there exists an x ∈ IN such that M (tx ) = 1. Obviously,
it is possible to extend tx in order to obtain a text for the infinite language L0 . Namely,
we may choose the text tx · t̂ where t̂ is the lexicographically ordered text of L0 . Since
M has to infer L0 from this text, too, M is forced to change its mind to the hypothesis
0. Therefore, there is a y ∈ IN+ such that M (tx · t̂y ) = 0. But now we may conclude
that tx · t̂y is an initial segment of a text t̃ for the finite language Ly . Consequently,
M has to perform one more mind change when successively fed t̃. By iterating thisidea one may effectively construct a text for the infinite language L0 on which M has
to change its mind infinitely often, a contradiction. Hence L ∈/ ELIM −T XT . As weshall see later (cf. Section 5, Theorem 11), this result implies that L is not learnable
at all in the limit, i.e., L ∈/ CLIM −T XT .
3This negative result is mainly caused by the problem that both finite and infinite
languages have to be simultaneously handled. Moreover, Proposition 1 as well as our
example do not only point to a weakness of identification by enumeration but to aserious weakness of learning from text. Hence, it is still imaginable that identification
by enumeration remains a universal learning method provided the target indexedfamily is learnable in the limit from positive data. Our next example shows that thesituation is much more subtle than one might expect.
Example 2. The weakness of identification by enumeration
Consider the following indexed family L = (Lj )j∈IN where L0 = {a}+ and Lj = {aj }for all j ∈ IN+ . An IIM M̂ which conservatively infers L may be designed as follows.
14

As long as a text for a singleton language, say Lj , is presented, M̂ outputs just theguess j. If at least two different strings appear, M̂ changes its mind to its final guess
0. Thus, on the one hand, L ∈ ELIM −T XT .

But on the other hand, any IIM M realizing the identification by enumeration
principle cannot infer L from positive data. To see this, suppose the converse, i.e.,there is such an IIM M inferring L with respect to any class comprising hypothesis
space G. Hence, there is a least index z ∈ IN such that L0 = L(Gz ). Therefore, there
has to be a singleton language L satisfying L(Gk ) 6= L for all k ≤ z. Since L ⊆ L(Gz ),M will never output a hypothesis j > z when fed a text for L. Thus, M fails to infer
the singleton language L.
3
The indexed family L from the above example contains a language L as well as
infinitely many proper sublanguages of L. A constellation like this always implies
that identification by enumeration fails to learn the corresponding target indexedfamily from text. As mentioned above, when learning from informant is consideredidentification by enumeration is insensible to the choice of the hypothesis space aslong as learnability at all is concerned. Our next example shows that this is no longer
the case when learning from positive data is considered.
Example 3. Sensibility of identification by enumeration with respect tothe hypothesis space
Consider the indexed family L = (Lj )j∈IN where L0 = {a}+ and Lj = {a} for allj ∈ IN+ . Again, identification by enumeration fails when L is selected as hypothesis
space. On the other hand, identification by enumeration yields successful inference, if
a hypothesis space G = (Gj )j∈IN is chosen such that L(G0 ) = {a} and L(Gj ) = {a}+for all j ∈ IN+ .
3

Taking the above examples into consideration, the question arises whether or not
identification by enumeration may be suitably modified for language learning frompositive data. The crucial point is how overgeneralization may be avoided or, in caseovergeneralization is inevitable, how the resulting problems may be handled. Furthermore, it would be interesting to know if all, or at least some, of the useful properties
of identification by enumeration can be maintained. After Gold’s (1967) pioneering
paper these problems faced more than a decade of decline. Proposition 1 had been
misinterpreted. Namely, many authors concluded that there is no interesting classof languages at all that can be learned from positive data, and hence, there is noneed to study the question mentioned above. The breakthrough has been provided
by Angluin (1980a) who showed that there are very interesting languages that can beinferred from text, for example the class of all pattern languages. Subsequently, thelearnability of pattern languages has been intensively studied within different learning models (cf. e.g. Shinohara (1982), Kearns and Pitt (1989), Lange and Wiehagen(1991)). Besides that, pattern languages form the basis of applications in different
fields, e.g. in the “intelligent” text processing system EBE (cf. Nix (1983)) or in aclassification system for transmembrane proteins (cf. Arikawa et. al (1992)). So let us
have a closer look to them.
Example 4. The pattern languages

Let Σ = {a, b, ..} be any non-empty finite alphabet containing at least two letters.
Furthermore, let X = {x0 , x1 , x2 , ...} be an infinite set of variables such that Σ∩X = ∅.
15

Patterns are non-empty strings from Σ ∪ X, e.g., ab, ax1 ccc, bx1 x1 cx2 x2 are patterns.
If p is a pattern, then L(p), the language generated by pattern p, is the set of strings
which can be obtained by substituting non-null strings si ∈ Σ∗ for each occurrenceof the variable xi in the pattern p. Thus aabbb is generable from pattern ax1 x2 b,
while aabba is not. From a practical point of view it is highly desirable to choose thehypothesis space as small as possible. For that purpose we use the canonical form of
patterns (cf. Angluin (1980a)). A pattern p is in canonical form provided that if k is
the number of variables in p, then the variables occurring in p are precisely x0 , ..., xk−1 .
Moreover, for every j with 0 ≤ j < k − 1, the leftmost occurrence of xj in p is to theleft of the leftmost occurrence of xj+1 in p. If a pattern p is in canonical form thenwe refer to p as a canonical pattern. Let Patc denote the set of all canonical patterns.
Clearly, for every pattern p there exists a unique q ∈ Patc such that L(p) = L(q).
Finally, choose any repetition free effective enumeration p0 , p1 , ... of Patc and define
PAT = (L(pj ))j∈IN . Then PAT establishes an indexed family (cf. Angluin (1980a)).
In the sequel, we discuss the learnability of the family PAT from different perspectives. Thereby, we are mainly interested in principal solutions. Technicalities aresuppressed as much as possible.
First, we summarize some characteristic features of pattern languages. From theabove definition it immediately follows that given any two patterns p and q it isdecidable whether or not L(p) = L(q). Furthermore, let Tp = {w w ∈ L(p), |w| =|p|} for every pattern p ∈ Patc. Then, every pattern language L(p) is uniquely
characterized by its finite subset Tp as the following proposition shows.
Proposition 2. (Angluin, 1980a) Let p, q be any patterns. Then we have:(1) L(p) = L(q) iff Tp ⊆ L(q) and Tq ⊆ L(p),(2) Tp ⊆ L(q) implies ¬ L(q) ⊂ L(p).

Let S denote any finite set of strings. A pattern p is said to be descriptive for
S provided that S ⊆ L(p) and there does not exists any pattern q satisfying S ⊆L(q) ⊂ L(p). Therefore, any IIM M which exclusively outputs descriptive patterns
as hypotheses realizes the subset principle, i.e., it never generates an overgeneralized
hypothesis. The sets Tp , henceforth called tell-tale sets, can be effectively computed,
if p is given. Hence, tell-tale sets may guide a learning device to avoid the problem ofovergeneralization.
Based on this idea, the following IIM conservatively infers PAT with respect tothe hypothesis space PAT . Assume that any initial segment tx of any text t for any
pattern language L(q) is presented. Initially, M searches for all indices j ≤ x suchthat t+x ⊆ L(pj ). Among these candidate hypotheses, M chooses the least j satisfying
T pj ⊆ t +x , if such an index exists. Because of Assertion (2), pj is descriptive for the set+
Tpj . Since Tpj ⊆ t+x ⊆ L(pj ), pj is descriptive for the set tx , too. Thus, M has seen
enough evidence to output just the hypothesis j. M does not change the hypothesis
j as long as it is consistent. If j turns out to be inconsistent then M again starts thesame search as explained above. Now, taking Proposition 2 into account, it is easy
to see that M converges on t. Moreover, since M never outputs an overgeneralized
hypothesis, M learns L(q) from text. Thus, we have the following theorem.
Theorem 1. PAT ∈ ECONSERVATIVE −TXT .
16

The IIM M explained above works enumeratively, too. But, M ’s search within
the hypothesis space does not only aim to find any consistent hypothesis. Instead, M
does not output any hypothesis until it has collected enough evidence. It measuresthe evidence obtained with respect to the relevant tell-tale sets. If at least one tell-taleset is completely contained in the range of its input M creates a suitable subspace ofcandidate hypotheses, i.e., the set of all those patterns p satisfying Tp ⊆ t+
x . Thenit searches the first consistent hypothesis, say p, and outputs it. If p is not a correct
guess, Assertion (2) of Proposition 2 guarantees that data contradicting it have toappear.
As we have seen, there is some hope to suitably modify identification by enumeration for learning from positive data. Moreover, for the particular case of patternlanguages the tell-tale sets are the main ingredient to solve the subset problem. Consequently, it is only natural to ask whether or not the approach outlined above may
be generalized. This is indeed the case as we shall see below. But before dealing withpossible generalizations we provide some more information concerning the learnability of pattern languages. First, we ask whether Theorem 1 may be strengthened, forexample to PAT ∈ SM ON −T XT . Recently, it has been shown that the inclusion
problem for pattern languages is undecidable. This implies the following result (cf.
Zeugmann, Lange and Kapur (1995) for a detailed discussion).
Theorem 2. PAT 6∈ MON −TXT .

Hence, Theorem 1 cannot be improved with respect to class preserving learning.
On the other hand, the pattern languages possess another favorable property, namely
they are iteratively learnable (cf. Lange and Wiehagen (1991)).
Theorem 3. PAT ∈ EIT −TXT .

The basic idea may be described as follows. Ignore for a moment that the desired
IIM has to be iterative. As we have already seen, every pattern language is uniquely
characterized by the set of all its minimal strings. This observation is the main
ingredient to the following IIM M . At each learning step, M first determines the set
S of all minimal strings it has been fed so far. All other strings will be simply ignored.
Then, M generates a pattern pj that is descriptive for S. Thus, M outputs in every
step a hypothesis j which is consistent with all the shortest strings seen so far. Now,
another property of pj comes into the play. Namely, M can effectively reproduce all
information it has used to compute pj from pj . Therefore, when fed its last guess aswell as the next input string, it can effectively decide whether or not it has to performa mind change. This is the gist underlying the construction in Lange and Wiehagen(1991). We omit the details.
Furthermore, their result has some special features. They have shown that the IIM
they actually use runs in time polynomial in the length of the input, since it totally
avoids to test membership. The price paid is that it sometimes outputs inconsistenthypotheses. For a more detailed discussion concerning the consistent versus inconsistent learnability of the pattern languages the reader is referred to Wiehagen and
Zeugmann (1994).
3
Reviewing the results discussed so far the questions arises whether or not any
indexed family learnable from text can be inferred by a conservative IIM or even by
an iterative one. In each case, the answer is negative (cf. Lange and Zeugmann (1992),
17

(1993c)).
Theorem 4.
(1) CCONSERVATIVE −TXT ⊂ ELIM −T XT(2) CIT −T XT ⊂ ELIM −T XTAssertion (1) proves that overgeneralization is inevitable, in general, if one considers language learning from positive examples. In order to show a particular way tosolve the subset problem, we discuss the relation between conservative learners andlearning in the limit in some more detail. In Angluin’s pioneering paper (cf. Angluin(1980b)) the following characterization of those indexed families for which learning in
the limit from positive data is possible has been shown.
Proposition 3. (Angluin, 1980b) Let L be an indexed family of recursive
languages. Then: L ∈ ELIM − T XT if and only if there is an effective procedure
which on every input j ∈ IN enumerates a tell-tale set Tj of strings such that(1) for all j ∈ IN, Tj is finite,(2) for all j ∈ IN, Tj ⊆ Lj ,(3) for all j, z ∈ IN, if Tj ⊆ Lz , then Lz 6⊂ Lj .
From the characterization above one may deduce how the identification by enumeration principle has to be modified in order to obtain a suitable learning method
for learning from positive data. In particular, this method provides insight into the
problem of how to deal with overgeneralization.
Example 5. A universal IIM for learning from text
Let L ∈ ELIM − T XT . Moreover, assume a corresponding procedure which on
every input j ∈ IN enumerates a tell-tale set Tj of strings satisfying the above require(x)ments. Let Tj denotes the finite subset of Tj which may be enumerated within x
steps. The following IIM M ELIM −T XT –identifies L. When fed an initial segment
tx of any text t for a language L ∈ L, M searches for the least index j ≤ x satisfying(x)
Tj ⊆ t +x ⊆ Lj . In case an index j is found, then M outputs the guess j. Otherwise,
M requests the next input.
3
Again, the tell-tale sets are used to control the search within the hypothesis spacein order to find a suitable consistent hypothesis. If the tell-tale set Tj is not completely
enumerated within x steps, M may be forced to produce an overgeneralized hypothesis
when fed a text t for L. Namely, after processing tx it may happen that M outputs a(y)hypothesis j with L ⊂ Lj . But, then there has to be a y > x such that Tj contains astring s not belonging to L (cf. Proposition 3, Condition (3)). Hence, s never appears
in the text t for L and M will reject its former guess j. Furthermore, M will never
output the guess j in any subsequent step.
Thus, we already know one way to design suitable enumeratively working IIMs
that can solve every learning task from positive data as long as indexed families areconcerned. However, a straightforward analysis shows that M is neither set-driven nor
semantically finite. Hence, some desirable properties are still missing. We postpone
the problem of order independence for a while and refer the reader to Section 8 fora detailed discussion. The remaining part of this section is devoted to the problem
18whether or not semantical finiteness can always be achieved. Clearly, any conservative
IIM is semantically finite, too. Therefore, let us have a closer look to conservative
learning. We start with the following characterization of class comprising conservative
inference.
Theorem 5. (Lange and Zeugmann, 1993d) Let L be an indexed family.
Then: L ∈ CCONSERVATIVE −TXT if and only if there are a hypothesis space
G = (Gj )j∈IN and a uniformly recursively generable family (Tj )j∈IN of finite non-empty
sets such that(1) range(L) ⊆ L(G),(2) for all j ∈ IN, Tj ⊆ L(Gj ),(3) for all j, z ∈ N , if Tj ⊆ L(Gz ), then L(Gz ) 6⊂ L(Gj ).
A family of finite sets (Tj )j∈IN is said to be uniformly recursively generable iff
there is a total effective procedure g which, on every input j, generates all elementsof Tj and stops.
Hence, the main difference between conservative learning and learning in the limit
is characterized by the different degree of recursiveness of the corresponding tell-talefamilies. In case of conservative learning they are recursively generable, and in thegeneral case of learning in the limit they are recursively enumerable. And indeed,recursive generability cannot always be achieved as our next example shows.
Example 6. The weakness of conservative learners
In order to verify ELIM −T XT \ CCONSERVATIVE −TXT 6= ∅ we define thefollowing indexed family L = (Lhj,ki )k,j∈IN . For all k ∈ IN, let Lhk,0i = {ak bn n ∈ IN+ }.
For all k ∈ IN and all j ∈ IN+ ,we distinguish the following cases:
Case 1. ¬ Φk (k) ≤ j

Then we set Lhk,ji = Lhk,0i .
Case 2. Φk (k) ≤ j

Let d = 2 · Φk (k) − j. Now, we set:({ak bm 1 ≤ m ≤ d}, if d ≥ 1,
Lhk,ji ={ak b},
otherwise.

L = (Lhk,ji )j,k∈IN is an indexed family of recursive languages, since the predicate“Φi (y) ≤ z” is uniformly decidable in i, y, and z. It is easy to see how a recursively
enumerable tell-tale family has to be defined, and hence L ∈ ELIM −T XT . Thus,
it remains to ask whether or not L can be class comprisingly, and conservatively
identified. An affirmative answer would imply that a finite tell-tale set for the infinite
language Lhk,0i can be recursively generalized. But any procedure which recursively
generates a corresponding tell-tale set may be used to solve simultaneously the halting
problem, a contradiction.
3Note that the same family may be used to witness the weakness of iterative IIMs,
too. However, the reasons for L ∈/ CCONSERVATIVE −TXT and L 6∈ CIT −T XT
are different. Conservative learners cannot handle overgeneralization at all, but iterative learners sometimes can (cf. Section 6, Theorem 18). The main reason for19

L 6∈ CIT −T XT is the topological structure of the finite languages in L. Every IIM
learning L has to output an overgeneralized hypothesis. Taking this into account,
it is intuitively clear that every iterative IIM fails to memorize the maximal element(with respect to lexicographical order) of some finite language a text of which it is fed.
A comprehensive discussion concerning the power and limitations of iterative IIMs isprovided in Section 6.
Up to now, we have discussed learning from text and learning from informant independently. Finally, let us mention an interesting aspect related to the interplay
between information presentation and learnability constraints. In Lange and Zeugmann (1993a) it was shown that the family PAT is finitely identifiable from positive
and negative examples. On the other hand, PAT is even learnable from text. Surprisingly enough, this observation can be generalized as follows.
Theorem 6. SM ON −IN F ⊆ CONSERVATIVE −TXT

Finally, we present a proof of the theorem above which is conceptually completely
different from the one published in Lange and Zeugmann (1993a). It is mainly basedon characterizations recently obtained (cf. Lange and Zeugmann (1992), (1994)).
Proof. The main ingredient is the following characterization of strong-monotonic
inference from positive and negative data (cf. Lange and Zeugmann (1994)).
Theorem 7. Let L be an indexed family of recursive languages. Then: L ∈SM ON −IN F if and only if there are a hypothesis space G = (Gj )j∈IN and uniformly
recursively generable families (Pj )j∈IN and (Nj )j∈IN of finite sets such that(1) range(L) = L(G),(2) for all j ∈ IN, ∅ 6= Pj ⊆ L(Gj ) and Nj ⊆ co − L(Gj ),(3) for all j, z ∈ IN, if Pj ⊆ L(Gz ) as well as Nj ⊆ co−L(Gz ), then L(Gj ) ⊆ L(Gz ).
Let G be the hypothesis space from the characterization above. We show that thefamily (Pj )j∈IN serves as a family of finite tell-tale sets satisfying the requirements in
Theorem 5. In doing so, it suffices to show that Pj ⊆ L(Gz ) implies L(Gz ) 6⊂ L(Gj )for all j, z ∈ IN. Suppose the converse, i.e., Pj ⊆ L(Gz ) as well as L(Gz ) ⊂ L(Gj ) for
any j, z ∈ IN.
Case 1. Nj ∩ L(Gz ) = ∅.

Thus, Pj ⊆ L(Gz ) as well as Nj ⊆ co − L(Gz ) implies L(Gj ) ⊆ L(Gz ) by Theorem
7, Property (3). This contradicts L(Gz ) ⊂ L(Gj ).
Case 2. Nj ∩ L(Gz ) 6= ∅.

Now, there has to be a string s ∈ L(Gz ) such that s ∈ Nj ⊆ co − L(Gj ). Therefore,s ∈ L(Gz ) \ L(Gj ). This contradicts L(Gz ) ⊂ L(Gj ).
The tell-tale family (Pj )j∈IN satisfies Conditions (2) and (3) in Theorem 5, if weselect the class preserving hypothesis space G = (Gj )j∈IN . From the proof of Theorem
5 (cf. Lange and Zeugmann (1993c)) it follows that L can be conservatively inferredwith respect to the hypothesis space G. Hence, L ∈ CONSERVATIVE −TXT . q.e.d.
As we have seen, the learnability of indexed families provides several interesting
problems that are worth to be studied in some more detail. The following sections
survey recently obtained results in a systematic way.
20

4. Characterizations
As we have already seen, characterizations provide a useful tool to answer thequestion how learning algorithms may be designed (cf. Example 5). Moreover, they
may help to gain a better understanding of what different learning types have in common and where the differences are (cf. Proposition 3 and Theorem 5). Furthermore,characterizations may be applied to solve particular learning problems and to solve
deeper theoretical questions (cf. Example 4 and Theorem 6). Therefore, it is justified
to deal with characterizations in some more detail. We continue our guided tour witha survey of representative results and proof techniques. For that purpose it suffices todeal with class preserving learning. We start with learning from positive and negativedata.

4.1. Learning from Informant
Remembering our discussion in Section 3, we already know that Gold’s (1967)
identification by enumeration principle serves as a universal inference algorithm forlearning in the limit. Moreover, every IIM realizing the identification by enumeration
principle fulfills the weak-monotonic and dual weak-monotonic constraint. Hence,
there is no need to characterize these learning models. On the other hand, neither
M ON −IN F , M ON d −IN F , SM ON −IN F nor SM ON d −IN F is as powerful as
learning in the limit. Hence, learning under these monotonicity constraints cannot berealized by a straightforward implementation of Gold’s identification by enumeration
principle. Therefore, we are interested in answering the question whether or not there
is a universal inference method for these learning types. The affirmative answer isgiven by our next theorem that characterizes M ON − IN F in terms of recursively
generable finite tell-tale sets. Note that the same proof technique applies mutatis
mutandis to all remaining learning types (cf. Lange and Zeugmann (1994)).
Theorem 8. Let L be an indexed family of recursive languages. Then: L ∈M ON −IN F if and only if there are a hypothesis space G = (Gj )j∈IN and recursively
generable families (Pj )j∈IN and (Nj )j∈IN of finite sets such that(1) range(L) = L(G),(2) for all j ∈ IN, ∅ 6= Pj ⊆ L(Gj ) and Nj ⊆ co − L(Gj ),(3) for all k, j ∈ IN, and for all L ∈ L, if Pk ∪ Pj ⊆ L(Gj ) ∩ L as well as Nk ∪ Nj ⊆co − L(Gj ) ∩ co − L, then L(Gk ) ∩ L ⊆ L(Gj ) ∩ L.
Proof. Necessity: Let L ∈ M ON−IN F . Then there are an IIM M and a hypothesis
space (Ĝj )j∈IN such that M infers every L ∈ L monotonically from any informant withrespect to (Ĝj )j∈IN . Without loss of generality, we can assume that M is conservative,
too, (cf. Lange and Zeugmann (1993a)). We proceed in showing how to construct(Ĝj )j∈IN . This is done in two steps. First, we define a hypothesis space (G̃j )j∈IN as
well as corresponding recursively generable families (P̃j )j∈IN and (Ñj )j∈IN of finite sets,
where P̃j may be empty for some j ∈ IN. Afterwards, we define a procedure which
enumerates a certain subset of G.
21˜First step: For all k, x ∈ IN we set G̃hk,xi = Ĝk . By construction, range(L) = L(G)is obvious. Let ik be the lexicographically ordered informant for L(Ĝk ), and let x ∈ IN.
We define:P̃hk,xi =

(

ik,+
y ,

if

y = min{z | z ≤ x, M (ikz ) = k, ik,+
6= ∅},z∅,otherwise.

If P̃hk,xi = ik,+
6= ∅, then we set Ñhk,xi = ik,−yy . Otherwise, we define Ñhk,xi = ∅.
The intuitive idea behind the definition of the families (P̃j )j∈IN and (Ñj )j∈IN is asfollows. If an IIM M is fed initial segments of an informant then there is almost no
hope to determine from the appearing outputs what the IIM M has learned fromits input. However, in the particular case that we have an index k of the language
L, the lexicographically ordered informant ik of which is successively fed M , there
is a syntactical criterion that can be effectively tested. Namely, if M (ikz ) = k, then
we know for sure that M has done a pretty good job on input ikz . Clearly, it has
output a correct guess for the language it should learn. Therefore, it seems very
reasonable to suitably collect all the information contained in these initial segmentsin the corresponding families (P̃j )j∈IN and (Ñj )j∈IN . And indeed, it even suffices tocollect the positive data in P̃j , and the negative data in Ñj .
Second step: The hypothesis space (Gj )j∈IN will be defined by simply striking
off all grammars G̃hk,xi with P̃hk,xi = ∅. In order to save readability, we omit thecorresponding mapping yielding the enumeration (Gj )j∈IN from (G̃j )j∈IN . If Gj isreferring to G̃hk,xi , we set Pj = P̃hk,xi and Nj = Ñhk,xi .
We have to show that (Gj )j∈IN , (Nj )j∈IN , and (Pj )j∈IN do fulfill the announced
properties. (1) and (2) follow immediately, since M has, in particular, to infer every
L ∈ L from its lexicographically ordered informant. It remains to show (3). Suppose
L ∈ L and k, j ∈ IN such that Pk ∪ Pj ⊆ L(Gj ) ∩ L as well as Nk ∪ Nj ⊆ co −L(Gj ) ∩ co − L. We have to show L(Gk ) ∩ L ⊆ L(Gj ) ∩ L. Due to our construction,
we can make the following observations. There is a uniquely defined initial segmentof the lexicographically ordered informant ik for L(Gk ), say ikx , such that range(ikx ) =Pk ∪ Nk . Moreover, M (ikx ) = m with L(Gk ) = L(Ĝm ). By ijy we denote the uniquely
defined initial segment of the lexicographically ordered informant ij for L(Gj ) withrange(ijy ) = Pj ∪ Nj . Furthermore, M (ijy ) = n and L(Gj ) = L(Ĝn ). From Pk ⊆ L(Gj )and Nk ⊆ co − L(Gj ), it follows ikx v ij . Since Pj ⊆ L and Nj ⊆ co − L, we conclude
that ijy is an initial segment of the lexicographically ordered informant iL for L.
We have to distinguish the following three cases.
Case 1. x = yHence, m = n and therefore L(Gk ) = L(Gj ). This implies L(Gk ) ∩ L ⊆ L(Gj ) ∩ L.

Case 2. x < yNow, we have ikx v ijy v iL . Moreover, M monotonically infers L from informanti . By the transitivity of “⊆” we immediately obtain L(Gk ) ∩ L ⊆ L(Gj ) ∩ L.
L

Case 3. y < xHence, ijy v ikx v ij . Since M is conservative, too, it follows m = n. Therefore,
22

L(Gk ) = L(Gj ). This implies L(Gk ) ∩ L ⊆ L(Gj ) ∩ L.

Hence, (Gj )j∈IN , (Pj )j∈IN as well as (Nj )j∈IN have indeed the announced properties.

Sufficiency: It suffices to prove that there is an IIM M inferring any L ∈ L
monotonically from any informant with respect to G. Interestingly enough, an easy
modification of the universal IIM described in Example 5 is all we need. So let L ∈ L,
let i be any informant for L, and x ∈ IN.
M (tx ) = “Generate Pj and Nj for j = 0, ..., x and test whether−
Pj ⊆ i +x ⊆ L(Gj ) and Nj ⊆ ix ⊆ co − L(Gj ).

In case there is at least a j fulfilling the test, output the minimal one and request
the next input. Otherwise, output nothing and request the next input.”
Since all of the Pj and Nj are uniformly recursively generable and finite, we seethat M is an IIM. We have to show that it infers L. Let z be the least k such that L =L(Gk ). We claim that M converges to z. Consider P0 , ..., Pz as well as N0 , ..., Nz .
−Then there must be an x such that Pz ⊆ i+x ⊆ L(Gz ) and Nz ⊆ ix ⊆ co − L(Gz ).
That means, at least after having fed ix to M , the machine M outputs a hypothesis.
−
Moreover, since Pz ⊆ i+x+r ⊆ L(Gz ) as well as Nz ⊆ ix+r ⊆ co − L(Gz ) for all r ∈ IN,
the IIM M never produces a guess j > z on ix+r .
Suppose, M converges to j < z. Then we have: Pj ⊆ i+x+r ⊆ L(Gj ) 6= L(Gz ) andNj ⊆ i−
⊆
co
−
L(G
)
for
all
r
∈
IN.
j
x+r
Case 1. L(Gz ) \ L(Gj ) 6= ∅Consequently, there is at least one string s ∈ L(Gz ) \ L(Gj ) such that(s, +) has
to appear sometime in i, say in ix+r for some r. Thus, we have i+x+r 6⊆ L(Gj ), a
contradiction.
Case 2. L(Gj ) \ L(Gz ) 6= ∅Then we may restrict ourselves to the case L(Gz ) ⊂ L(Gj ), since otherwise we areagain in Case 1. Consequently, there is at least one string s ∈ L(Gj ) \ L(Gz ) such that(s, −) has to appear sometime in i, say in ix+r for some r. Thus, i−x+r 6⊆ co − L(Gj ),a contradiction.
Consequently, M converges to z on informant i. To complete the proof we showthat M monotonically learns L. Suppose M outputs k and changes its mind to jin some subsequent step. Consequently, M (ix ) = k and M (ix+r ) = j , for somex, r ∈ IN.
Case 1. L(Gj ) = L

Hence, L(Gk ) ∩ L ⊆ L(Gj ) ∩ L = L is obviously fulfilled.
Case 2. L(Gj ) 6= L+
Due to the definition of M , it holds Pk ⊆ i+
x ⊆ ix+r ⊆ L(Gj ). Hence, Pk ⊆−−L ∩ L(Gj ). Furthermore, we have Nk ⊆ ix ⊆ ix+r ⊆ co − L(Gj ). This implies
Nk ⊆ co − L(Gj ) ∩ co − L. Since M (ix+r ) = j, it holds that Pj ⊆ L and Nj ⊆ co − L.
This yields Pk ∪ Pj ⊆ L(Gj ) ∩ L as well as Nk ∪ Nj ⊆ co − L(Gj ) ∩ co − L. From (3),
we obtain L(Gk ) ∩ L ⊆ L(Gj ) ∩ L.

Hence, M M ON −IN F –identifies L.

q.e.d.

23

As a matter of fact, the machine defined above uses the tell-tale sets to control
its search within the hypothesis space. Therefore, the desired modification of theidentification by enumeration principles has been obtained using the same ideas that
we have exemplified in the proof of Theorem 1 in Section 3.
Exploiting the same proof method similar characterizations for M ON d − IN F ,SM ON −IN F , and SM ON d −IN F have been obtained (cf. Lange and Zeugmann(1994)). Hence, the different monotonicity constraints are completely characterized
by the specific properties of the relevant recursively generable tell-tale families. Notethat the resulting characterization for SM ON − IN F is stated in Section 3, Theorem 7. Finally, the characterization of LIMk −IN F required some new ingredients(cf. Lange and Zeugmann (1993a)). However, the difficulties one has to overcome
when characterizing LIMk −IN F are closely related to the problems one has to handle in characterizing LIMk − T XT . Therefore, we refer the reader to Theorem 10
below.

4.2. Learning from Text
When investigating monotonic language learning from text, the situation is much
more subtle. As we shall see later, the IIM M defined in the proof of Theorem 8 does
not longer serve as a universal learning device. Consequently, a relaxation of the basic
approach underlying M 0 s definition is necessary. We shall come back to this point.
Although Angluin (1980b) established some sufficient conditions that guarantee
exact conservative learning from positive data, it remained open whether the classof those indexed families for which exact conservative learning from positive data
is possible may be characterized in terms of finite non-empty tell-tale sets. Next,
we present a preliminary solution to this long standing open problem. In doing so,
we characterize WM ON − T XT in terms of recursively generable finite tell-tales.
The underlying proof method is powerful enough to successfully attack the original
problem, too, (cf. Section 8, Theorem 42).
Theorem 9. Let L be an indexed family. Then: L ∈ WM ON −T XT if and only
if there are a hypothesis space G = (Gj )j∈IN and a recursively generable family (Tj )j∈INof finite and non-empty sets such that(1) range(L) = L(G),(2) for all j ∈ IN, Tj ⊆ L(Gj ),(3) for all j, z ∈ IN, if Tj ⊆ L(Gz ), then L(Gz ) 6⊂ L(Gj ).
Proof. Necessity: Let L ∈ WM ON −T XT = CONSERVATIVE–TXT. Then there
are an IIM M and a hypothesis space Ĝ = (Ĝj )j∈IN such that M conservatively infers
every L ∈ L with respect to Ĝ. The desired hypothesis space G = (Gj )j∈IN andthe corresponding tell-tale family (Tj )j∈IN can be defined in a similar way as in thedemonstration of Theorem 8. Therefore, we point to the differences, only. First, weconstruct a hypothesis space G̃ = (G̃j )j∈IN as well as a recursively generable family(T̃j )j∈IN of finite but possibly empty sets. For all k, x ∈ IN, we set G̃hk,xi = Ĝk .
Furthermore, for any language L(Ĝk ), let tk be the canonically ordered text of L(Ĝk ).
24

We define:T̃hk,xi =(range(tky ), if∅,

y = min{z z ≤ x, M (tkz ) = k},otherwise.

Obviously, (T̃j )j∈IN is a uniformly recursively generable family of finite sets.
Conceptually, we use the same idea as in the proof of Theorem 8. The main
new ingredient is the introduction of the canonical text. Clearly, if L(Ĝk ) is finite,then the sequence of its lexicographically ordered strings is finite, too. Thus, it does
not constitute a text for L(Ĝk ). The tempting idea to repeat the lexicographicallylargest string infinitely often fails, since the resulting text becomes non-recursive. As
a consequence, the tell-tales were no longer uniformly recursively generable. Using
the canonical text, all these difficulties vanish.
The desired hypothesis space G is obtained from G̃ by simply striking off all grammars G̃hk,xi for which T̃hk,xi = ∅. Analogously, (Tj )j∈IN is obtained from (T̃j )j∈IN .
Obviously, (Tj )j∈IN is a recursively generable family of finite and non-empty sets. In
order to save notational convenience, we refer to Tj as to Thk,xi , i.e., we omit thecorresponding mapping yielding the enumeration of the sets Tj from T̃z . It remains
to show that G = (Gj )j∈IN and (Tj )j∈IN do fulfill the announced properties. Due toour construction, (2) holds obviously. In order to prove (1), let L ∈ L. We have toshow that there is at least a j ∈ IN such that for j = hk, xi we have L = L(Ghk,xi ).
For this purpose, due to our construction, it suffices to show that T̃hk,xi 6= ∅. Let t
be L’s canonically ordered text. Since M has to infer L from t, there are k, y ∈ IN
such that for all z < y, M (tz ) 6= k, M (ty ) = k and L = L(Ĝk ). Consequently,+T̃hk,yi = t+y . Hence, by the convention made above, we get that Thk,yi = ty . Moreover,it immediately follows that L = L(Ghk,xi ) for any x ≥ y. This proves Property (1).
Finally, we have to show (3). It results from the requirement that any conservative
IIM is never allowed to output an overgeneralized hypothesis. To see this, suppose
the converse, i.e., there are j, z ∈ IN such that Tj ⊆ L(Gz ) and L(Gz ) ⊂ L(Gj ). By
definition, there are uniquely determined k, x ∈ IN such that j = hk, xi. Let s0 , ..., sybe the sequence of strings of Tj in canonical order with respect to L(Ghk,xi ) suchthat M (s0 , ..., sy ) = k. Now we conclude that s0 , ..., sy is an initial segment of thecanonically ordered text for L(Gz ), since Tj ⊆ L(Gz ) ⊂ L(Gj ) = L(Ghk,xi ). Finally,
M has to infer L(Gz ) from its canonically ordered text. Thus, it has to perform amind change in some subsequent step which cannot be caused by an inconsistency.
This contradiction yields (3).

Sufficiency: It suffices to prove that there is a conservative IIM M inferring every
L ∈ L from text with respect to G. First,Swe slightly modify the corresponding telltale family. For all j ∈ IN, we set T̂j = n≤j Tn ∩ L(Gj ). Note that the new tell-talefamily fulfills Properties (1) through (3). Let L ∈ L, t ∈ text (L), and x ∈ IN.
M (tx ) = “For j = 0, ..., x, generate T̂j and test whether T̂j ⊆ t+x ⊆ L(Gj ).

In case there is one j fulfilling the test, output the minimal one and request thenext input. Otherwise, output nothing and request the next input.”

Since all of the T̂j are uniformly recursively generable and finite, we see that M isan IIM. Now it suffices to show that M conservatively infers L from t.
25Claim 1. M is conservative.
Let k and j be two hypotheses produced by M on input tx and tx+r , respectively.
We have to show that t+
x+r 6⊆ L(Gk ). For that purpose we distinguish the following
cases.
Case 1. k < j
Due to M ’s definition we immediately obtain t+
x+r 6⊆ L(Gk ).
Case 2. j < kSuppose, t+
x+r ⊆ L(Gk ). In accordance with its definition, M has verified that+T̂j ⊆ tx+r ⊆ L(Gj ). Moreover, the definition of the tell-tale family directly yields+
T̂j ⊆ T̂k , since j < k and T̂j ⊆ t+x+r ⊆ L(Gk ). Taking into account that T̂k ⊆ tx , this
implies Tˆj ⊆ t+x ⊆ L(Gj ). Finally, since j < k we conclude M (tx ) = j, a contradiction.
Hence, the claim is proved.
Claim 2. M infers L from t.
Let z be the least k such that L(Gk ) = L. Therefore, L(Gj ) 6= L for all j ≤ z. By
Property (3) we obtain that L\L(Gj ) 6= ∅ for all j < z provided T̂j ⊆ L. Consequently,
every candidate hypothesis j < z is sometimes rejected by M , and M converges to z.
Hence, the claim follows.
This proves the theorem.

q.e.d.

Looking at the definition of the IIM M it is easy to see that this machine isconceptually the same as that one used in the demonstration of Theorem 8. Since
M is conservative, M it is semantically finite, too. Moreover, M ’s output exclusively
depends on the length as well as on the range of its input. IIMs satisfying the latter
requirement are called rearrangement-independent (cf. Definition 12, Section 8).
The proof method explained above applies mutatis mutandis to characterize strongmonotonic as well as dual strong-monotonic inference from positive data. All thesecharacterizations express the different monotonicity constraints the relevant learnerhas to fulfill by a specific modification of Property (3) from the latter theorem (cf.
Lange and Zeugmann (1992)). Hence, we again arrived at a unifying framework. As aconsequence, class preserving strong-monotonic as well as dual strong-monotonic inference can always be realized by a semantically finite and rearrangement-independent
IIM.
Looking at monotonic language learning from text, the situation considerablychanges (cf. Section 8, Theorem 41). Thus, the IIM M defined in the demonstration of Theorem 9 does not serve as universal learning algorithm for monotonic anddual monotonic inference from text. The same difficulties arise when dealing withlearning within an a priori fixed number of mind changes. Therefore, we continue
with a characterization of LIMk −T XT , and explain the new proof technique. Notethat the following theorem establishes a new method how to handle overgeneralization. This solution to the subset problem considerably improves Angluin’s method(cf. Example 5). Finally, the main idea used in the following proof is powerful enoughto establish characterizations for monotonic and dual monotonic learning, respectively(cf. Zeugmann, Lange and Kapur (1995)).
In order to characterize LIMk −T XT in terms of recursively generable finite tell26

tale sets we have been forced to define an easily computable relation ≺ ⊆ IN × IN
that can be used to distinguish appropriate chains of tell-tales with the help of whichan IIM M may compute its hypotheses. Now we are ready to present the desired
characterization.
Theorem 10. Let L be an indexed family, and k ∈ IN+ . Then: L ∈ LIMk −T XT
if and only if there are a hypothesis space G = (Gj )j∈IN , a computable relation ≺ overIN, and a recursively generable family (Tj )j∈IN of finite and non-empty sets such that(1) range(L) = L(G),(2) for all L ∈ L and all z ∈ IN, Tz ⊆ L(Gz ),(3) for all L ∈ L and every z ∈ IN, and all finite A ⊆ L, if Tz ⊆ L, L(Gz ) 6= L,
then there is a j such that z ≺ j, and A ⊆ Tj ⊆ L(Gj ) = L,(4) for all L ∈ L, there is no sequence (zj )j=0,...,k+1 such that for all j ≤ k, zj ≺ zj+1
as well as all Tzj ⊆ Tzj+1 ⊆ L
Proof. Necessity: Without loss of generality, let M be an IIM consistently inferring
L with respect to some hypothesis space Ĝ = (Ĝj )j∈IN (cf. Lange and Zeugmann(1993b)). Then, for every L ∈ L and every t ∈ text (L) the IIM M performs at
most k mind changes when successively fed t. First, we construct a hypothesis spaceG̃ = (G̃j )j∈IN as well as a recursively generable family (T̃j )j∈IN of finite but possibly
empty sets. Then, we describe a procedure enumerating a certain subset of G̃ which
we call G. Finally, we define the desired relation ≺.

Let σ0 , σ1 , σ2 , ... be an effective enumeration of all finite, non-null sequences ofstrings from Σ∗ such that σx < σy implies x < y for all x, y ∈ IN. Furthermore, for alln, x ∈ IN we set G̃hn,xi = Ĝn . The family (T̃hn,xi )n,x∈IN is defined as follows.
T̃hn,xi =

σx+ , if M (σx ) = n,∅,otherwise.

Obviously, (T̃hn,xi )n,x∈IN is a uniformly recursively generable family of finite sets.
Furthermore, by construction we have L(G̃) = range(L).

Claim 1. For all L ∈ L there exists an index hn, xi such that T̃hn,xi 6= ∅ andL(G̃hn,xi ) = L.

Let t be the canonical text of L. Since M learns L, there exist n, y ∈ IN such that
M (ty ) = n and L = L(Ĝn ). Moreover, ty is a finite, non-null sequence. Hence, there
has to be an x such that σx = ty . Consequently, T̃hn,xi 6= ∅, and L(G̃hn,xi ) = L. This
proves the claim.
We proceed with the definition of the desired hypothesis space G and the relation≺. For that purpose we define a recursive function f as follows. Let f (0) be the least
j with T̃j 6= ∅, and for all j ≥ 1 letj,if T̃j 6= ∅,f (j) =f (j − 1), otherwise.
27

Furthermore, we define Gj = G̃f (j) and Tj = T̃f (j) for all j ∈ IN. Finally, let z, j ∈IN, and let m, n, x, y be the uniquely determined numbers such that f (z) = hm, yi
and f (j) = hn, xi. Then we define z ≺ j if and only if m 6= n and σy < σx .

Clearly, (Tj )j∈IN is a uniformly recursively generable family of finite and non-empty
sets and the relation ≺ is computable. It remains to show that Properties(1) through(4) are satisfied. Property (1) is an immediate consequence of Claim 1 and the definition of G. In order to prove (2) it suffices to show that n = M (σx ) implies σx+ ⊆ L(Ĝn ).
But this is obvious, since M is a consistent IIM.
We continue in proving Property (3). Let L ∈ L, let A ⊆ L be any finite set,
and let z ∈ IN be any index such that Tz ⊆ L and L(Gz ) 6= L. We have to showthat there is a j with z ≺ j and A ⊆ Tj ⊆ L(Gj ) = L. In accordance with ourconstruction we have Tz = T̃f (z) and Gz = G̃f (z) . Let m, y be the uniquely determined
numbers with f (z) = hm, yi. Then we know that M (σy ) = m and L 6= L(Ĝm ), sinceL(Ĝm ) = L(G̃hm,yi ) = L(Gz ) 6= L. Moreover, Tz = σy+ ⊆ L. Hence, σy is an initial
segment of a text for L. Since L 6= L(Gz ), we additionally know that M , on input
σy , has not yet converged to a correct hypothesis for L. Now, let t be the canonicaltext of L. Since A ⊆ L, there exists an a ∈ IN such that A ⊆ t+
a . Moreover, M has
to learn L from every text for it. Consequently, there has to be an r ∈ IN such thatfor n = M (σy ta+r ) the condition L(Ĝn ) = L is satisfied. Furthermore, since σy ta+r
is a finite sequence, there exits an index x with σx = σy ta+r . By construction we get∅ 6= T̃hn,xi ⊆ L(G̃hn,xi ) = L. Thus, there is a number j such that f (j) = hn, xi, andfor every j with f (j) = hn, xi we get σy < σx and m 6= n. Therefore, z ≺ j, and (3)is proved.
We proceed with the demonstration of (4). Looking at the definition of the relation≺ we immediately realize that z ≺ j implies Tz ⊆ Tj . Suppose there is a finite sequence(zj )j=0,...,k+1 such that for all j ≤ k, zj ≺ zj+1 and Tzj ⊆ Tzj+1 ⊆ L. Since zj ≺ zj+1
and Tzj ⊆ Tzj+1 ⊆ L, we get an initial segment of a text t of L on which M changes
its mind k + 1 times, a contradiction. Hence, (4) is proved.
Sufficiency: Again, it suffices to describe an IIM M that infers L in the limit withat most k mind changes from text with respect to G. Let L ∈ L, let t be any text forL, and let x ∈ IN. We define the desired IIM M as follows:
M (tx ) = “If x = 0 or x > 0 and M when successively fed tx−1 does not produce any
guess, then goto (A). Else goto (B).
(A) Search for the least j ≤ x such that Tj ⊆ t+
x . In case it is found, set
yj = x, output j and request the next input. Otherwise, output nothing
and request the next input.
(B) Let j = M (tx−1 ). Test whether there exists a z ≤ x such that j ≺ z and+t+yj ⊆ Tz ⊆ tx . In case one z is found, set yz = x , output z and request
the next input. Otherwise, output j and request the next input.”
Since all of the Tj are uniformly recursively generable and finite and since ≺ is computable, we directly obtain that M is an IIM. We proceed in showing that M identifies
L from t with at most k mind changes.
Claim 1. M converges and card({x M (tx ) 6= M (tx+1 }) ≤ k.
28

Because of (1) and (2), M generates at least one hypothesis when fed the text
t. Furthermore, assume for a moment that M performs more than k mind changes
when inferring L from t. It is easy to recognize that this assumption would imply theexistence of a sequence (Tzj )j=0,...,m with m > k such that for all j < m, zj ≺ zj+1 ,and Tzj ⊆ Tzj+1 ⊆ L. This would contradict (4). Thus, the number of possible mindchanges M may perform when fed t is bounded by k. Moreover, M outputs after acertain period always a hypothesis. Hence, we may conclude that M converges.
Claim 2. If M converges, then the hypothesis M converges to is correct.
Assume that M converges to a hypothesis z with L(Gz ) 6= L. Let x be the leastindex such that M (tx ) = z. Note that Tz ⊆ t+
x by M ’s definition. By Property+(3), there has to be a j such that z ≺ j, tx ⊆ L(Gj ), and L(Gj ) = L. Hence, M
performs an additional mind change when fed a sufficiently large initial segment tx oft satisfying Tj ⊆ t+
x , a contradiction.
By Claim 1 and 2, M infers any L ∈ L with at most k mind changes. Thus, thetheorem is proved.
q.e.d.

Note that the IIM defined in the proof of Theorem 10 uses a new technique todetect whether or not it has to perform a mind change. Clearly, no IIM can provethat its actual guess is correct, except in case it finitely learns. Hence, the machine has
to collect evidence allowing it to decide whether it should prefer a new guess instead ofmaintaining its actual one. The machine defined in the proof above achieves this goalby using a priori knowledge concerning the hypothesis space as well as concerning thefamily of tell-tale sets. This a priori knowledge is provided by the computable relation.
We believe that this approach considerably refines Angluin’s (1980b) method how to
detect overgeneralization. Finally, it should be mentioned that a conceptually similar,
but technically different approach has been successfully applied to limit learning ofrecursive functions (cf. Wiehagen (1991)).

5. Learnability in Dependence on the Hypothesis SpaceHistorically, most authors have investigated exact learnability. Moreover, many investigations in other domains of algorithmic learning theory deal with exact learning
too (cf. e.g. Natarajan (1991)). And indeed, as long as one considers learning in thelimit without any additional demand, every indexed family that is class comprisingly
learnable may be exactly inferred, too (cf. Lange and Zeugmann (1993b)). However,when dealing with characterizations it turned out to be very helpful to constructclass preserving hypothesis spaces (cf. Kapur and Bilardi (1992), Lange and Zeugmann (1992)). Consequently, it is only natural to ask whether or not class preserving
learning algorithms are more powerful than exact ones. Dealing with a measure ofefficiency we found that an appropriate choice of a class preserving hypothesis space
may eventually increase the learning power (cf. Lange and Zeugmann (1993b)). Recently, these results have been considerably improved and similar effects concerning
the relation between class preserving and class comprising inference have been elaborated (cf. Lange (1994)). Furthermore, studying the capabilities of learning algorithms
in dependence on the hypothesis space has yield very interesting results concerning29

probabilistic learning models (cf., e.g., Anthony and Biggs (1992), Freivalds, Kinberand Wiehagen (1988)). Therefore, it is worth to study this phenomenon in some moredetail.
First, we present results demonstrating the superiority of class comprising to classpreserving monotonic learning algorithms that are themselves superior to exact ones.
These separations have been obtained by developing a new powerful proof technique.
Establishing the announced separations using standard proof techniques would require to diagonalize against all hypothesis spaces and all IIMs. Instead, we haveelaborated an almost always effective reduction of the halting problem to monotonic
learning problems. This approach yields easy to describe indexed families witnessing
the desired separations. Next, we present results comparing class comprising and exact inference procedures. These results strongly recommend the designer of learningalgorithms to carefully choose the enumeration as well as the description of the target
languages to get exact learning procedures of maximal power (cf. Theorem 15).
Finally, we ask why, for example, class preserving inference is sometimes more
powerful than exact learning. Obviously, as long as there is an effective compiler
from the space G of hypotheses into the indexed family L, both models of inference
are of equal power. Looking at learning in the limit, Gold (1967) proved that evenlimiting recursive compilers do suffice. What we present is a characterization result
stating that exact learning is of the same power as class preserving inference if andonly if there is a limiting recursive compiler satisfying an appropriate monotonicity
requirement (cf. Theorem 17). Hence, our separations prove the non-existence of suchcompilers.

5.1. Separations
In this subsection we compare the learning capabilities of most of the introduced
models of monotonic and dual-monotonic inference in dependence on the hypothesis
space. The underlying selection aims to illustrate different effects which occur. The
following theorem provides a summary of results obtained that relate the power ofexact identification, class preserving inference, and class comprising learning undervarious monotonicity constraints to one another (cf. Lange, Zeugmann and Kapur(1992), Lange and Zeugmann (1993c, 1993d)).
Theorem 11.
ELIM −T XT∪
EWM ON d −T XT∪
EWM ON −T XT∪
ESM ON −T XT∪
EF IN −T XTk
ESM ON d −T XT

=
⊂
⊂
⊂
=
=

LIM −T XT∪WM ON d −T XT∪
WM ON −T XT∪
SM ON −T XT∪F IN −T XTkSM ON d −T XT
30

=
⊂
⊂
⊂
=
⊂

CLIM −T XTk
CWM ON d −T XT∪CWM ON −T XT∪
CSM ON −T XT∪
CF IN −T XT∩
CSM ON d −T XT

For instance, it turns out that dual weak-monotonic learning is exactly as powerfulas learning in the limit, if class comprising hypothesis spaces are admissible. In
particular, a dual weak-monotonic learner may realize a suitable interplay between
generalization and specialization (cf. Theorem 15). In comparison to CWM ON −T XT ⊂ CLIM − T XT , having the freedom to combine both, generalization andspecialization is essential in order to achieve maximal learning power. We consider thisas a particular answer to the long-standing debate in the machine learning community
for and against learning by generalization and learning by specialization, respectively.
Furthermore, the following incomparabilities have been shown (cf. Lange and Zeugmann (1993c, 1993d)).
Theorem 12.
(1) WM ON −T XT# CSM ON −T XT(2) EWM ON −T XT# CSM ON −T XT(3) EWM ON −T XT# SM ON −T XT(4) CSM ON d −T XT# CSM ON −T XTDetailed proofs of both theorems can be found in Lange and Zeugmann (1993d).
Because of the lack of space, we demonstrate one separation, only. On the one hand,
this should illustrate the underlying proof technique. On the other hand, the corresponding result has some special features distinguishing it from most of the otherones (cf. Theorem 14).
Theorem 13. SM ON d −T XT ⊂ CSM ON d −T XTProof. Obviously, by definition SM ON d −T XT ⊆ CSM ON d −T XT . It suffices toshow that CSM ON d−T XT \SM ON d−T XT 6= ∅. The desired indexed family Lcsd =(Lhk,ji )k,j∈IN is defined as follows. For all k ∈ IN we set Lhk,0i = {ak+1 }∪{bn n ∈ IN+ }.
For all k ∈ IN and all j ≥ 1, we distinguish the following cases:
Case 1. ¬ Φk (k) ≤ j

We set Lhk,ji = Lhk,0i .

Case 2. Φk (k) = x ≤ jThen, we set Lhk,ji = {ak+1 } ∪ {bm 1 ≤ m ≤ x} ∪ {cj }.

Lemma 1. Lcsd 6∈ SM ON d −T XTSince EF IN − T XT = SM ON d − T XT (cf. Theorem 11), it remains to showthat there is no IIM M which finitely infers Lcsd with respect to Lcsd . Thereby, we
effectively reduce the halting problem to Lcsd ∈ EF IN −T XT .

Claim. If there exists an IIM M witnessing Lcsd ∈ EF IN − T XT , then one
can effectively construct an algorithm deciding for all k ∈ IN whether or not ϕk (k)converges.

Let M be any IIM witnessing Lcsd ∈ EF IN − T XT . First of all, we define analgorithm A solving the halting problem. On input k ∈ IN the algorithm A executes
the following instructions:

31

(A1) For z = 0, 1, 2, . . . generate successively the lexicographically ordered text t of
Lhk,0i until M on input tz outputs for the first time a hypothesis of the formhk, ji, i.e., M (tz ) = hk, ji.
(A2) Test whether Φk (k) ≤ max{j, z}. In case it is, output “ϕk (k) converges.”
Otherwise output “ϕk (k) diverges.”
Due to our assumption, M in particular finitely infers Lhk,0i from its lexicographically ordered text. Taking Lcsd ’s definition into account one can easily deduce that M
has to output a hypothesis of the form hk, ji, since any other hypotheses describe alanguage which is definitely different from Lhk,0i . Thus, Instruction (A1) has to terminate. Due to the definition of a complexity measure Instruction (A2) can be effectively
accomplished. Therefore, algorithm A eventually terminates for every number k.

It remains to show that ϕk (k) is undefined, if ¬ Φk (k) ≤ max{j, z}. Suppose theconverse, i.e., ϕk (k) is defined. Then, Φk (k) = x for some x > max{z, j}. Taking
again Lcsd definition into account it follows Lhk,ji = Lhk,0i , since x > j. Now, letm be the maximal index such that bm ∈ t+
z . Obviously, m < x, since t is thelexicographically ordered text of Lhk,0i . Thus, tz is an initial segment of a text for thefinite language Lhk,xi . Note that Lhk,xi 6= Lhk,0i . Thus, M fails to finitely infer Lhk,xifrom every text having the initial segment tz . This contradiction completes the proofof the above claim. Hence, Lemma 1 follows.
Lemma 2. Lcsd ∈ CSM ON d −T XT

We have to show that there are an appropriate hypothesis space Gcsd comprising
Lcsd and an IIM M inferring L dual strong-monotonically with respect to Gcsd .

We define the wanted hypothesis
space Gcsd = (Ghk,ji )k,j∈IN as follows. For all
Sk, j ∈ IN, we set L(Ghk,0i ) = j∈IN Lhk,ji and L(Ghk,j+1i ) = Lhk,ji . Taking the definitionof Lcsd into account, it is easy to verify that membership is uniformly decidable for
Gcsd .

Now, let k ∈ IN. If ϕk (k) is undefined, we have L(Ghk,0i ) = Lhk,ji = Lhk,0i for allj ∈ IN. Otherwise, i.e., if ϕk (k) is defined, we have L(Ghk,0i ) ⊃ Lhk,ji for all j ∈ IN.
Thus, a dual strong-monotonic learner M may simply output the hypothesis hk, 0i
after the corresponding identifier ak+1 has been presented. No matter whether or not
ϕk (k) is defined, hk, 0i is a suitable hypothesis. If ϕk (k) is undefined, hk, 0i is alreadythe desired final guess. Otherwise, one string has to appear which tells M in which
way the language L(Ghk,0i ) has to be specialized. Consequently, M CSM ON d−T XT –identifies Lcsd with respect to the class comprising hypothesis space Gcsd .
q.e.d.
The new proof technique demonstrated above applies to obtain most of the statedseparations. In particular, we can almost always effectively reduce the halting problem
to several monotonic learning problems. These reductions imply that the consideredlearning problems are at least as hard as the halting problem. This insight deserves
some attention. Gold (1967) showed that no IIM can learn the class R of all recursivefunctions in the limit. On the other hand, the degree of the algorithmic unsolvabilityof R ∈ LIM is strictly less than the degree of the halting problem (cf., Adleman andBlum (1991)). This puts the constraint to learn monotonically with respect to a particular hypothesis space into a new perspective. An algorithmically solvable learning
problem (e.g. Lcsd ∈ CSM ON d−T XT ) may become algorithmically unsolvable, if an
32

at first glance natural demand is added (e.g. to learn class preservingly). Moreover,the degree of unsolvability may be at least as high as that of the halting problem, andis, therefore, strictly higher than that of learning all recursive functions. As far as weknow, there is only one paper stating an analogous result in the setting of inductive
inference of recursive functions, namely Freivalds, Kinber and Wiehagen (1992).

5.2. Class Comprising and Exact Learning
When dealing with monotonic inference, class comprising learning is almost always
more powerful than class preserving inference which itself is superior to exact learning.
In particular, the results obtained give strong evidence that exclusively changing thedescriptions for the objects to be learned as well as their enumeration does not sufficeto get learning algorithms of maximal power. Therefore, we are interested in knowing
what kind of languages has to be supplemented to hypothesis spaces in order to design
superior inference procedures. Moreover, we ask whether or not these added languages
may be learned themselves as well. As the following theorems show, the answer tothese questions strongly depends on the type of monotonicity requirement involved.
First, we investigate dual-strong monotonic learning. Applying the same idea usedin the demonstration of Lcsd 6∈ EF IN − T XT (cf. Theorem 13, Lemma 1) one caneasily show that L(Gcsd ) 6∈ SM ON d −T XT . Hence, in order to learn the family Lcsd
strong-monotonically one is required to add grammars to the hypothesis space that
describe languages being not learnable themselves. It turns out that this property is
characteristic for dual strong-monotonic inference as the following theorem shows.
Theorem 14. Let L be any indexed family satisfying L ∈ CSM ON − T XT d \SM ON d−T XT . Then there is no hypothesis space G = (Gj )j∈IN such that L ⊂ L(G),and L(G) ∈ SM ON d −T XT .

Proof. Suppose the converse, i.e., there is a hypothesis space G = (Gj )j∈IN such that
L(G) ∈ SM ON d −T XT . By assumption, L ∈ CSM ON d −T XT \ SM ON d −T XT ,and hence, L ⊂ L(G). Moreover, due to Theorem 11 we know that F IN −T XT =SM ON d −T XT . Therefore, L(G) ∈ SM ON d −T XT implies L(G) ∈ F IN −T XT .
Consequently, there is an IIM M that finitely infers L(G). On the other hand, L ⊂L(G). Hence, M finitely infers L, too. Applying Theorem 11 once again yields
L ∈ EF IN −T XT . Thus, we conclude L ∈ SM ON d −T XT which contradicts ourassumption.
q.e.d.
The situation completely changes, if weak-monotonic learning and its dual counterpart are investigated.
Theorem 15. For all indexed families L we have:

If L ∈ CWM ON d−T XT , then there is a hypothesis space G = (Gj )j∈IN comprising
L such that L(G) ∈ EWM ON d −T XT .

Proof. Let L ∈ CWM ON d − T XT . Since CWM ON d − T XT = ELIM − T XT
(cf. Theorem 11), there is an IIM M which ELIM −T XT –infers L with respect tothe hypothesis space L.

Let L̂ = (L̂j )j∈IN denote any canonical enumeration of all singleton languages overthe underlying alphabet and all languages in L. Obviously, M can be easily converted
33into an IIM M̂ which ELIM −T XT identifies L̂. Without loss of generality we may
assume that M̂ is consistent, too (cf. Lange and Zeugmann (1993a)). Furthermore,assume that M̂ outputs a canonical number of a singleton language as long as theinitial segment presented to M̂ does not contain two different strings.
It remains to define an IIM M̃ which dual weak-monotonically infers L̂ with respect to L̂. This proves the above theorem, if we choose G = (Gj )j∈IN such that
(L(Gj ))j∈IN = (L̂j )j∈IN .
Let L̂ be any language in L̂, t ∈ text (L̂), and x ∈ IN. Furthermore, let j0 , j1 , j2 , . . .
denote the sequence of hypotheses generated by M̂ when successively fed t. Instead of
this sequence, M̃ produces the following sequence of hypotheses j0 , k0 , j1 , k1 , j2 , k2 , . . .
when fed t, too. Thereby, the indices k0 , k1 , k2 , . . . generated by M̃ as intermediate
hypotheses are defined as follows. Let z ∈ IN. If jz = jz+1 , then let kz = jz . Otherwise,i.e., jz 6= jz+1 , let kz denote the number of the singleton language containing the firststring in t.
Obviously, M̃ converges to a correct number of L̂, since M̂ infers L̂ when fed t. It
remains to show that M̃ works dual weak-monotonically. It suffices to discuss the casejz 6= jz+1 . Since M̂ exclusively produces consistent hypotheses, it follows Ljz ⊇ Lkz
because of the choice of the hypothesis kz . Hence, M̃ has specialized its former
guess Ljz . On the other hand, jz 6= jz+1 implies that at least two different strings
occur in the initial segment M̂ is fed. Consequently, Lkz is an inconsistent hypothesis
and, therefore, the mind change from kz to jz+1 is a justified one. Thereby, M̃ hasgeneralized its former hypothesis kz , since jz+1 is consistent. Thus, we may conclude
that M̃ satisfies the dual weak-monotonicity constraint.
q.e.d.
In fact, the IIM M̃ defined above realizes a suitable interplay between learning
by generalization and learning by specialization. Thereby, M̃ doubles the number ofmind changes which M̂ performs when processing the same text.
An analogous result can be shown for weak-monotonic learning, too (cf. Section 8,
Corollary 40).
Theorem 16. For all indexed families L we have:

If L ∈ CWM ON −T XT , then there is a hypothesis space G = (Gj )j∈IN comprising
L such that L(G) ∈ EWM ON −T XT .

5.3. Limiting Recursive Compilers
This subsection is devoted to the problem why an indexed family L that canbe learned with respect to some hypothesis space G = (Gj )j∈IN might become noninferable with respect to other hypothesis spaces Ĝ = (Ĝj )j∈IN satisfying L ⊆ L(Ĝ).
A first hint how to answer this question has already been given by Gold (1967).
Namely, he proved that, whenever there is a limiting recursive compiler (cf. Definition
9 below) from G into Ĝ, then any IIM inferring a class L of languages with respect to G
can easily be converted into one that learns L with respect to Ĝ. Considering indexedfamilies being learnable with respect to some space G of hypotheses, we could provethat there is always a limiting recursive compiler from G into L. The same is, mutatis
mutandis, true for finite learning, i.e., there is always a recursive compiler from G into34

L. However, if some monotonicity requirement is involved, then the situation considerably changes. The reason for that phenomenon is as follows. A limiting recursivecompiler in general does not preserve any of the introduced monotonicity demands.
But even if it does, it is a highly non-trivial task to convert an IIM that, for example,
class preservingly learns an indexed family L with respect to some appropriate chosen
hypothesis space G into an IIM exactly learning L. The latter difficulty is caused by
the fact that one has to combine two limiting processes into one.
For the sake of presentation we give only one of the theorems obtained, since itdoes already suffice to convey the spirit of the insight achievable. We start with theformal definition of limiting recursive compilers.
Definition 9. Let G = (Gj )j∈IN and Ĝ = (Ĝj )j∈IN be two spaces of hypotheses
such that L(G) = L(Ĝ). A recursive function f : IN × IN → IN is said to be alimiting recursive compiler from G into Ĝ iff k := limx→∞ f (j, x) exists andsatisfies L(Gj ) = L(Ĝk ) for all j ∈ IN.
Next we introduce limiting recursive compilers fulfilling a certain monotonicity
demand.

Definition 10. Let G = (Gj )j∈IN and Ĝ = (Ĝj )j∈IN be two hypothesis spaces suchthat L(G) = L(Ĝ). A limiting recursive compiler f from G into Ĝ is said tobe strong-monotonic iff L(Ĝf (j,x) ) ⊆ L(Ĝf (j,x+1) ) for all j, x ∈ IN
Now we are ready to present the announced characterization comparing the powerof exact and class preserving learning algorithms under the constraint to learn strongmonotonically. Note that the proof presented below is a considerably improved versionof that one in Lange and Zeugmann (1993c).

Theorem 17. Let L be an indexed family and let G = (Gj )j∈IN be a hypothesis
space such that L ∈ SM ON −T XT with respect to G. Then we have:
L ∈ ESM ON −T XT if and only if there is a strong-monotonic limiting recursivecompiler from G into L.

Proof. Necessity. Let L ∈ ESM ON − T XT . Then there is an IIM M strongmonotonically inferring L with respect to L. We define the desired limiting recursivecompiler from G = (Gj )j∈IN into L as follows. Let j, x ∈ IN and let tj be the canonicaltext of L(Gj ). We set:f (j, x) = “Compute the sequence (M (tjz ))z∈IN up to length x. Let jy be the lastelement of this sequence. Set f (j, x) = jy .”It is straightforward to verify that f is a strong-monotonic limiting recursive compiler
from G into L.

Sufficiency. Let L ∈ SM ON − T XT with respect to G be witnessed by M̂ , andlet f be a strong-monotonic limiting recursive compiler from G into L. Without lossof generality we may assume that M̂ exclusively outputs consistent hypotheses (cf.
Lange and Zeugmann (1993a)). We have to define an IIM M that ESM ON −T XT –infers L. The main difficulty we have to deal with is the combination of two limiting
recursive processes into one yielding an IIM strong-monotonically inferring L withrespect to L.
Let L ∈ L, t ∈ text (L), and x ∈ IN. Then, we define:35M (tx ) = “Simulate M̂ when fed tx . If M̂ does not output any hypothesis, then output
nothing and request the next input. Otherwise, execute Instruction (A).
(A) Let M̂ (tx ) = j. Determine the least y ∈ IN such that t+x ⊆ Lf (j,y) . Output
f (j, y) and request the next input.”
Recall that M̂ is consistent. Consequently, M̂ (tx ) = j implies t+
x ⊆ L(Gj ). Since
f defines a limiting recursive compiler from G into L, there exists a y ∈ IN such that
Lf (j,y) = L(Gj ). Furthermore, since L is an indexed family, M always effectively finds
an index y ∈ IN satisfying t+
x ⊆ Lf (j,y) . Thus, Instruction (A) terminates and M isindeed an IIM.
Next, we show that M infers L when fed t. Since M̂ witnesses L ∈ SM ON−T XT ,there is a z ∈ IN such that M̂ (tz+r ) = j with L(Gj ) = L for all r ∈ IN. Since f defines
a strong monotonic limiting recursive compiler from G into L, there is a least y ∈ IN
such that Lf (j,y) = L(Gj ). Furthermore, Lf (j,n) ⊂ Lf (j,y) for all n < y. By definition,
M converges to the correct guess Lf (j,y) when fed t.
Finally, it remains to show that M behaves strong-monotonically when processing
the text t for L. First, we prove the following claim.
Claim. M̂ (tx ) = j implies L(Gj ) ⊆ L̂ for all L̂ ∈ L satisfying t+
x ⊆ L̂.

+Let L̂ ∈ L such that t+x ⊆ L̂. Obviously, tx ⊆ L̂ implies that there is a text t̂ forL̂ having the initial segment tx . Since M̂ , in particular, strong-monotonically infers
L̂ on t̂, M̂ (tx ) = M̂ (t̂x ) = j implies L(Gj ) ⊆ L̂. This proves the claim.

Now, let f (j, y) and f (k, z) denote any two different hypotheses subsequently generated by M when fed t, i.e., M (tx ) = f (j, y) and M (tx+r ) = f (k, z) for any x ∈ IN
and r ∈ IN+ . It remains to show Lf (j,y) ⊆ Lf (k,z) .
Case 1. j = k

By the definition of M , y < z. Since f defines a strong-monotonic limiting recursivecompiler from G into L, y < z directly implies Lf (j,y) ⊆ Lf (j,z) .
Case 2. j 6= k

By definition of a strong-monotonic limiting recursive compiler Lf (j,y) ⊆ L(Gj ).
+Taking M ’s definition into consideration we obtain t+
x+r ⊆ Lf (k,z) . Therefore, tx ⊆Lf (k,z) , too. On the other hand M̂ (tx ) = j by the definition of M . Thus, by applying
the claim above we obtain L(Gj ) ⊆ Lf (k,z) . Consequently, Lf (j,y) ⊆ L(Gj ) ⊆ Lf (k,z)
and, therefore, Lf (j,y) ⊆ Lf (k,z) .
This proves the theorem.

q.e.d.

Let us finish our survey on the learnability in dependence on the hypothesis spacewith the remark that this filed is large and the discourse here is brief. Further information concerning this subject is in part provided in the subsequent sections. Finally,
the most intriguing open problems are outlined in Section 9.

6. Iterative IIMs
Within the standard definition of inductive inference machines the limitation of
space in realistic computations is not considered. Weakening the requirement that a36

learner has always access to the whole initial segment of a text (an informant) it has
been fed results in the concept of iterative learning. An iterative IIM is only allowed touse its last guess and the next string of a text and an informant, respectively, in orderto produce its next guess. From the viewpoint of potential applications this approachseems to be well-suited. As discussed in Section 3, the class of all pattern languages
can be identified by an iterative IIM from text. On the other hand, the question
naturally arises whether this restriction seriously affects the learning capabilities. In
answering this question, we are mainly interested in estimating the power of iterative
learners which are required to fulfill simultaneously certain monotonicity constraints.

6.1. On the Strength of Iterative IIMs
Conceptually, it seems to be appropriate to think about an iterative IIM M as
follows: When fed a text (an informant) of a language M is supposed to learn, M
defines a sequence (Mn )n∈IN of learning devices each of which takes as its input theoutput of its predecessor. Furthermore, since iterative learners are always required to
produce an output (cf. Definition 8), it seems to be reasonable to consider exclusively
iterative IIMs which are allowed to work with respect to a class comprising hypothesis
space. On the other hand, we have seen that the learning capabilities of monotonic
IIMs essentially depend on the selection of the underlying hypothesis space (cf. Section
5). Consequently, it is interesting to know whether or not iterative learners are also
sensitive to the the choice of the underlying space of hypotheses.
Theorem 18. EIT −T XT ⊂ IT −T XTProof. By definition it suffices to show IT −T XT \ EIT −T XT 6= ∅. Again, we
reduce the halting problem to a suitably chosen learning task. The desired indexedfamily Leit = (Lhk,ji )k,j∈IN is defined as follows. For all k ∈ IN, we set Lhk,0i ={ak+1 } ∪ {bn n ∈ IN+ }. For all j ≥ 1, we distinguish the following cases.
Case 1. ¬ Φk (k) ≤ j

We set Lhk,ji = {ak+1 }.

Case 2. Φk (k) = x ≤ jThen, we set Lhk,ji = {ak+1 } ∪ {bm 1 ≤ m ≤ x}.

Obviously, Leit is an indexed family. The non-learnability of Leit in the sense of
EIT − T XT is due to the following facts. For every k ∈ IN, there is exactly one
index for the infinite language Lhk,0i . Moreover, no IIM weak-monotonically infers
Leit with respect to Leit . Hence, every IIM learning Leit has to produce at least
once an overgeneralized hypothesis. Therefore, it has sometimes to shrink its guess
to a finite language. But afterwards, it might receive data forcing it to output thecorresponding number of the relevant infinite language. Now, every iterative IIM
exactly learning Leit is in serious trouble, since the only available hypothesis does not
suffice to memorize the fact that the shrunk guess has been provably rejected. We
continue with the formal proof.
Claim 1. Leit 6∈ EIT −T XTSuppose that there exists any IIM M which EIT − T XT -identifies Leit . Let us
consider M ’s behavior when fed the text t = ak+1 , b, b2 , . . . for the language Lhk,0i .
37Since Leit 6∈ EWM ON −T XT (cf. Lange and Zeugmann (1993b)), there have to be
indices k, x ∈ IN such that ϕk (k) ↓ with Φk (k) > x and M outputs the hypothesis hk, 0i
after processing tx . Obviously, tx serves as an initial segment of a text for Lhk,Φk (k)i ,too. Thus, there has to be a string s ∈ Lhk,Φk (k)i such that M (hk, 0i, s) = hk, yi forsome y ≥ Φk (k). (Note that Lhk,yi = Lhk,Φk (k)i , if y ≥ Φk (k).) On the other hand, M
has, in particular, to infer the infinite language Lhk,0i from its text t̂ = tx , s, b, s, b2 , . . .
Since the string s appears infinitely many times, M outputs infinitely many times
the wrong hypothesis hk, yi. Thus, M fails to converge to a correct guess on t̂, acontradiction.
Claim 2. Leit ∈ IT −T XT

We sketch the underlying idea, only. Now, assume any class preserving hypothesis
space G which contains for every k ∈ IN at least two different indices, say jk and ̂k , for
the infinite language Lhk,0i . Applying this a priori knowledge about the underlying
hypothesis space, an iterative IIM M is able to handle overgeneralization. Thereby,
M may use each of both semantically equivalent hypotheses to represent different
stages. Clearly, as long as M is exclusively fed ak+1 , it outputs a canonical numberof that singleton language. Now we describe how M uses the semantical equivalent
hypotheses. The index jk may be used to encode that M ’s last guess Lhk,0i is apossibly overgeneralized hypothesis which may be changed in some subsequent step.
M outputs this hypothesis as long as it has no knowledge whether or not Φk (k) ↓,i.e., as long as it has exclusively seen strings bz such that ¬Φk (k) ≤ z. On the other
hand, if M has been fed a string bz satisfying Φk (k) ≤ z then it knows for sure thatΦk (k) ↓. After having gained this knowledge, it never outputs jk . Instead, it either
output an index for the corresponding finite language or, in case enough evidence has
been presented, the index ̂k for Lhk,0i . We omit the details.
q.e.d.
As the latter proof shows iterative IIMs may successfully handle overgeneralization.
Moreover, their ability to solve the subset problem seriously depends on the choice ofthe relevant hypothesis space. However, it remained open whether or not the powerof iterative IIMs increases, if class comprising hypothesis spaces are admissible. But
it is known that CIT −T XT ⊂ CWM ON −T XT (cf. Lange and Zeugmann (1995)).
Hence, iterative learning does not achieve the whole power of weak-monotonic IIMs.
Nevertheless, the proof technique presented above is powerful enough to compare
exact iterative learning and class preserving weak-monotonic inference. Moreover, thefollowing theorems additionally relate the power of CM ON−T XT and of CSM ON−
T XT to the capabilities of iterative IIMs.
Theorem 19. 1(1) EIT −T XT \ CSM ON −T XT 6= ∅(2) EIT −T XT \ CM ON −T XT 6= ∅(3) EIT −T XT \ WM ON −T XT 6= ∅Proof. First, we proof Assertion (2). We define an indexed family L over thealphabet Σ = {a, b} as follows. Let L0 = {a}+ and Lk,n = {aj 1 ≤ j ≤ k} ∪1

Assertion (3) corrects the erroneous statement EIT −T XT \ CWM ON−T XT 6= ∅ in Zeugmann
and Lange (1995).

38

{bk , an , bn }. L ∈ EIT−T XT can be easily verified. On the other hand, L 6∈ CM ON−
T XT results from the following observations. Suppose that there is an IIM M whichmonotonically infers L with respect to a class comprising hypothesis space G. Since
M has to infer L0 on its lexicographically ordered text t, there is an x ∈ IN such that
M (tx ) = j with L(Gj ) = L0 . Now, tx may be extended to become a text t̂ for the
language Lx,x on which M sometimes has to output a correct hypothesis z, say after
processing t̂x+r . Obviously, t̂x+r forms an initial segment of a text for the language
Lx,x+1 . When fed t̂x+r , M ’s first guess j correctly contains the string ax+1 ∈ Lx,x+1 ,but ax+1 is incorrectly excluded by its subsequent guess z. Thus, M violates themonotonicity constraint when inferring Lx,x+1 on a text having the initial segmentt̂x+r .
Since CSM ON −T XT ⊂ CM ON −T XT Assertion (1) follows immediately. Furthermore, since CM ON −T XT # WM ON −T XT , proving Assertion (3) requires adifferent approach.
Subsequently, we use the following shorthands. For all n, m ∈ IN, let L̂hn,0i =1 ≤ j} and L̂hn,mi = {bn cj 1 ≤ j ≤ m}. The desired indexed family{b c
L = (Lhk,ji )k,j∈IN will be defined as follows. Let k ∈ IN. We distinguish the following
cases.
n jCase 1. j ≤ 1

SThen, we set Lhk,ji = {ak+1 } ∪ ( n∈IN L̂hn,0i ).

Case 2. j ≥ 2

We distinguish the following subcases:
Subcase 2.1. ¬ Φk (k) ≤ j − 1

Then, let Lhk,ji = Lhk,0i .

Subcase 2.2. Φk (k) ≤ j − 1 ≤ 2Φk (k)SS

Let d = (j − 1) − Φk (k). Then, we set Lhk,ji = {ak+1 } ∪ ( n≤d L̂hn,0i ) ∪ ( n>d L̂hn,Φk (k)i ).

Subcase 2.3. j − 1 > 2Φk (k)SThen, we set Lhk,ji = {ak+1 } ∪ L̂h0,0i ∪ ( n>0 L̂hn,Φk (k)i ).

L 6∈ WM ON−T XT follows by applying our standard proof idea, namely by reducing the halting problem to L ∈ WM ON −T XT (cf. Lange and Zeugmann (1993c)).
Next, we define an iterative IIM M which infers L with respect to the hypothesis
space L. Let L ∈ L and let t = s0 , s1 , s2 , . . . be any text for L. Without loss ofgenerality, we may assume that s0 = ak+1 for some k ∈ IN. (If s0 6= ak+1 , M simply
ignores all strings presented until a string ak+1 appears for the first time.) The IIM
M is defined in stages, where Stage x conceptually describes Mx .
Stage 0: Let s0 = ak+1 for some k ∈ IN. Set j0 = hk, 0i. Output hk, 0i, and goto
Stage 1.
Stage x: M receives as input jx−1 and the x + 1st element sx of t. If sx = ak+1 forsome k ∈ IN, then set jx = jx−1 . Output jx , and goto Stage x + 1. Otherwise,sx = bn cm for some n, m ∈ IN.
Case 1. jx−1 = hk, 0i for some k ∈ IN

39

Test whether or not Φk (k) ≤ m. In case it is, set jx = hk, Φk (k) + 1i,
output jx , and goto Stage x + 1. Otherwise, set jx = jx−1 , output jx , andgoto Stage x + 1.
Case 2. jx−1 = hk, 1i for some k ∈ IN

Set jx = jx−1 , output jx , and goto Stage x + 1.

Case 3. jx−1 = hk, zi for some k ∈ IN and some z ≥ 1

Test whether or not sx = bn cm ∈ Lhk,zi . In case it is, set jx = jx−1 , output
jx , and goto Stage x + 1. Otherwise, execute Instruction (A).
(A) Test whether or not n ≤ Φk (k). In case it is, set jx = hk, Φk (k)+n+1i,
output jx , and goto Stage x + 1. Otherwise, set jx = hk, 1i, output jx ,and goto Stage x + 1.

It remains to show that M infers L. Let k, z ∈ IN. Assume that a text t for thetarget language L = Lhk,zi is presented. If ϕk (k) is undefined, then M outputs inevery step the guess hk, 0i. Since Lhk,0i = Lhk,zi for all z ∈ IN, M infers L from text t.
It remains to discuss the case that ϕk (k) is defined.
Because of the definition of L, there has to be an x ∈ IN such that sx = cm withm ≥ Φk (k). Hence, M eventually rejects its current guess hk, 0i and changes its mind
to the guess hk, Φk (k) + 1i. Afterwards, M realizes the subset principle. In particular,
M avoids overgeneralization in every subsequent step. Since M has to distinguishbetween finitely many possible hypotheses, only, M converges to a correct hypotheses.
Note that every language is uniquely characterized by infinitely many strings of theform bn cm satisfying m > Φk (k) whereas the maximal index n is referring to a correct
number of the target language L.
Thus, M behaves as required. This finishes the proof of Assertion (3).

q.e.d.

If language learning from informant is investigated, the situation slightly changes.
The difference is caused by the fact that the weak-monotonicity constraint does notfurther restrict learning power. A detailed proof of the theorem below may be foundin Lange and Zeugmann (1992).
Theorem 20.
(1) EIT −IN F \ CSM ON −IN F 6= ∅(2) EIT −IN F \ CM ON −IN F 6= ∅(3) CIT −IN F ⊂ EWM ON −IN F

6.2. Monotonic Inference by Iterative Machines
In this subsection we aim to give some more insight concerning the trade-offs between information presentation and monotonicity constraints. Our treatment is basedon the following perspective. Obviously, an iterative learner has only a limited access to the history of the learning process. Contrary to that, a monotonic learner
can inspect the whole initial segment it has been fed. Thus, it may recompute thewhole sequence of hypotheses created so far, and may incorporate this knowledge into40

the production of its actual guess. On the other hand, learning under monotonicity
constraints provides additional a priory knowledge concerning the relation of subsequently produced hypotheses. Hence, it is only natural to ask whether or not thisknowledge suffices to learn iteratively, too. As we will see, the answer to this question
heavily depends on the monotonicity constraint involved as well as on the class ofadmissible hypothesis spaces.
Theorem 21. EM ON −T XT \ CIT −T XT 6= ∅Proof. Let L1 = {a}∗ and Lk,n = {az z ≤ k} ∪ {az z ≥ n} ∪ {bk , bn } ∪ {c} for allk, n ∈ IN, k, n > 1 and k + 2 < n. Finally, we set Lk,n,m = Lk,n \ {c} ∪ {am } for allk, n ∈ N as above and k < m < n. Then define L to be the collection of all L1 , Lk,nand Lk,n,m . It is not hard to prove that L ∈ EM ON −T XT . The following weaknessof iterative learners will be exploited to prove L 6∈ CIT − T XT . Suppose to thecontrary that an iterative IIM M yields successful inference. Let t be any text for L1 .
Since M has to infer L1 , it has to reach a point of stabilization, i.e., after this point M
has to repeat its last guess, no matter which string s ∈ L1 is actually presented. Let
ak be the longest string M has fed before reaching the point of stabilization. Lateron, M has no chance to deduce from its last hypothesis whether or not a particularstring s ∈ L1 has been fed to it. But this is necessary to distinguish, for instance,
between the languages Lk,k+3,k+1 and Lk,k+3,k+2 . Hence, M is fooled.
q.e.d.
The latter theorem directly yields the following consequence. Monotonic as wellas weak-monotonic inference with iterative IIMs is less powerful than with ordinary
machines.
Corollary 22. Let λ ∈ {E, ε, C}. Then we have:(1) λM ON −IT −T XT ⊂ λM ON −T XT(2) λWM ON −IT −T XT ⊂ λWM ON −T XT
Next, we study strong-monotonic inference performed by iterative IIMs. As ournext theorem shows, there is a peculiarity. Namely, class comprising strong-monotonic
inference from positive data is precisely as powerful as class comprising strong-monotonic and iterative learning. Moreover, class comprising hypothesis spaces are inevitable to achieve this equality.
Theorem 23.
(1) ESM ON −IT −T XT ⊂ ESM ON −T XT(2) SM ON −IT −T XT ⊂ SM ON −T XT(3) CSM ON −IT −T XT = CSM ON −T XTProof. First, we show (1) and (2). It suffices to present an indexed family L =(Lj )j∈IN witnessing ESM ON −T XT \ SM ON −IT −T XT 6= ∅. Let L denote any
canonical enumeration of all finite languages over Σ = {a} which does not containthe singleton languages {a} and {aa}.
Obviously, L ∈ ESM ON−T XT . The main reason for L ∈/ SM ON−IT−T XT canbe described as follows. Suppose, M is initially fed the string a. Then, M may either
41remain in its initial stage or it may guess a language L from L. However, the lattercannot be done without violating the strong-monotonicity constraint, since L 6= {a}for all L ∈ L. The same argument applies when M is initially fed the string aa.
Hence, in both cases M is forced to maintain its initial stage. But this implies thatM guesses the same sequence of hypotheses when successively fed t = a, a3 , a3 , . . .
and t̂ = aa, a3 , a3 , . . ., respectively. Consequently, M fails to infer at least one of
the corresponding finite languages L = {a, a3 } and L̂ = {aa, a3 } in the sense of
SM ON −IT −T XT , respectively.
Next, we prove Assertion (3). Let M strong-monotonically infer L with respect to aclass preserving space of hypotheses G. Without loss of generality, we may assume that
M outputs in every step a consistent hypothesis (cf. Lange and Zeugmann (1993a)).
First, we define another strong-monotonic IIM M̂ which infers L. In doing so, wechoose the hypothesis space Ĝ which is obtained from G by enumerating its closure
with respect to finite unions. Now, let L ∈ L and t = s0 , s1 , . . . be any text for L.

M̂ (tx ) = “If x = 0, compute M (t0 ) = j. Output, the canonical index ̂0 of L(Gj ) inĜ. Otherwise, execute Instruction (A).
(A) Let ̂k = M̂ (tx ). If sx ⊆ L(Ĝ̂k ), repeat the hypothesis ̂k . Otherwise, goto
(B).
(B) Compute the initial segment t̂z of the lexicographically ordered text ofL(Ĝ̂k ) which contains all strings being smaller than sx with respect tothe underlying lexicographical ordering. Compute j = M (t̂z , sx ). Output
the canonical index of the language L(Ĝ̂k ) ∪ L(Gj ) in Ĝ.”
By definition, L(Ĝ̂k ) ⊆ L(Ĝ̂k+1 ) for every k ∈ IN. Thus, M̂ works strongmonotonically, too. Moreover, M̂ exclusively produces consistent hypotheses, because
M is a consistent IIM. When fed any initial segment tx of any text for L, M always
outputs a guess j such that L(Gj ) ⊆ L. Obviously, the same statement is true, if tx
is an initial segment of a text for any of L’s sublanguages. Now, taking M̂ 0 s definition into account it can be easily verified that M̂ never outputs an overgeneralized
hypothesis.
It remains to show that M̂ infers L from text t. Since M̂ exclusively performs
justified mind changes, it suffices to show that M̂ outputs once a correct hypothesis.
This happens trivially, if L is a finite language, since M̂ is a consistent IIM. Otherwise,
let L be infinite. In order to verify that M̂ succesfully handles this case, too, one has
to take into consideration that M , in particular, strong-monotonically infers L fromits lexicographically ordered text tL . (Note that this assumes that L is infinite.) Thus,
M (tLx ) = j with L(Gj ) = L for some x ∈ IN. On the other hand, t is a text for L.
Hence, there is a least y ∈ IN such that range(tLx ) ⊆ t+
y . Moreover, M̂ (ty ) = ̂y withrange(tLx ) ⊆ L(Ĝ̂y ). If L = L(Ĝ̂y ), we are done. Otherwise, L(Ĝ̂y ) ⊂ L. Then,
there exists a least r ∈ IN such that sy+r 6∈ range(tLx ). Since range(tLx ) ⊆ L(Ĝ̂y ) ⊂ L,
the string sy+r forces M̂ to compute an extension of L’s lexicographically ordered text
having the initial segment tLx . Taking again M̂ ’s definition into account it follows thatM̂ (ty+r ) = ̂y+r with L(Gj ) ⊆ L(Ĝ̂y+r ). Since M̂ avoids overgeneralization, we are
done.
42

Finally, a closer look to the definition of M̂ shows that, when fed tx , M̂ ’s output
depends only on its last guess ̂x−1 and the actual string sx . Consequently, M̂ witnesses
L ∈ CSM ON −IT −T XT .
q.e.d.
Finally, we summarize the corresponding results concerning monotonic inference
from positive and negative examples (cf. Lange and Zeugmann (1992)).
Theorem 24. Let λ ∈ {E, ε, C}. Then we have:(1) λM ON −IT −IN F ⊂ λM ON −IN F(2) λWM ON −IT −IN F ⊂ λWM ON −IN F
Furthermore, concerning strong-monotonic learning the following theorem can beproved. Thereby, the same idea already used in the demonstration of Theorem 23
applies mutatis mutandis.
Theorem 25.
(1) ESM ON −IT −IN F ⊂ ESM ON −IN F(2) SM ON −IT −IN F ⊂ SM ON −IN F
Up to now, it remains open whether class comprising strong-monotonic inference
from informant can be performed by iterative IIMs without limiting learning power.

7. Trading Monotonicity Constraints Versus Efficiency
This section deals with the efficiency of learning. The measure of efficiency we use is
the number of mind changes an IIM is allowed to perform. Starting with the pioneering
paper by Barzdin and Freivalds (1972) this measure of efficiency has been intensively
studied (cf., e.g., Barzdin, Kinber and Podnieks (1974), Barzdin and Freivalds (1974),
Case and Smith (1983), Wiehagen, Freivalds and Kinber (1984)). However, all thementioned papers considered the learnability of recursive functions. Hence, it is only
natural to ask whether or not this measure of efficiency is of equal importance in thesetting of language learning. This is indeed the case as recently obtained results show.
Therefore, we continue with a short survey that comprises relevant results concerning
the inferability of indexed families. Mukouchi (1992) considered exact learning from
both, text and informant, and established the following hierarchies:
ELIM0 −T XT ⊂ ELIM1 −T XT ⊂ ... ⊂ELIM0 −IN F ⊂ ELIM1 −IN F ⊂ ... ⊂SSn∈IN ELIMn −T XT ⊂ ELIM∗ −T XTn∈IN ELIMn −IN F ⊂ ELIM∗ −IN F

Subsequently, in Lange and Zeugmann (1993b) we extended the latter result tothe class preserving case. Moreover, we considered the problem whether or not information presentation can always be traded versus efficiency, and obtained ELIMn+1 −T XT \ LIMn −IN F 6= ∅ for all n ∈ IN as well as ELIM1 −IN F \ LIM −T XT 6= ∅.
Furthermore, we studied the influence of an appropriate choice of the hypothesis space43

on the efficiency of learning. As it turned out, at least one mind change can be saved
provided the right hypothesis space is used. Recently, Lange (1994) sharpened thelatter result in the strongest possible way for learning from text as well as from informant, thereby, handling class comprising learning, too. Finally, we additionallysucceeded to characterize LIMn −T XT and LIMn −IN F in terms of uniformly generable recursive finite tell-tales (cf. Lange and Zeugmann (1993b) as well as Theorem3) and M. Sato extended this result to exact learning (cf. Mukouchi (1994)).
Discussing some of the results outlined above, Kinber (1992) proposed the followinginteresting problem.
Does any of the monotonicity constraints defined in Section 2 influence the efficiency of learning?
Clearly, this question is directly related to the problem how a natural learningalgorithm might look like. In particular, it is well imaginable that one may succeed indesigning a learning algorithm that fulfills a desirable monotonicity demand. However,it seems to be interesting to know what price one might have to pay concerning
the resulting efficiency. Therefore, we study the influence of different monotonicity
constraints to the number of mind changes an IIM has to perform when inferring atarget indexed family. Then, the right question to ask is whether a weakening of themonotonicity requirement may yield a speed-up. A partial answer to this problem
can already be found in Lange, Zeugmann and Kapur (1992). There it has beenshown that CWM ON d−T XT = CLIM−T XT . However, the construction presented
uniformly transforms any IIM that learns a target indexed family in the limit into one
that fulfills the dual weak-monotonicity constraint. But the price paid is high. The
dual weak-monotonic learner may be forced to change its mind twice as often thanthe original IIM (cf. Section 5, Theorem 15). It is open whether or not this bound istight. Furthermore, Lange, Zeugmann and Kapur (1992) presents results showing thatindexed families learnable with an a priori fixed number of mind changes under somemonotonicity constraint can become non-inferable at all if the monotonicity demandis strengthened.
Our approach below deals with a problem of higher granularity. We always startwith a target indexed family inferable under some monotonicity constraint with ana priori fixed number of mind changes. Then we ask whether or not the least or
some possible relaxation of the corresponding monotonicity requirement might help
to uniformly reduce the number of mind changes. As we shall see, there is no uniqueanswer to this problem. Finally, in the following we restrict ourselves to consider
learning from positive data and incorporate the number of mind changes into thedefinition of all types of monotonic learning in the same way as it has been done in
Definition 3. The resulting learning types are denoted by λSM ONn−T XT , λM ONn−
T XT and λWM ONn −T XT , where n ∈ IN ∪ {∗}, and λ ∈ {C, ε, E}.

7.1. Strong-Monotonic Inference
We start our investigations with the strongest possible monotonicity constraint, i.e.,with SM ON −T XT and its variations. Note that it does not make sense to consider
ESM ON d −T XT or SM ON d −T XT , since SM ON d −T XT = EF IN −T XT , andhence, there is nothing to speed-up. Moreover, in the following we exclusively consider
44

the case where at least one mind change is mandatory, since otherwise finite learning
is compared with some type of monotonic learning.
Theorem 26. Let L be an indexed family. Then, for every n ∈ IN+ we have:(1) L ∈ ESM ONn+1 −T XT \ ESM ONn −T XT implies L 6∈ CLIMn −T XT ,(2) L ∈ SM ONn+1 −T XT \ SM ONn −T XT implies L 6∈ CLIMn −T XT .
Proof. The proof is based on the following observations.
(A) Any strong-monotonically working IIM M̂ can be simulated by a consistent,
conservative, and strong-monotonic IIM M that performs at most as many
mind changes than M̂ does (cf. Lange and Zeugmann (1993a)).
(B) Let L be any indexed family with L ∈ ESM ONn+1 −T XT \ ESM ONn −T XT .
Furthermore, let L ∈ ESM ONn+1−T XT be witnessed by M , where M is chosenin accordance with (A). Since L 6∈ ESM ONn −T XT , there has to be an L ∈ L
and a text t for L such that M changes its mind exactly n + 1 times when fed
t. Let j0 , . . . , jn+1 denote the finite sequence of M ’s mind changes producedon t. Since M is strong-monotonic and conservative, we directly obtain that
Lj0 ⊂ · · · ⊂ Ljn+1 = L.
Now, L 6∈ CLIMn −T XT is a direct consequence of Proposition 3.7 by Mukouchi(1994). Applying the same arguments, one easily proves Assertion (2).
q.e.d.
The latter theorem allows the following interpretation. Relaxing the requirement
to learn exactly (class preservingly) strong-monotonically as much as possible does notincrease the efficiency. This is even true, if we are allowed to choose an arbitrary classcomprising hypothesis space provided that the target indexed family is inferable inthe sense of ESM ONn+1−T XT (SM ONn+1−T XT ), but cannot be class preservingly
and strong-monotonically learned with at most n mind changes for some n ∈ IN.

Next we consider the class comprising case. Interestingly enough, now the topological argument used above does not apply any more. The following theorem showsthat a suitable choice of the hypothesis space may increase the efficiency of learning,
even under the strong-monotonicity constraint.
Theorem 27. For every n ∈ IN+ there exists an indexed family L such that
(1) L ∈ CSM ONn+1 −T XT \ CSM ONn −T XT ,(2) L ∈ ELIMn −T XT .

Proof. First we prove the n = 1 case. Moreover, we use this case to fully explain
the basic proof technique developed. The first idea is to incorporate a non-recursive
but recursively enumerable problem in the definition of the target indexed family.
Note that this incorporation has to be done in a way such that membership in theenumerated languages remains uniformly decidable. For that purpose, we used thehalting problem. Without loss of generality, we may assume that Φj (j) ≥ 1 for allj ∈ IN.

The desired indexed family is defined as follows. Let k, j ∈ IN. We set L3hk,ji ={ak bz z ∈ IN+ }. The remaining languages will be defined as follows.
45

Case 1. ¬Φk (k) ≤ j

Then we set L3hk,ji+1 = L3hk,ji+2 = L3hk,0i .
Case 2. Φk (k) ≤ j

Let m = Φk (k). Now we set L3hk,ji+1 = {ak bz 1 ≤ z ≤ m} ∪ {ak cm }, andL3hk,ji+2 = L3hk,0i ∪ {ak dm }.

Since the predicate “Φi (x) = y” is uniformly decidable for all i, x, y ∈ IN, it is easy
to see that L = (Lz )z∈IN is an indexed family. Whenever Φk (k) ↓, the main problem forany strong-monotonic IIM consists in learning the finite language L3hk,Φk (k)i+1 with at
most one mind change. Hence, for proving L ∈ CSM ON2 −T XT , another ingredientis required, i.e., a suitable choice of a hypothesis space (cf. Claim A). The harder partis to show that L ∈/ CSM ON1 −T XT . As long as only class preserving hypothesis
spaces are allowed, it is intuitively obvious that any IIM M strong-monotonicallylearning L has to solve the halting problem. However, we have additionally to showthat no choice of the hypothesis space may prevent M to recursively handle thehalting problem. This part of the proof exploits to a larger extend the assumptionthat membership is uniformly decidable (cf. Claim C).
We continue with the formal proof.
Claim A. L ∈ CSM ON2 −T XT .

First of all we define a suitable hypothesis space L̃ = (L̃i )i∈IN . For all k, j ∈ IN andz ∈ {0, 1, 2}, we set:( T
if j = 0,j∈IN L3hk,ji+1 ,L̃3hk,ji+z =L3hk,j−1i+z ,otherwise.
It is not hard to see that L̃ is indeed an indexed family. Now we define an IIM M
which strong-monotonically identifies L with respect to L̃.
Let L ∈ L, let t be any text for L, and let x ∈ IN.

M (tx ) = “Determine the unique k such that ak bz ∈ t+
x for some z ∈ IN. Test whether
⊆
L̃
.
In
case
it
is,
output3hk,
0i.
Otherwise, goto (A).
or not t+
3hk,0ix(A) Compute m = max{z ak bz ∈ L̃3hk,0i )}. In case that ak cm ∈ t+
x , output
3hk, mi + 1. Otherwise, goto (B).
(B) If ak dm ∈ t+
x , then output 3hk, mi + 2. Else, output 3hk, 1i.”
Now, one straightforwardly verifies that M CSM ON2−T XT –learns L. This proves
Claim A.
Before showing the second part of Assertion(1), we prove Assertion(2).
Claim B. L ∈ ELIM1 −T XT .

The desired IIM is defined as follows. Let L ∈ L, let t be any text for L, and letx ∈ IN. We define:
M (tx ) = “Determine the unique k such that ak bz ∈ t+
x for some z ∈ IN. Test whether+
or not tx ⊆ Lhk,0i . In case it is, output 3hk, 0i. Otherwise, goto (A).
46

(A) Compute m = Φk (k). In case that ak cm ∈ t+
x , output 3hk, mi + 1. Otherwise, output 3hk, mi + 2.”
It remains to show that M infers L in the sense of ELIM1−T XT . By construction, if
M performs a mind change, then it has detected an inconsistency. But in accordancewith the definitions of L and M , t+
x 6∈ L3hk,0i can happen if and only if Φk (k) is defined.
Hence, the IIM may compute m = Φk (k). By construction, only two cases are possible,
i.e., either L contains ak cm or it comprises ak dm . Looking at the definitions of M and
L it directly follows that M ’s second guess is correct. Hence, M ELIM1−T XT –infers
L. This proves Claim B.
Claim C. L ∈/ CSM ON1 −T XT .

Suppose, there are a class comprising hypothesis space G for L, and an IIM M
witnessing L ∈ CSM ON1−T XT with respect to G. Then M may be used to design aneffective procedure solving the halting problem for the programming system ϕ0 , ϕ1 , ....
This can be seen as follows.
Procedure HALT“Let k ∈ IN, and let t be the canonical text for L3hk,0i . For x = 0, 1, ..., compute
M (tx ) until the minimal index z is found such that M , on successive input tz outputs
its first guess, say j. Test whether or not Φk (k) ≤ z + 1. In case it is, output ϕk (k) ↓.
Otherwise, output ϕk (k) ↑.”First, we show that HALT is an effective procedure. In particular, M has to infer
L3hk,0i from t. Hence, there is a z such that M on input tz computes a hypothesis j.
Hence, HALT is recursive and terminates for all k ∈ IN.

It remains to show that HALT correctly works. Obviously, if the output is ϕk (k) ↓,then ϕk (k) is indeed defined. Suppose, HALT outputs ϕk (k) ↑ but ϕk (k) is defined.
Hence, Φk (k) is defined, too. Let m = Φk (k). By construction, m > z + 1. Since M
is a strong-monotonic IIM, one easily verifies that L(Gj ) 6∈ L. Furthermore, M has
to infer L3hk,0i from its canonical text. Hence, there has to be an y > z such that
M (ty ) = r and L(Gr ) = L3hk,0i . Therefore, M performs at least one mind change
when seeing ty . Finally, due to our construction, there is a language L0 ∈ L such that
0
0
0
k m
t+
y ⊆ L and L 6= L3hk,0i , namely L = L3hk,0i ∪ {a d }. Consequently, ty may be
0extended to a text for L on which M has to perform an additional mind change, acontradiction.
The cases n > 1 may be proved using the same “lifting” technique as in Lange andZeugmann (1993b) (cf. proof of Theorem 11).
q.e.d.
At this point it is only natural to ask whether the latter theorem generalizes toall indexed families from CSM ONn+1 − T XT \ CSM ONn − T XT not belonging to
SM ON−T XT . As we show, removing the requirement to learn strong-monotonicallydoes not necessarily lead to a speed-up with respect to the number of mind changes.
Theorem 28. For all n ∈ IN, there exists an indexed family L such that
(1) L ∈ CSM ONn+1 −T XT \ CSM ONn −T XT ,(2) L 6∈ SM ON −T XT ,(3) L 6∈ ELIMn −T XT .
47

Proof. We consider the following indexed family L = (Lk )k∈IN . For all k ∈ IN wedefine L2k = {ak bj j ∈ IN+ } and L2k+1 = {ak bj 1 ≤ j ≤ Φk (k)}∪{cΦk (k) }. Note thatthe set {cΦk (k) } is defined to be empty, if Φk (k) diverges. Then it is easy to show that
L ∈ CSM ON1 −T XT \ SM ON −T XT . On the other hand, one straightforwardly
verifies that L cannot be finitely inferred. Again, an easy application of the same
“lifting” technique as in Lange and Zeugmann (1993b) directly yields the Theorem
for all n ∈ IN.
q.e.d.
Theorem 28 directly yields the problem whether or not Theorem 27 can be strengthened, i.e., whether or not the number of mind changes that can be traded versus thestrong-monotonicity constraint is bounded by one. The answer is provided by ournext theorem.
Theorem 29. For every n ∈ IN+ there exists an indexed family L such that
(1) L ∈ CSM ONn+1 −T XT \ CSM ONn −T XT ,(2) L ∈ EM ON1 −T XT .
Proof. We restrict ourselves to present the case n = 2, since it suffices to explain
the proof technique developed. The main idea is to suitably iterate the proof techniquepresented in the demonstration of Theorem 27. Therefore, we incorporate one morehalting problem into the definition of the indexed family L witnessing L ∈ CSM ON3−
T XT \ CSM ON2 −T XT , and L ∈ ELIM1 −T XT . This is done as follows. Without
loss of generality, we may assume that Φj (j) ≥ 1 for all j ∈ IN. We define:L4hk1 ,k2 ,ji = {ahk1 ,k2 i bz z ∈ IN+ } for all k1 , k2 , j ∈ IN. In order to define theremaining languages of L we distinguish the following cases.
Case 1. ¬Φk1 (k1 ) ≤ j

Then we set L4hk1 ,k2 ,ji+1 = L4hk1 ,k2 ,ji+2 = L4hk1 ,k2 ,ji+3 = L4hk1 ,k2 ,0i .

Case 2. Φk1 (k1 ) ≤ j

Then, let ` = Φk1 (k1 ), and set L4hk1 ,k2 ,ji+1 = {ahk1 ,k2 i bz 1 ≤ z ≤ `} ∪ {ahk1 ,k2 i c` }.
Furthermore, we distinguish the following subcases.
Subcase 2.1. ¬Φk2 (k2 ) ≤ j

Then let L4hk1 ,k2 ,ji+2 = L4hk1 ,k2 ,ji+3 = L4hk1 ,k2 ,0i .

Subcase 2.2. Φk2 (k2 ) ≤ j

Let ` = Φk1 (k1 ), and m = Φk2 (k2 ).
We set L4hk1 ,k2 ,ji+2 = {ahk1 ,k2 i bz 1 ≤ z ≤ ` + m} ∪ {ahk1 ,k2 i d`+m }, andL4hk1 ,k2 ,ji+3 = L4hk1 ,k2 ,0i ∪ {ahk1 ,k2 i e`+m }.

Now, it is easy to see that L = (Lz )z∈IN constitutes an indexed family. It remains
to show that L fulfills the stated requirements. This is done by the following lemmata.
Lemma 1. L ∈ EM ON1 −T XT .

An IIM M witnessing L ∈ ELIM1−T XT can be easily defined. Initially, it outputs
4hk1 , k2 , 0i. As long as this guess is consistent, it is repeated. Otherwise, M reads
one of the following strings ahk1 ,k2 i c` , ahk1 ,k2 i d`+m or ahk1 ,k2 i e`+m . These strings serve
as a label as the definition of L shows. Therefore, M can change its mind to a correct48

hypothesis which it repeats subsequently. Moreover, it is easy to see that the possible
mind change satisfies the monotonicity requirement. This proves the lemma.
Lemma 2. L ∈ CSM ON3 −T XT .

The wanted hypothesis space G = (Gj )j∈IN is defined to be a canonical enumeraTtion of all languages of L and all languages L̂4hk1 ,k2 i+1 = j∈IN L4hk1 ,k2 ,ji+1 as well asTL̂4hk1 ,k2 i+2 = j∈IN L4hk1 ,k2 ,ji+2 for all k1 , k2 ∈ IN. We suppress the technicalities andrefer to hypotheses in G as to canonical numbers of the corresponding languages.
The desired IIM M is defined as follows. Let L ∈ L, t ∈ text (L), and x ∈ IN. We
define:M (tx ) = “If ahk1 ,k2 i c` ⊆ t+
x output the canonical number of L4hk1 ,k2 ,`i+1 .
If ahk1 ,k2 i d`+m ⊆ t+
x output the canonical number of L4hk1 ,k2 ,`+mi+2 .
hk1 ,k2 i `+m+
If ae⊆ tx output the canonical number of L4hk1 ,k2 ,`+mi+3 .
hk1 ,k2 i z
Otherwise, i.e., if t+
b z ∈ IN+ }, test successively whether or not thex ⊆ {acanonical number for L̂4hk1 ,k2 i+1 , or L̂4hk1 ,k2 i+2 or L4hk1 ,k2 ,0i is consistent. Output
the first consistent hypothesis.”
The definitions of L and G directly imply that M satisfies the strong-monotonicity
constraint. Moreover, it is easy to see that M learns L with respect to G. Hence,
it remains to show that three mind changes are sufficient. Obviously, the worst caseoccurs when M is forced to output successively the canonical numbers for L̂4hk1 ,k2 i+1 ,L̂4hk1 ,k2 i+2 and L4hk1 ,k2 ,0i before seeing ahk1 ,k2 i e`+m . However, even in this case M
performs precisely three mind changes. This proves the lemma.
The remaining part, i.e., L ∈/ CSM ON2 − T XT , is much harder to prove. The
critical part is to show that any IIM which strong-monotonically infers L has to beat least as careful, when fed a text for L4hk1 ,k2 ,0i , as the IIM M provided in Lemma 2.
For that purpose we need some additional insight into the behavior of every IIM thatstrong-monotonically learns L. In particular, we are mainly interested in knowing
how every IIM inferring L strong-monotonically behaves when successively fed thelexicographically ordered text for L4hk1 ,k2 ,0i . The desired information is provided by
the following lemma.
Lemma 3. Let G = (Gj )j∈IN be any class comprising hypothesis space for L and
let M be any IIM witnessing L ∈ CSM ON −T XT with respect to G. Then we have:
For all k2 there are numbers k1 , x, j ∈ IN such that
(1) M (tx ) = j,(2) Φk1 (k1 ) > x + 1 and ϕk1 (k1 ) ↓,where t is the lexicographically ordered text of L4hk1 ,k2 ,0i .
Suppose the converse. Then there is a k2 such that for all k1 , x, j we have: M (tx ) =j implies Φk1 (k1 ) ≤ x + 1 or Φk1 (k1 ) ↑.
Assuming the latter statement we have the following claim.

Claim. Provided the latter statement is true, any program for M may be used toobtain non-effectively an algorithm deciding “ϕk1 (k1 ) ↓.”49

By assumption, there is a k2 such that for all k1 , x, j: If (1) is fulfilled, then eitherΦk1 (k1 ) ≤ x + 1 or Φk1 (k1 ) ↑. Using this k2 we can define the following algorithm A.
Algorithm A: “On input k1 execute (A1) and (A2).
(A1) Generate successively the lexicographically ordered text t of L4hk1 ,k2 ,0i andsimulate M until the first hypothesis j is produced.
Let x0 be the least x such that M (tx ) = j.
(A2) Test whether Φk1 (k1 ) ≤ x0 + 1.
In case it is, output “ϕk1 (k1 ) ↓.”Otherwise, output “ϕk1 (k1 ) ↑” and stop.”
First we observe that M has to infer L4hk1 ,k2 ,0i from its lexicographically ordered
text t. Hence, M should eventually output a hypothesis j when fed t. Furthermore,
Instruction (A2) can be effectively accomplished, too. Hence, A is an algorithm andthe execution of (A1) and (A2) must eventually terminate. Finally, by assumption
we immediately obtain the correctness of A’s output. This proves the claim. Since
the halting problem is algorithmically undecidable, the lemma follows.
Lemma 4. L ∈/ CSM ON2 −T XT .

Suppose the converse, i.e., there exist a hypothesis space G = (Gj )j∈IN and an IIM
M that CSM ON2−T XT –learns L with respect to G. Then we can prove the following
lemma.
Lemma A. Given any hypothesis space G = (Gj )j∈IN and any program for M witnessing L ∈ CSM ON2 − T XT , one can effectively construct an algorithm deciding
whether or not “ϕk2 (k2 ) ↓.”Let K = {k ϕk (k) ↓} and let j0 , j1 , j2 , ... be any fixed effective enumeration of K.
We define an algorithm A as follows.

Algorithm A: “On input k2 execute (A1) and (A2).
(A1) For z = 0, 1, 2, ... successively compute the lexicographically ordered
texts tj0 , tj1 , tj2 , ... for L4hj0 ,k2 ,0i , L4hj1 ,k2 ,0i , ..., L4hjz ,k2 ,0i of length z + 1,
respectively. Then, dovetail the simulation of M on successive input ofeach of these initial segments until the first initial segment tjxr (r, x ≤ z)
and the first hypothesis j are found such that(α1) M (tjxr ) = j,(α2) Φjr (jr ) > x + 1.
(* By Lemma 3, the execution of (A1) has to terminate *)(A2) Let f =df hjr , k2 i and ` = Φjr (jr ). Furthermore, we define t̂`+y as follows:t̂`+y = af b, ..., af bx+1 , ..., af b` , af b` , af b`+1 , ..., af b`+y
|
|
{z
}
{z
}
y−stringsr=tj`−1For y = 0, 1, 2, ... execute in parallel (β1) and (β2) until (β3) or (β4)
happens.

(β1) Test whether Φk2 (k2 ) ≤ ` + y.
50

(β2) Compute j`+y = M (t̂`+y ).
(β3) Φk2 (k2 ) ≤ ` + y is verified. Then output “ϕk2 (k2 ) ↓.”(β4) In (β2) a hypothesis j`+y = M (t̂`+y ) is computed such that af b`+1 ∈L(Gj`+y ). Then output “ϕk2 (k2 ) ↑” and stop.”
It remains to show that A terminates on every input, and behaves correctly.
Claim 1. On every input k2 , the algorithm A terminates.

As we have already mentioned, by Lemma 3 we know that the execution of (A1)
has to terminate. Hence, it suffices to show that either (β3) or (β4) happens. Suppose,(β3) does not happen. Then, for all y ∈ IN we have ¬Φk2 (k2 ) ≤ ` + y. Consequently,Φk2 (k2 ) ↑. Therefore, when y tends to infinite, then t̂`+y converges to a text forL4hjn ,k2 ,0i , and hence, M eventually has to output a hypothesis j`+y such that af b`+1 ∈L(Gj`+y ). Thus, (β4) must happen. This proves the claim.
Claim 2. Algorithm A works correctly.

Obviously, if (β3) happens then ϕk2 (k2 ) is indeed defined. Suppose, (β4) happens.
We have to show that ϕk2 (k2 ) ↑. Suppose the converse, i.e., ϕk2 (k2 ) ↓. Thus, Φk2 (k2 )converges, too. We distinguish the following cases.
Case 1. The hypothesis j`+y satisfies L(Gj`+y ) = L4hjr ,k2 ,0i .
Then M fails to infer L4hjr ,k2 ,Φjr (jr )+Φk2 (k2 )i+2 strong-monotonically. This can beseen as follows. Since (β3) did not happen, we have Φk2 (k2 ) > ` + y. Hence, t̂`+y is
an initial segment of a text for L4hjr ,k2 ,0i and of a text t̃ for L4hjr ,k2 ,Φjr (jr )+Φk2 (k2 )i+2 .
On the other hand, when successively fed t̃, the IIM M sometimes outputs j`+y , andL(Gj`+y ) = L4hjr ,k2 ,0i . Since L4hjr ,k2 ,0i 6⊆ L4hjr ,k2 ,Φjr (jr )+Φk2 (k2 )i+2 , we directly see that
M violates the strong-monotonicity constraint.
Case 2. The hypothesis j`+y does not satisfy L(Gj`+y ) = L4hjr ,k2 ,0i .
Then, M fails to learn L with at most two mind changes. Recall that M has
already generated the guesses j and j`+y when successively fed t̂`+y . First, we showthat j 6= j`+y . Suppose to the contrary that j = j`+y . Remember that ` = Φjr (jr ).
Then M fails to infer L4hjr ,k2 ,`i+1 strong-monotonically. This can be seen as follows.
By construction, af b`+1 ∈ L(Gj`+y ), and hence, af b`+1 ∈ L(Gj ). But j = M (tjxr ), andx < `. Therefore, tjxr is an initial segment of some text for L4hjr ,k2 ,`i+1 , too. On theother hand, af b`+1 6∈ L4hjr ,k2 ,`i+1 . Consequently, L(Gj ) 6⊆ L4hjr ,k2 ,`i+1 , a contradiction.

Finally, since j 6= j`+y , M has already performed at least one mind change whensuccessively fed t̂`+y . Hence, t̂`+y is an initial segment of a text for L4hjr ,k2 ,0i as
well as for L4hjr ,k2 ,`+Φk2 (k2 )i+3 . In accordance with L’s definition we additionally haveL4hjr ,k2 ,0i ⊂ L4hjr ,k2 ,`+Φk2 (k2 )i+3 . Thus, we may extend t̂`+y with af b`+y+1 , af b`+y+2 , ...
until M learns L4hjr ,k2 ,0i . This forces M to change its mind again. Afterwards, we
present af e`+Φk2 (k2 ) , and hence, one more mind change has to occur. Thus, L ∈/CSM ON2 −T XT . This contradiction proves Claim 3. Thus, Lemma 4 is shown, andthe theorem follows.
q.e.d.
Note that the proof of the latter theorem directly allows the following corollary.
Corollary 30. EM ON1 −T XT \ SM ON −T XT 6= ∅.

Proof. The indexed family L defined above belongs to ELIM1 −T XT . Hence, we
51

have to argue that L 6∈ SM ON −T XT . This is a direct consequence of Lemma 3 in
the above proof.
q.e.d.
In the next subsection we study monotonic inference.

7.2. Monotonic InferenceThis subsection deals with monotonic inference, and possible relaxations of themonotonicity requirement. But there is a peculiarity which we point out with thefollowing theorem.
Theorem 31. λLIM1 −T XT = λM ON1 −T XT for all λ ∈ {E, ε, C},

Proof. Let L be any indexed family such that L ∈ λLIM1 − T XT , where λ ∈{E, ε, C}. Hence, there are a hypothesis space G = (Gj )j∈IN and an IIM M that
λLIM1 −T XT –infers L with respect to G. Consequently, when fed any text of any
language L ∈ L the IIM M performs at most one mind change. Suppose, first M
outputs k, and then it changes its mind to j. Hence, j has to be a correct guess for L,
i.e., we have L = L(Gj ). Therefore, we directly obtain L(Gk ) ∩ L ⊆ L(Gj ) ∩ L = L.
Hence, M monotonically infers L.
q.e.d.
Next we show that the monotonicity constraint can be traded versus efficiency.
This is even true, if the relaxation is as weak as possible, i.e., if the requirement tolearn monotonically is relaxed to weak-monotonic inference.
Theorem 32. For every n ∈ IN, n ≥ 2, there exists an indexed family such that
(1) L ∈ M ONn+1 −T XT \ M ONn −T XT ,(2) L ∈ EWM ONn −T XT .
Proof. For the sake of presentation, we consider the case n = 2. The extension
to all n ≥ 3 may be easily obtained by applying the lifting technique of Lange andZeugmann (1993b). The desired indexed family is defined as follows. For all k ∈ IN,
we set L4k = {ak bz z ∈ IN+ } and L4k+1 = L4k ∪ {bk a}. In order to define theremaining languages we distinguish the following cases:
Case 1. Φk (k) ↑Then we set L4k+2 = L4k+3 = L4k+1 .
Case 2. Φk (k) ↓Then, let m = Φk (k), and let L̂k = {ak bz 1 ≤ z ≤ m} ∪ {bk a}. We set L4k+2 =L̂k ∪ {ak cm }, and L4k+3 = L̂k ∪ {ak cm , ak dm }.

Obviously, L = (Lz )z∈IN is an indexed family of recursive languages. To see thistake into consideration that, for instance, ak bz ∈ L4k+2 iff Φk (k) ≥ z. But Φk (k) ≥ z
is uniformly decidable for any z, k ∈ IN.
Claim A. L ∈ EM ON3 −T XT .

We define the desired IIM M as follows. Let L ∈ L, let t be any text for L, andlet x ∈ IN.
k+
M (tx ) = “Determine the unique k such that ak bz ∈ t+
x for some m ∈ IN. If b a 6∈ tx
output 4k. Otherwise, goto (A).

52+(A) If ak dm ∈ t+x and tx ⊆ L4k+3 , then output 4k + 3.
+
If ak cm ∈ t+x and tx ⊆ L4k+2 , then output 4k + 2.
Otherwise, output 4k + 1.”

Obviously, M monotonically infers L. In the worst case, M changes its mind threetimes, namely it outputs successively the hypotheses 4k, 4k+1, 4k+2, and 4k+3. It iseasy to verify that each of these mind changes satisfies the monotonicity requirement.
Claim B. L ∈ EWM ON2 −T XT .

The desired IIM is defined as follows. Let L ∈ L, let t ∈ text (L), and let x ∈ IN.
+k+
M (tx ) = “Determine the unique k such that ak bz ∈ t+
x for some z ∈ IN . If b a 6∈ tx
output 4k. Otherwise, goto (A).

(A) If t+
x ⊆ L4k+2 output 4k + 2.
If ak dm ∈ t+
x output 4k + 3.
Otherwise, i.e., a string ak bz 6∈ L4k+2 occurred, output 4k + 1.”
Obviously, M weak-monotonically infers L. Thereby, M changes its mind at most
twice. This proves Claim B.
Note that the IIM M defined in the latter proof may subsequently output the
hypotheses 4k, 4k + 2, and 4k + 1 when fed a text for L4k+1 . It is easy to verify thatthe latter mind change violates the monotonicity requirement. Moreover, it is easy toargue that L 6∈ EM ON2 −T XT . But again, we show a slightly stronger result.
Claim C. L 6∈ M ON2 −T XT .

Claim C follows by contraposition of Lemma 1.
Lemma 1. Given any class preserving hypothesis space G and any program for an
IIM M witnessing L ∈ M ON2 −T XT with respect to G, one can effectively define a
total-recursive predicate ψ solving the halting problem.
Proof. Let k ∈ IN; the desired predicate ψ is defined as follows.
ψ(k) = “Let t be the lexicographically ordered text for L4k . For x = 0, 1, ..., compute
M (tx ) until the first index z is found such that j = M (tz ) satisfies ak b ∈ L(Gj ),and bk a 6∈ L(Gj ).

(A) For r = 1, 2, . . . simulate M , when fed the text t̂ = tz , bk a, ak b, ..., ak br
for L4k+1 , until the first index y is found such that jz+1+y = M (t̂z+1+y )satisfies bk a ∈ L(Gjz+1+y ).
(B) Test whether or not Φk (k) ≤ z + 1 + y. In case it is, output 1.
Otherwise, output 0.”

Since M has to infer the languages L4k as well as L4k+1 , it is easy to verify thatthe procedure defined above terminates for every k ∈ IN. Hence, ψ is total-recursive.
It remains to show that ϕk (k) is undefined, if ψ(k) = 0. Suppose the converse, i.e.,ψ(k) = 0 as well as ϕk (k) is defined. Therefore, Φk (k) = m > z + 1 + y.

Recall that M has already performed at least one mind change when fed t̂z+1+y ,namely from j to jz+1+y . Due to the definition of L, bk a 6∈ L(Gj ) together with ak b ∈53

L(Gj ) implies L(Gj ) = L4k . Since M monotonically infers L4k+1 from t̂ and bk a ∈L(Gjz+1+y ), we obtain L(Gjz+1+y ) = L4k+1 . Otherwise, M violates the monotonicity
constraint when inferring L4k+1 on its text t̂. Now, taking L’s definition into account,it follows that t̂z+1+y may also serve as an initial segment of a text for the language
L4k+2 because Φk (k) = m > z + 1 + y. Finally, since L4k+2 ⊂ L4k+3 , it is easy toverify that t̂z+1+y can be extended to a text for L4k+3 such that M has to perform
at least two additional mind changes in order to infer L4k+3 from this text. This
contradicts our assumption that M monotonically infers L with at most two mindchanges. Therefore, ϕk (k) is undefined, if ψ(k) = 0. Hence, the predicate ψ solves
the halting problem for the ϕ-system.
q.e.d.
Refining mutatis mutandis the latter proof analogously as the demonstration ofTheorem 27 has been extended to show Theorem 29, one obtains the following result.
Theorem 33. For every n ≥ 2 there exists an indexed family such that
(1) L ∈ M ONn+1 −T XT \ M ONn −T XT ,(2) L ∈ EWM ON2 −T XT .
The latter theorems allow the following interpretation. Removing the constraint tolearn monotonically may considerably increase the efficiency of the learning process.

7.3. Weak-Monotonic Learning
Finally, we consider weak-monotonic learning. Possible relaxations include dual
weak-monotonic learning as well as learning in the limit. However, much less isknown. First, Theorem 31 directly implies LIM1 −T XT = WM ON1 −T XT as wellas ELIM1 −T XT = EWM ON1 −T XT , since λM ON −T XT ⊂ λWM ON −T XT for
λ ∈ {E, ε}. On the other hand, it is even open whether or not CM ON1 − T XT ⊆CWM ON1 −T XT . Hence, showing CLIM1 −T XT = CWM ON1 −T XT requires aseparate proof that is still missing. Nevertheless, we succeeded to obtain results thatshed considerable light on the power of learning with at most one mind change.
Theorem 34.
(1) M ON1 −T XT \ EWM ON −T XT 6= ∅(2) ELIM2 −T XT \ WM ON −T XT 6= ∅(3) CM ON1 −T XT \ WM ON −T XT 6= ∅Proof. Lange and Zeugmann (1993b) proved LIM1 −T XT \ EWM ON −T XT 6= ∅,and recently Lange (1994) shows CLIM1 −T XT \ WM ON −T XT 6= ∅. Combining
these results with Theorem 31 we directly get Assertion (1) and (3). Finally, for a
proof of Assertion (2) we refer the reader to Lange (1994).
q.e.d.
Consequently, relaxing the weak-monotonicity constraint may considerably increase the inference capabilities.
We conclude this section with further problems that remain open. First of all, it
would be very interesting to answer the following question. Does there exist a k ∈ IN
54

such that CLIMk \ CWM ON 6= ∅? Of course, one should ask similar questions fordual monotonic and especially for dual weak-monotonic learning.
Furthermore, our results show that a relaxation of the corresponding monotonicity
demands sometimes yields a significant speed-up of the learning process. Hence, it
seems highly desirable to investigate necessary and sufficient conditions Ccsmon , Cmon ,and Cwmon allowing assertions of the following type.
Let LT as well as LT 0 be any learning type, and let L ∈ LT . Then one may learn
L more efficiently in the sense of LT’ if and only if Clt0 is satisfied but Clt is not.

Moreover, it would be very interesting to relate possible relaxations of our monotonicity requirements to problems studied in complexity theory. Recently, such an approach has been undertaken concerning consistent and inconsistent learning resulting
in a proof for the superiority of an inconsistent learning algorithm (cf. Wiehagen and
Zeugmann, 1994)). We will see what the future brings concerning these problems.

8. Degrees of Order Independence
In this section we study the question whether or not the order of information
presentation does really influence the capabilities of IIMs. Since an IIM is required
to learn the target language from every text (informant) for it, one may conjecturethat an IIM mainly extracts the range of the information fed to it, thereby neglecting
the length and order of the data sequence it reads. While this is true for learningfrom informant, the situation considerably changes for inference from positive data.
A first explanation for this phenomenon can be derived from the fact that, when fed
an informant, an IIM can decide whether or not is has already seen a complete initial
segment. Then it ignores all the other data fed to it, and behaves like an IIM learningfrom the lexicographically ordered informant. Clearly, when exclusively learning frompositive data, an IIM never knows whether it possesses a complete initial segment.
But this is only part of the story as we shall see. Next we define two modes of order
independence.
Definition 11. (Wexler and Culicover, 1980, Sec. 2.2) Let L be an indexedfamily. An IIM is said to be set-driven with respect to L iff its output depends
only onS the range of its input; that+is, iff+ M (tx ) = M (t̂y ) for all x, y ∈ IN, all textst, t̂ ∈ L∈range(L) text (L) provided tx = t̂y .

Schäfer-Richter (1984) as well as Fulk (1990), later, and independently proved that
set-driven IIMs are less powerful than unrestricted ones. Fulk (1990) interpreted theweakening in the learning power of set-driven IIMs by the need of IIMs for time to“reflect” on the input. However, this time cannot be bounded by any a priori fixedcomputable function depending exclusively on the size of the range of the input, sinceotherwise set-drivenness would not restrict the learning power. Indeed, Osherson,
Stob and Weinstein (1986) proved that any non-recursive IIM M may be replaced bya non-recursive set-driven IIM M̂ learning at least as much as M does. On the other
hand, the weakness of set-driven inference has been proved in a domain that allows
self-referential arguments. Since this proof technique does not apply in the settingof indexed families, the problem whether or not set-drivenness constitutes a severe
restriction in this domain remained open. But before starting our survey of results55

we consider a natural weakening of Definition 11.
Definition 12. (Schäfer-Richter, 1984; Osherson et al., 1986)) Let L be anindexed family. An IIM is said to be rearrangement-independent iff its output
depends only on the range andSon the length of its input; that is, iff M (tx ) = M (t̂x )+for all x ∈ IN, all texts t, t̂ ∈ L∈range(L) text (L) provided t+
x = t̂x .
We make the following convention. For all the learning models in this paper we
use the prefix s−, and r− to denote the learning model restricted to set-driven andrearrangement-independent IIMs, respectively. For example, s − LIM denotes thecollection of all indexed families that are LIM –inferable by some set-driven IIM.

Fulk (1990) proved that rearrangement-independence can be always achieved whenlearning in the limit is concerned. However, Fulk’s proof technique does not preserve
any of the monotonicity constraints defined in Section 2. On the other hand, the first
result concerning order-independence with respect to the inferability of indexed families goes back to Angluin (1980a). As already mentioned in Section 3 she characterized learning in the limit using families of recursively enumerable finite and non-empty
tell-tales. In particular, the IIM defined in the sufficiency part of her characterization
theorem establishes that rearrangement-independence does not constitute a restriction for ELIM (cf. Section 3, Example 5). In Lange and Zeugmann (1993b) weproved that ELIM = LIM = CLIM . Hence, learning in the limit can be always
achieved by rearrangement-independent IIMs. Inspired by Angluin’s (1980b) work wecharacterized conservative, monotonic, strong-monotonic, and finite learning in termsof recursive finite and non-empty tell-tales (cf. Lange and Zeugmann (1992)). These
results directly yield that r−EF IN = F IN , and r−SM ON = SM ON . However, allremaining questions required special attention. In the following subsection we survey
results concerning set-drivenness.

8.1. Learning with Set-driven IIMs
We start with finite learning. The next theorem in particular states that finite
learning is invariant with respect to the specific choice of the hypothesis space. Moreover, for every hypothesis space comprising the target indexed family L there is a
set-driven IIM that finitely learns L.
Theorem 35. EF IN = F IN = CF IN = s−EF IN

Proof. EF IN = F IN = CF IN is due to Lange and Zeugmann (1993c).
The main ingredient for the proof of EF IN = s−EF IN is the following characterization of finite learning (cf. Lange and Zeugmann (1992)).
Theorem 36. Let L be an indexed family. Then: L ∈ F IN −T XT if and only ifthere is a recursively generable family (Tj )j∈IN of finite non-empty sets such that(1) for all j ∈ IN, Tj ⊆ Lj ,(2) for all k, j ∈ IN, if Tk ⊆ Lj , then Lj = Lk .

Using this recursively generable family (Tj )j∈IN we define a IIM M witnessing
L ∈ s−EF IN −T XT . Let L ∈ L, t ∈ text(L), and x ∈ IN.

M (tx ) = “ If x = 0 or x > 0 and M when, fed successively tx−1 , does not stop, thenexecute stage x.
56+Stage x: Search for the least j such that t+x ⊆ Lj . Test whether or not Tj ⊆ tx .
In case it is, output j and stop.
Otherwise, request the next input and output nothing.”

We sketch only the idea behind the proof. The IIM defined above searches forthe first language that comprises t+
x . Since t is a text of some language from L,
this unbounded search terminates. Then M tests whether or not the relevant tell-talebelongs to the range of the initial text segment it has been fed. Hence, intuitively
it is clear that M is set-driven. It remains to show that M has to stop sometimes.
This part of the proof mainly exploits Property (2) of the tell-tale family. M might
fail to stop provided the first index j that is found by M is proper superset of thetarget language L and Tj 6⊆ L. But this is impossible, since then TL ⊆ Lj , where TL
is any tell-tale for the target language L. By Property (2) we conclude L = Lj , acontradiction.
For a formal proof of M s−EF IN −T XT –learns L the reader is referred to Lange
and Zeugmann (1993e).
q.e.d.
The proof sketch given above makes its clear why set-drivenness may constitute a
severe restriction. The main problem is just a suitable restriction of the actual search
space an IIM may use to compute its actual guess. If the topological structure of L
is more complicated than in case of finite learning, then the method presented above
fails. The next theorem shows that any other method fails as well.
Theorem 37. s−CLIM−T XT ⊂ ELIM−T XT = LIM−T XT = CLIM−T XTProof. The part ELIM −T XT = LIM −T XT = CLIM −T XT is due to Lange
and Zeugmann (1993c). Again, the part s−CLIM −T XT ⊂ ELIM −T XT is only
sketched.
As a matter of fact, the proof technique introduced in Section 5 is powerful enoughto show the desired result. The desired separation can be obtained by using theindexed family L of Example 6. Thus, L is defined as follows. For all k ∈ IN we set
Lhk,0i = {ak bn n ∈ IN+ }. For all k ∈ IN and all j ∈ IN+ we distinguish the following
cases:
Case 1. ¬Φk (k) ≤ j

Then we set Lhk,ji = Lhk,0i .
Case 2. Φk (k) ≤ j

Let d = (2 · Φk (k) − j. Now, we set:{ak bm 1 ≤ m ≤ d}, if d ≥ 1,
Lhk,ji ={ak b},
otherwise.

L = (Lhk,ji )j,k∈IN is an indexed family of recursive languages, since the predicate“Φi (y) ≤ z” is uniformly decidable in i, y, and z.

Any set-driven IIM that might learn L has to overcome two difficulties. First, it
has to find a hypothesis, and second, it has to detect whether or not its actual guessis overgeneralized. Intuitively, detecting overgeneralization forces M to handle thehalting problem. Hence, it may try to avoid overgeneralized hypothesises. But again,
this forces M to search the least language with respect to set inclusion comprising t+x.
57

Since the halting problem is algorithmically unsolvable, M cannot decide whether or
not to continue its search for a number of a least language. But if it gives up, it mightovergeneralize, and we are back to Case 1. This can be well formalized, and indeed
one can show that any set-driven IIM learning L directly yields an algorithm solving
the halting problem (cf. Lange and Zeugmann (1993e)).
On the other hand, it is not hard to prove that L can be inferred in the limit
with respect to the hypothesis space L. The main idea can be described as follows.
The desired IIM M uses the length of its actual input to test whether Φk (k) might
be defined. As long as Φk (k) does not turn out to be defined, M simply outputs
the corresponding index hk, 0i, where k can be easily computed from t0 . In caseΦk (k) happens to be defined, M can effectively search for the least language in L thatcomprises tx .
q.e.d.
As the latter theorem shows, sometimes there is no way to design a set-driven
IIM. However, with the following theorems we mainly intend to show that the carefulchoice of the hypothesis space deserves special attention whenever set-drivenness isdesired.
Theorem 38. There is an indexed family L such that
(1) L ∈ r−ESM ON −T XT ,(2) no set-driven IIM M LIM −T XT –infers L,(3) there are a hypothesis space G and an IIM M witnessing L ∈ s−CSM ON−T XTwith respect to G.
As we have seen, set-drivenness constitutes a severe restriction. While this is truein general as long as exact and class preserving learning is considered, the situation
looks differently in the class comprising case. On the one hand, learning in the limit
cannot always be achieved by set-driven IIMs (cf. Theorem 37). On the other hand,conservative learners may always be designed to be set-driven, if the hypothesis space
is appropriately chosen.
Theorem 39.

s–CCONSERVATIVE–TXT = CCONSERVATIVE–TXT

Again, we only sketch the main ideas of the proof, and refer the interested reader toLange and Zeugmann (1993e) for any detail. The proof is partitioned into two parts.
The first part establishes the equality of class comprising conservative and class comprising, rearrangement-independent conservative learning. The main ingredients into
this proof are the characterization of CCONSERVATIVE–TXT (cf. Section 3, Theorem 5) as well as a technically simple, but powerful modification of the corresponding
tell-tale family (cf. Section 4, Theorem 9). For the sake of readability, we recall theseresults.
Let L ∈ CCONSERVATIVE −TXT . Then there exist a space G = (Gj )j∈IN of
hypotheses and a recursively generable tell-tale family (Tj )j∈IN of finite and non-empty
sets such that(1) range(L) ⊆ L(G),(2) for all j ∈ N , Tj ⊆ L(Gj ),58

(3) for all j, k ∈ IN, if Tj ⊆ L(Gk ), then L(Gk ) 6⊂ L(Gj ).
Using this tell-tale family, we define a new recursively generable family (T̂j )j∈IN of
finite and non-empty sets that allows the design of a rearrangement-independent IIM
inferring L conservatively with respect to G. But surprisingly enough, we can even do
better, namely, we can defineSan IIM witnessing L(G) ∈ r−ECONSERVATIVE −TXT .
For all j ∈ IN we set T̂j = n≤j Tn ∩ L(Gj ). Note that the new tell-tale family fulfills
Properties (1) through (3) above.
Now, the wanted IIM can be defined as follows: Let L ∈ L(G), t ∈ text (L), andx ∈ N.
M (tx ) = “Generate T̂k for all k ≤ x and test whether T̂k ⊆ t+x ⊆ L(Gk ). In case there
is one k fulfilling the test, output the minimal one, and request the next input.
Otherwise, output nothing and request the next input.”
Obviously, M is rearrangement-independent. We omit the proof that M ECONSERVATIVE–TXT–learns L(G).

The second part of the proof establishes set-drivenness. For that purpose, we define
a new hypothesis space G̃ = (G̃j )j∈IN as well as a new IIM M̃ . The basis for thesedefinitions are the hypothesis space G = (Gj )j∈IN , and the IIM M described above.
The hypothesis space G̃ is the canonical enumeration of all grammars from G and
all finite languages over the underlying alphabet Σ. Before defining the IIM M̃ , weintroduce the notion of repetition free text rf (t). Let t = s0 , s1 , ... be any text. We
set rf (t0 ) = s0 and proceed inductively as follows: For all x ≥ 1, rf (tx+1 ) = rf (tx ),if sx+1 ∈ rf (tx )+ , and rf (tx+1 ) = rf (tx ), sx+1 otherwise. Obviously, given any initial
segment tx of a text t one can effectively compute rf (tx ). Now we are ready to present
the definition of M̃ . Let L ∈ L(G), t ∈ text (L), and x ∈ IN.
M̃ (tx ) = “Compute rf (tx ). If M on input rf (tx ) outputs a hypothesis, say j, thenoutput the canonical index of j in G̃ and request the next input.
Otherwise, output the canonical index of t+
x in G̃ and request the next input.”
Intuitively, it is clear that M̃ is set-driven. We omit the proof that M̃ CCONSERVATIVE–TXT–learns L with respect to G̃.
q.e.d.
The latter theorem allows a nice corollary that we present next. In particular, thiscorollary shows that the IIM M̃ defined above can be transformed into an IIM M
that learns much more than one might expect.
Corollary 40. Let L ∈ CCONSERVATIVE −TXT . Then, there exists a hypothesis space Ĝ = (Ĝj )j∈IN comprising L such that L(Ĝ) ∈ s−ECONSERVATIVE −TXT .

Proof. Let L ∈ CCONSERVATIVE −TXT . Furthermore, by the latter theorem,
there are an IIM M̃ and a hypothesis space G̃ such that M̃ s−CCONSERVATIVE−
TXT –infers L with respect to G̃.

Recall that G̃ is a canonical enumeration of G = (Gj )j∈IN satisfying L ⊆ L(G) andof all finite languages over the underlying alphabet. Without loss of generality we
may assume that G̃ fulfills the following property. If j is even, then L(G̃j ) ∈ L(G).
Hence, M̃ s −CCONSERVATIVE −TXT –learns L(G̃j ) with respect to G̃. Otherwise,
L(G̃j ) is a finite language.
59

We start with the definition of the desired hypothesis space Ĝ = (Ĝj )j∈IN If j iseven, then we set Ĝj = G̃j . Otherwise, we distinguish the following cases. If M
when fed the lexicographically ordered enumeration of all strings in L(G̃j ) outputs
the hypothesis j, then we set Ĝj = G̃j . In case it does not, we set Ĝj = G̃j−1 .
Now we are ready to define the desired IIM M witnessing L(Ĝ) ∈ s−ECONSERVATIVE−TXT. Let L ∈ L(Ĝ), t ∈ text (L), and x ∈ IN.
M (tx ) = “Simulate M̃ on input tx . If M̃ does not output any hypothesis, then output
nothing and request the next input.
Otherwise, let M̃ (tx ) = j. Output j and request the next input.”
Since M̃ is a conservative and set-driven IIM, M behaves thus. It remains to showthat M learns L. Obviously, if L = L(Ĝ2k ) for some k ∈ IN, then M̃ infers L, sinceM̃ s −CCONSERVATIVE −TXT –infers L. Therefore, since M simulates M̃ , we aredone.
Now, let us suppose, L 6= L(Ĝ2k ) for some k ∈ IN. By definition of Ĝ, we know that
L is finite. Moreover, since t is a text for L, there exists an x such that t+
y = L forall y ≥ x. Recalling the definition of Ĝ, and by assumption, we obtain the following.
There is a number j such that M̃ (tx ) = j, L = t+
x = L(G̃j ) = L(Ĝj ). Hence,
M (tx ) = j, too. Finally, since M is set-driven, we directly get M (ty ) = j for ally ≥ x. Consequently, M learns L.
q.e.d.

8.2. Learning with Rearrangement-Independent IIMs
In this section we study the impact of rearrangement-independence on the learning power of IIMs. Recall that r − ELIM − T XT = CLIM − T XT as well asr − SM ON − T XT = SM ON − T XT . So what about ESM ON − T XT ? By answering this question another proof technique comes into the play. The key idea
consists in applying Theorem 17. Hence, we may use a rearrangement-independent
IIM M̂ as well as a class preserving hypothesis space G such that L ∈ r−SM ON withrespect to G is witnessed by M . Due to that Theorem there exists a strong-monotonic
limiting recursive compiler f from G into L. Therefore, all we have to do is to combine
the IIM M̂ and the strong-monotonic limiting recursive compiler f . And indeed, thisidea goes through. Thus, ESM ON −T XT = r−ESM ON −T XT .
Moreover, the latter result cannot be improved as the next theorem states. Furthermore, the sketched proof technique does not apply to monotonic language learning,and so does any other proof technique. As a matter of fact, monotonic inference isvery sensitive with respect to the order in which the input data are presented.
Theorem 41.
(1) s−EM ON −T XT ⊂ r−EM ON −T XT ⊂ EM ON −T XT ,(2) s−M ON −T XT ⊂ r−M ON −T XT ⊂ M ON −T XT .
Finally, we consider rearrangement-independence in the context of exact and classpreserving conservative learning. Since conservative learning is exactly as powerful
as weak-monotonic one, by the latter theorem one might expect that rearrangementindependence is a severe restriction under the weak-monotonic constraint, too. On
60the other hand, looking at Theorem 39 we see that conservative learning has its
peculiarities. And indeed, exact and class preserving learning can always be performedby rearrangement-independent IIMs. In order to prove this, we first characterize
ECONSERVATIVE in terms of finite tell-tales. We present this theorem separately,
since it is interesting in its own right.
Theorem 42. Let L be an indexed family. Then, L ∈ ECONSERVATIVE −TXT
if and only if there exists a recursively generable family (Tjy )j,y∈IN of finite sets suchthat(1) for all L ∈ L there exists a j with Lj = L and Tjy 6= ∅ for almost all y ∈ IN,(2) for all j, y ∈ IN, Tjy 6= ∅ implies Tjy ⊆ Lj and Tjy = Tjy+1 ,(3) for all j, y, z ∈ IN, ∅ 6= Tjy ⊆ Lz implies Lz 6⊂ Lj .
For a proof, the reader is referred to Lange and Zeugmann (1993e).
Finally, applying the same technique as described in the proof of Theorem 39
one may modify mutatis mutandis the tell-tale family (Tjy )j,y∈IN appropriately. Then,the new family as well as a suitable modification of the IIM defined in the proofof Theorem 39 directly yield the rearrangement-independence of exact conservative
learning. Moreover, the same ideas are powerful enought to show the analogous result
for class preserving conservative inference (cf. Section 4, Theorem 9). Hence, we havethe following theorem.
Theorem 43.
(1) r−ECONSERVATIVE −TXT = ECONSERVATIVE −TXT ,(2) r−CONSERVATIVE −TXT = CONSERVATIVE −TXT .
With the following figure we summarize the results surveyed in this section andpoint to questions that remain open. We shall discuss them and some less obvious
ones in Section 9.
For every model of learning LT mentioned “rearrangement-independence +” indicates r − LT = LT as well as s − LT ⊂ LT . “Rearrangement-independence –”implies s−LT ⊂ r −LT ⊂ LT whereas “set-drivenness +” should be interpreted ass−LT = LT and, therefore, r−LT = LT , too.

61

exactlearningclass preserving
learningclass comprisinglearning

F IN

setdrivenness+

set
drivenness+

set
drivenness

SM ON

rearrangement
independence+

rearrangement
independence

+

?

M ON

rearrangement
independence–

rearrangement
independence

–

?

WM ON

rearrangement
independence+

rearrangement
independence+

set
drivenness

LIM

rearrangement
independence+

rearrangement
independence+

rearrangement+
independence++

9. Outlook
We started our guided tour with several question that are closely related to thedesign of “natural” learning algorithms. Therefore, we continue with a short discussion of our results in this regard. Mathematically sound formalizations of learning bygeneralization and specialization have been introduced. Furthermore, the models of
weak-monotonic learning and of dual weak-monotonic inference formalized the problem to what extend non-monotonic reasoning has to be incorporated into the learning
process. As we have seen, superior learning algorithms can be designed if and only
if most of the monotonicity demands are dropped (cf. e.g. Section 5, Theorem 11 as
well as Figure 1 and 2). Consequently, our results provide considerable evidence thatlearning has to be performed, at least to some extend, incorporating non-monotonic
reasoning.
Furthermore, the characterizations obtained provide a unifying framework to alltypes of monotonic learning. Hence, we achieved considerable insight into the problem
what is more appropriate, learning by specialization or learning by generalization. All
the differences between these two global learning strategies can be expressed in terms
of properties the hypothesis space and the corresponding finite tell-tale sets mustsatisfy. These results strongly recommend to study particular properties of indexedfamilies that can be expressed by suitable descriptions of the objects to be learned andby finite tell-tale sets (cf. e.g. Example 4). As we have seen, it is mainly the interplay
between the properties of the relevant hypothesis space and the relevant tell-talesets that makes or does not make a learning problem solvable. The latter assertioneven remains true, if additional postulates of naturalness are involved. Our theorem
stating s − CCONSERVATIVE − TXT = CCONSERVATIVE–TXT may serve as anillustrative example (cf. Section 8, Theorem 39).
However, some intriguing questions concerning order independence remain open.
Two of them are presented in the figure above. Additionally, it would be highly desirable to elaborate characteristic conditions under what circumstances set-drivenness
does not restrict the learning power. We expect that such characterizations might62

allow much more insight into the problem how to handle simultaneously both, finite
and infinite languages in the learning process 2 . Next, as we have seen, an algorithmically solvable learning problem might become infeasible, if one tries to solve it with
set-driven IIMs. On the other hand, when dealing with particular learning problems
it might often be possible to design a set-driven learning algorithm solving it. But
what about the complexity of learning in such circumstances? More precisely, we areinterested in knowing whether the “high-level” theorem separating set-driven learningfrom unrestricted one, has an analogue in terms of complexity theory. For example,
it is well conceivable that an indexed family L may be learned in polynomial time but
no set-driven algorithm can efficiently infer L provided P 6= N P.
Moreover, our results suggest some further avenues of research. All learning models
described in this paper dealt with passive inference, i.e., the IIM itself has no influence
to the data it is fed. Hence, it seems to be very promising to study active learning,too (cf. Angluin (1992) and the references therein). The most common types ofqueries are equivalence and membership queries. Clearly, each indexed family canbe learned by equivalence queries alone. However, this approach may lead to nonefficient solutions. On the other hand, there are some results showing that particularindexed families are learnable in polynomial time using membership and equivalence
queries (cf. e.g. Ishizaka (1989)). Obviously, the crucial point is to determine whatmembership queries the learner should ask. We conjecture that tell-tales might bevery helpful to solve the latter problem.

Finally, it seems very promising to study the learnability of indexed families withinprobabilistic models of inductive inference. In the setting of inductive inference ofrecursive functions Freivalds, Kinber and Wiehagen (1988) proved the following interesting result. There are hypothesis spaces H such that non-exactly learnable function
classes might become inferable with probability 1 with respect to H. It would be interesting to know whether or not similar effects might occur in the setting of learning
recursive languages. Furthermore, Wiehagen, Freivalds and Kinber (1984) proved thesuperiority of probabilistic inference algorithms with respect to the number of allowed
mind changes. Again, we are interested in learning whether or not these results extend
to our setting.

10. References
Adleman, L.M., and Blum, M. (1991), Inductive inference and unsolvability,
Journal of Symbolic Logic 56, 891 – 900.
Angluin, D. (1980a), Finding patterns common to a set of strings, Journal ofComputer and System Sciences, 21, 46 – 62.
Angluin, D. (1980b), Inductive inference of formal languages from positive data,
Information and Control, 45 (1980), 117 – 135.
Angluin, D. (1992), Computational learning theory: Survey and selected bibliography, in “Proceedings 24th Annual ACM Workshop on Theory of Computing,”
pp. 351 – 369, ACM Press.
2

For recent results see Lange and Zeugmann (1996).

63

Angluin, D., and Smith, C.H. (1983), Inductive inference: theory and methods,
Computing Surveys 15, 237 – 269.
Angluin, D., and Smith, C.H. (1987), Formal inductive inference, in “Encyclopedia of Artificial Intelligence” (St.C. Shapiro, Ed.), Vol. 1, pp. 409 – 418,
Wiley-Interscience Publication, New York.
Anthony, M. and Biggs, N. (1992), “Computational Learning Theory,” Cambridge University Press, Cambridge.
Arikawa, S., Goto, S., Ohsuga, S., and Yokomori, T. (Eds.) (1990) “Proceedings 1st International Workshop on Algorithmic Learning Theory,” October
1990, Tokyo, Japanese Society for Artificial Intelligence.
Arikawa, S., Maruoka, A., and Sato, T. (Eds.) (1991) “Proceedings 2nd
International Workshop on Algorithmic Learning Theory,” October 1991, Tokyo,
Japanese Society for Artificial Intelligence.
Arikawa, S., Kuhara, S., Miyano, S., Mukouchi, Y., Shinohara, A. andShinohara, T. (1992), A machine discovery from amino acid sequences bydecision trees over regular patterns, in Proceedings International Conference on
Fifth Generation Computer Systems, Vol. 2, pp. 618 – 625, Institute for New
Generation Computer Technology (ICOT), Tokyo, Japan.
Barzdin, Ya.M. (1974), Inductive inference of automata, functions and programs,in “Proceedings International Congress of Math.,” Vancouver, pp. 455 – 460.
Barzdin, Ya.M., and Freivalds, R.V. (1972), On the prediction of generalrecursive functions, Sov. Math. Dokl. 13, 1224 – 1228.
Barzdin, Ya.M., and Freivalds, R.V. (1974), Prognozirovanie i predel~nyĭ sintez effektivno pereqislimyh klassov funkciĭ, in “Teori
Algoritmov i Programm,” Vol. 1 (Ya. M. Barzdin, ed.) Latvian State
University, Riga, pp. 101 – 111.
Barzdin, Ya.M., Kinber, E.B., and Podnieks, K.M. (1974), Ob uskorenii
sinteza i prognozirovani funkciĭ, in “Teori Algoritmov i Programm,” Vol. 1 (Ya.M. Barzdin, Ed.) Latvian State University, Riga, pp. 117– 128.
Berwick, R. (1985), “The Acquisition of Syntatic Knowledge,” MIT Press, Cambridge, Massachusetts.
Blum, A., and Singh, M. (1990), Learning functions of k terms, in “Proceedings 3rd Workshop on Computational Learning Theory, July 1990, Rochester,”(M. Fulk and J. Case, Eds.), pp. 144 – 153, Morgan Kaufmann Publishers Inc.,
San Mateo.
Brewka, G. (1991), “Nonmonotonic Reasoning: Logical Foundations of Commonsense,” Cambridge University Press, Cambridge.

64Case, J. (1988), The power of vacillation, in “Proceedings 1st Workshop on Computational Learning Theory, August 1988, Boston,” (D. Haussler and L. Pitt,
Eds.), pp. 196 – 205, Morgan Kaufmann Publishers Inc., San Mateo.
Case, J., and Lynes, C. (1982), Machine inductive inference and language identification, in “Proceedings Automata, Languages and Programming, Ninth Colloquium, Aarhus, Denmark,” (M. Nielsen and E.M. Schmidt, Eds.), Lecture Notes
in Computer Science Vol. 140, pp. 107 – 115, Springer-Verlag, Berlin.
Case, J., and Smith, C.H. (1983), Comparison of identification criteria for machine inductive inference, Theoretical Computer Science 25, 193 - 220.
Freivalds, R., Kinber, E.B. and Wiehagen, R. (1988), Probabilistic versus deterministic inductive inference in nonstandard numberings, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 34 (1988), 531 – 539.
Freivalds, R., Kinber, E.B. and Wiehagen, R. (1992), Convergently versus
divergently incorrect hypotheses in inductive inference, GOSLER–Report 02/92,
January 1992, FB Mathematik und Informatik, TH Leipzig.
Fulk, M. (1990), Prudence and other restrictions in formal language learning, Information and Computation, 85 1 – 11.
Fulk, M., and Case, J. (Eds.) (1990), Proceedings of the 3rd Annual Workshop
on Computational Learning Theory, July 1990, Rochester, Morgan Kaufmann
Publishers Inc., San Mateo.
Gasarch, W.I., and Velauthapillai, M. (1992), Asking questions versus verifiability, in “Proceedings 3rd International Workshop on Analogical and Inductive Inference,” October 1992, Dagstuhl, (K.P. Jantke, ed.) Lecture Notes in
Artificial Intelligence Vol. 642, pp. 197 – 213, Springer-Verlag, Berlin.
Gold, M.E. (1965), Limiting recursion, Journal of Symbolic Logic, 30 28 – 48.
Gold, M.E. (1967), Language identification in the limit, Information and Control
10, 447 – 474.
Haussler, D. (Ed.) (1992), Proceedings of the 5th Annual Workshop on Computational Learning Theory, July 1992, Pittsburgh, ACM Press, New York.
Hopcroft, J.E., and Ullman, J.D. (1969), “Formal Languages and their Relation to Automata,” Addison-Wesley, Reading, Massachusetts.
Ishizaka, H. (1989), Learning simple deterministic languages. in “Proceedings ofthe 2nd Annual Workshop on Computational Learning Theory, Santa Cruz,
August 1989, (R. Rivest, D. Haussler and M.K. Warmuth, Eds.), pp. 162–174,
Morgan Kaufmann Publishers Inc., San Mateo.
Jain, S., and Sharma, A. (1989), Recursion theoretic characterizations of language learning, The University of Rochester, Dept. of Computer Science, TR
281.

65

Jantke, K.P. (Ed.) (1989), “Proceedings 2nd International Workshop on Analogical and Inductive Inference, October 1989, Reinhardsbrunn Castle,” Lecture
Notes in Artificial Intelligence Vol. 397.
Jantke, K.P. (1991a), Monotonic and non-monotonic inductive inference, New
Generation Computing 8, 349 – 360.
Jantke, K.P. (1991b), Monotonic and non-monotonic inductive inference of functions and patterns, in “Proceedings 1st International Workshop on Nonmonotonic and Inductive Logics, December 1990, Karlsruhe,” (J. Dix , K.P. Jantke and
P.H. Schmitt, Eds.), Lecture Notes in Artificial Intelligence Vol. 543, pp. 161 –
177, Springer-Verlag, Berlin.
Jantke, K.P. (Ed.) (1992), “Proceedings 3rd International Workshop on Analogical and Inductive Inference, October 1992, Dagstuhl Castle,” Lecture Notes in
Artificial Intelligence Vol. 642.
Kapur, S. (1992), Monotonic language learning, in “Proceedings 3rd Workshop
on Algorithmic Learning Theory,” October 1992, Tokyo, (S. Doshita, K. Furukawa, K.P. Jantke and T. Nishida, Eds.), Lecture Notes in Artificial Intelligence Vol. 743, pp. 147 – 158, Springer-Verlag, Berlin.
Kapur, S., and Bilardi, G. (1992), Language learning without overgeneralization, in “Proceedings 9th Annual Symposium on Theoretical Aspects of Computer Science, Cachan, France, February 13 - 15,” (A. Finkel and M. Jantzen,
Eds.), Lecture Notes in Computer Science Vol. 577, pp. 245 – 256, SpringerVerlag, Berlin.
Kearns, M., and Pitt, L. (1989), A polynomial-time algorithm for learning k–variable pattern languages from examples, in “Proceedings 1st Annual Workshop on Computational Learning Theory, August 1988, Boston,” (D. Haussler
and L. Pitt, Eds.), pp. 196 –205, Morgan Kaufmann Publishers Inc., San Mateo.
Kinber, E.B. (1992), personal communication.
Kodratoff, Y., and Michalski, R.S. (1990), “Machine Learning, An Artificial
Intelligence Approach,” Vol. 3, Morgan Kaufmann Publishers Inc., San Mateo.
Lange, S. (1994), The representation of recursive languages and its impact on theefficiency of learning, in “Proceedings 7th Annual ACM Conference on Computational Learning Theory, New Brunswick, July 1994,” (M. Warmuth, Ed.),
pp. 256 – 267, ACM Press, New York.
Lange, S., and Wiehagen, R. (1991), Polynomial-time inference of arbitrary
pattern languages, New Generation Computing 8, 361 – 370.
Lange, S., and Zeugmann, T. (1992), Types of monotonic language learning andtheir characterization, in “Proceedings 5th Annual ACM Workshop on Computational Learning Theory, Pittsburgh, July 1992,” (D. Haussler, Ed.), pp. 377 –
390, ACM Press, New York.

66

Lange, S., and Zeugmann, T. (1993a), Monotonic versus non-monotonic language learning, in “Proceedings 2nd International Workshop on Nonmonotonic
and Inductive Logic, December 1991, Reinhardsbrunn,” (G. Brewka, K.P. Jantke and P.H. Schmitt, Eds.), Lecture Notes in Artificial Intelligence Vol. 659,
pp. 254 – 269, Springer-Verlag, Berlin.
Lange, S., and Zeugmann, T. (1993b), Learning recursive languages with bounded mind changes, International Journal of Foundations of Computer Science 4,
157 – 178.
Lange, S., and Zeugmann, T. (1993c), Language learning in dependence on thespace of hypotheses, in “Proceedings 6th Annual ACM Conference on Computational Learning Theory,” Santa Cruz, July 1993, pp. 127 – 136, ACM Press,
New York.
Lange, S., and Zeugmann, T. (1993d), The learnability of recursive languages
in dependence on the space of hypotheses, GOSLER–Report 20/93, July 1993,
Fachbereich Mathematik und Informatik, TH Leipzig.
Lange, S., and Zeugmann, T. (1993e), On the impact of order independence
to the learnability of recursive languages, Research Report ISIS-RR-93-17E,
Institute for Social Information Science, FUJITSU Laboratories Ltd, Numazu.
Lange, S., and Zeugmann, T. (1994), Characterization of language learning on
informant under various monotonicity constraints, Journal of Experimental andTheoretical Artificial Intelligence 6, 73 – 94.
Lange, S., and Zeugmann, T. (1995), Modeling incremental learning from positive data, Technical Report RIFIS-TR-CS-117, Research Institute of Fundamental Information Science (RIFIS), Kyushu University, Fukuoka.
Lange, S., and Zeugmann, T. (1996), Set-driven and rearrangement-independent
learning of recursive languages, Mathematical Systems Theory 29, No. 6, 1996,
599 – 634.
Lange, S., and Zeugmann, T., and Kapur, S (1992), Class preserving monotonic language learning, GOSLER–Report 14/92, FB Mathematik und Informatik,
TH Leipzig, appeared as:
Monotonic and dual monotonic language learning, Theoretical Computer Science
155 (1996), 365 – 410.
Machtey, M., and Young, P. (1978), “An Introduction to the General Theoryof Algorithms,” North-Holland, New York.
Michalski, R.S., Carbonell, J.G., and Mitchell, T.M. (1984), “Machine
Learning, An Artificial Intelligence Approach,” Vol. 1, Springer-Verlag, Berlin.
Michalski, R.S., Carbonell, J.G., and Mitchell, T.M. (1986), “Machine
Learning, An Artificial Intelligence Approach,” Vol. 2, Morgan Kaufmann Publishers Inc., San Mateo.

67

Mukouchi, Y. (1992), Inductive inference with bounded mind changes, in “Proceedings 3rd Workshop on Algorithmic Learning Theory,” October 1992, Tokyo,(S. Doshita, K. Furukawa, K.P. Jantke and T. Nishida, Eds.), Lecture Notes in
Artificial Intelligence Vol. 743, pp. 125 – 134, Springer-Verlag, Berlin.
Mukouchi, Y. (1994), Inductive inference of recursive concepts, Ph.D. Thesis, RIFIS, Kyushu University 33, RIFIS-TR-CS-82, March 25th.
Natarajan, B.K. (1991), “Machine Learning, A Theoretical Approach,” Morgan
Kaufmann Publishers, Inc., San Mateo.
Nix, R.P. (1983), Editing by examples, Yale University, Dept. Computer Science,
Technical Report 280.
Osherson, D., Stob, M., and Weinstein, S. (1986), “Systems that Learn,
An Introduction to Learning Theory for Cognitive and Computer Scientists,”
MIT-Press, Cambridge, Massachusetts.
Pitt, L., and Valiant, L.G. (1988), Computational limitations on learning fromexamples, Journal of the ACM 35, 965 – 984.
Popper, K. (1968), “The Logic of Scientific Discovery,” Harper Torch Books.
Rivest, R., Haussler, D., and Warmuth, M.K. (Eds.) (1989), Proceedingsof the 2nd Annual Workshop on Computational Learning Theory, August 1989,
Santa Cruz, Morgan Kaufmann Publishers Inc., San Mateo.
Schäfer-Richter, G. (1984), Über Eingabeabhängigkeit und Komplexität vonInferenzstrategien, Rheinisch Westfälische Technische Hochschule Aachen, Dissertation.
Shinohara, T. (1982), Polynomial time inference of extended regular pattern languages, in “Proceedings RIMS Symposia on Software Science and Engineering,”
Kyoto, Lecture Notes in Computer Science 147, pp. 115 – 127, Springer-Verlag,
Berlin.
Solomonoff, R. (1964), A formal theory of inductive inference, Information andControl 7, 1 – 22, 234 – 254.
Trakhtenbrot, B.A., and Barzdin, Ya.M. (1970) “Koneqnye Avtomaty(Povedenie i Sintez),” Nauka, Moskva,
English translation: “Finite Automata–Behavior and Synthesis, Fundamental
Studies in Computer Science 1,” North-Holland, Amsterdam, 1973.
Wexler, K. (1992), The subset principle is an intensional principle, in “Knowledge
and Language: Issues in Representation and Acquisition,” ((E. Reuland and
W. Abraham, Eds.), Kluwer Academic Publishers.
Wexler, K., and Culicover, P. (1980), “Formal Principles of Language Acquisition,” MIT Press, Cambridge, Massachusetts.

68Wiehagen, R. (1976), Limes–Erkennung rekursiver Funktionen durch spezielle
Strategien, Journal of Information Processing and Cybernetics (EIK), 12, 93– 99.
Wiehagen, R. (1977), Identification of formal languages, in “Proceedings Mathematical Foundations of Computer Science, Tatranska Lomnica,” (J. Gruska,Ed.), Lecture Notes in Computer Science 53, pp. 571 – 579, Springer-Verlag,
Berlin.
Wiehagen, R. (1978), Characterization problems in the theory of inductive inference, in “Proceedings 5th Colloquium on Automata, Languages and Programming,” (G. Ausiello and C. Böhm, Eds.), Lecture Notes in Computer Science62, pp. 494 – 508, Springer-Verlag, Berlin.
Wiehagen, R. (1991), A thesis in inductive inference, in “Proceedings First International Workshop on Nonmonotonic and Inductive Logic,” (J. Dix, K.P. Jantke
and P.H. Schmitt, Eds.), Lecture Notes in Artificial Intelligence 543, pp. 184 –
207, Springer-Verlag, Berlin.
Wiehagen, R., Freivalds, R., and Kinber, B. (1984), On the power of probabilistic strategies in inductive inference, Theoretical Computer Science 28, 111– 133.
Wiehagen, R., and Zeugmann, T. (1994), Learning and Consistency, this volume.
Zeugmann, T., and Lange, S. (1995), A guided tour across the boundaries oflearning recursive languages, in “Algorithmic Learning for Knowledge-Based
Systems” (K.P. Jantke and S. Lange, Eds.), Lecture Notes in Artificial Intelligence, Vol. 961, pp. 193 – 262, Springer-Verlag.
Zeugmann, T., Lange, S., and Kapur, S. (1995), Characterizations of monotonic and dual monotonic language learning, Information and Computation 120,
No. 2, 1995, 155 – 173.

69