Set-Driven and Rearrangement-Independent Learning of
Recursive Languages1

Steffen Lange

Thomas Zeugmann

HTWK Leipzig

Department of Informatics

FB Mathematik und Informatik

Graduate School of Inf. Sci. and EE

PF 30066

Kyushu University

04251 Leipzig, Germany

Fukuoka 812-81, Japan

steffen@informatik.th-leipzig.de

thomas@i.kyushu-u.ac.jp

Key words: Algorithmic Learning Theory, Computational issues in A.I., Automata and Formal
Languages

1 This is a substantially revised version of the author’s paper at the 5th International Workshop

on Algorithmic Learning Theory (ALT’94), Lecture Notes in Artificial Intelligence 872, 453 – 468.

Abstract
The present paper studies the impact of order independence to the learnability of indexedfamilies L of uniformly recursive languages from positive data. In particular, we consider
set-driven and rearrangement-independent learners, i.e., learning devices whose output exclusively depends on the range and on the range and length of their input, respectively.
The impact of set-drivenness and rearrangement-independence on the behavior of learners
to their learning power is studied in dependence on the hypothesis space the learners may
use. We distinguish between exact learnability (L has to be inferred with respect to L),
class-preserving learning (L has to be inferred with respect to some suitably chosen enumeration of all the languages from L), and class-comprising inference (L has to be learned withrespect to some suitably chosen enumeration of uniformly recursive languages containing atleast all the languages from L).
Furthermore, we consider the influence of set-drivenness and rearrangement-independence
for learning devices that realize the subset principle to different extents. Thereby we distinguish between strong-monotonic, monotonic and weak-monotonic or conservative learning.
The results obtained are threefold. First, rearrangement-independent learning does notconstitute a restriction except in the case of monotonic learning. Next, we prove that for all
but two of the considered learning models set-drivenness is a severe restriction. However,class-comprising set-driven conservative learning is exactly as powerful as unrestricted classcomprising conservative learning. Finally, the power of class-comprising set-driven learningin the limit is characterized by equating the collection of learnable indexed families withthe collection of class-comprisingly conservatively inferable indexed families. These results
considerably extend previous work done in the field (cf., e.g., Schäfer-Richter [20] and Fulk
[5]).

1. Introduction
Language acquisition is one of the main topics in cognitive science, epistemology, linguistic
and psycholinguistic theory as well as of machine learning and algorithmic learning theory.
All these disciplines share the common goal to gain a better understanding of what learning
really is. This goal is of special interest to computer science if a learning computer should
not remain a fiction.
Formal language learning 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 inwhich the sequence of hypotheses stabilizes to an accurate and finite description (a grammar)of the target language. Clearly, then some form of learning must have taken place. In his
pioneering paper, Gold [6] gave precise definitions of the concepts “evidence,” “stabilization,”and “accuracy” resulting in the model of learning in the limit. During the last decades,
Gold-style formal language learning has attracted a lot of attention by computer scientists(cf., e.g., Osherson, Stob and Weinstein [19] and the references therein). Most of the work
done in the field has been aimed at the following goals: showing what general collections oflanguage classes are learnable, characterizing those collections of language classes that canbe learned, studying the impact of several postulates on the behavior of learners to theirlearning power, and dealing with the influence of various parameters to the efficiency oflearning.
In this paper we aim to investigate the learning capabilities of learners that fulfill simultaneously various combinations of desirable properties. For the purpose of motivationand discussion of our research, we introduce some notations. A text of a language L is an
infinite sequence of strings that eventually contains all strings of L. An algorithmic learner,
henceforth called inductive inference machine (abbr. IIM), takes as input initial segmentsof a text, and outputs, from time to time, a hypothesis about the target language. The
set G of all admissible hypotheses 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 thatlearns a language L from all texts for it, then L is said to be learnable in the limit with1

respect to the hypothesis space G (cf. Definition 1).
A first question directly arising when dealing with learning in the limit is whether or not
the order of information presentation does really influence the capabilities of IIMs. An IIM
is said to be set-driven, if its output only depends on the range of its input. Surprisingly
enough, Schäfer-Richter [20] and Fulk [5] proved that set-driven IIMs are less powerful thanunrestricted ones. Intuitively, the weakness of set-driven IIMs is caused by the difficultiesof handling both, finite and infinite languages. A natural weakening of set-drivenness isrearrangement-independence. An IIM is called rearrangement-independent if its output only
depends on the range and length of its input. As it turned out, any collection of languages
that can be learned in the limit may also be learned by a rearrangement-independent IIM(cf. Schäfer-Richter [20], Fulk [5]). However, the weakness of set-driven IIMs has been provedin the setting of learning recursively enumerable languages. And indeed, the examples ofSchäfer-Richter [20] and Fulk [5] witnessing the weakness of set-driven IIMs are not enumerable families of nonempty uniformly recursive languages, henceforth called indexed families.
This might lead to the impression that this result is of restricted practical relevance, since
numerous potential applications of learning involve indexed families.
Therefore, we study the power of set-driven IIMs in a more realistic setting with respect topotential applications, i.e., we deal exclusively with indexed families. Well-known examples
of indexed families are the set of all context sensitive languages, the set of all context freelanguages as well as the set of all regular languages (cf., e.g., Hopcroft and Ullman [7]).
Another famous example for an indexed family is the collection of all pattern languages(cf. Angluin [1]). Although this indexed family contains finite and infinite languages, Lange
and Wiehagen [9] succeeded in designing a set-driven IIM learning it (cf. [26, Theorem 2]).
Consequently, it is only natural to ask whether or not any learnable indexed family may belearned by a set-driven IIM, too.
A major problem that has to be dealt with when learning from text, is to avoid or to detect overgeneralization (also called the subset problem), i.e., hypotheses that describe proper
supersets of the target language. The impact of this problem results simply from the factthat a text cannot supply counterexamples to such hypotheses. IIMs that strictly avoid2

overgeneralized hypotheses are called conservative (cf. Definition 6). As it turns out, neither
Schäfer-Richter’s [20] nor Fulk’s [5] transformation of an arbitrary IIM into a rearrangementindependent one preserves conservativeness. Therefore, we study the problem whether or
not rearrangement-independence is a severe restriction for conservative learners. However,this problem has its special peculiarities. Namely, when dealing with conservative learning,
the choice of the hypothesis space does seriously influence the learnability of indexed families (cf. Lange and Zeugmann [12]). Hence, we have to distinguish between exact learning,class-preserving inference, and class-comprising identification. If an indexed family L canbe learned with respect to the hypothesis space L, then L is said to be exactly learnable.
Furthermore, L is learnable by a class-preserving learning algorithm M , if there is a hypothesis space G = (Gj )j∈IN such that any Gj describes a language from L and M learns Lwith respect to G. That means, if one learns class-preservingly, then one has the freedom
to change the enumeration as well as the description of the languages from L. Finally, if
any hypothesis space G = (Gj )j∈IN comprising the range of L may be taken by the learningalgorithm, then we call it class-comprising. In this setting one has the freedom to change theenumeration, the description and to add elements Gk not describing any language from L
to the hypothesis space. However, since membership in L is uniformly decidable, we restrict
ourselves to consider exclusively hypothesis spaces having a uniformly decidable membershipproblem.
Several authors proposed the so-called subset principle to solve the problem of avoiding
overgeneralization (cf., e.g., Berwick [4], Wexler [22]). Informally, the subset principle requires the learner to hypothesize a “least” language from the hypothesis space with respect
to set inclusion that fits with the data the IIM has read so far. Therefore, we present someformalizations of learning realizing the subset principle to different extents. First, we require
the learning algorithm to produce a sequence of hypotheses describing an augmenting chainof languages, i.e., L(Gj ) ⊆ L(Gk ), if k is hypothesized on an extension of the text segment that led to j (cf. Definition 5, (A)). We call learners behaving thus strong-monotonic.
Weakening the latter demand leads to weak-monotonic learners that are required to behave
strong-monotonically as long as they do not receive data contradicting its actual hypothesis.
If they receive strings that provably misclassify their actual hypothesis, then weak-monotonic
3

learners are allowed to output any hypothesis (cf. Definition 5, (C)). Third, we refine strongmonotonic learning in that we only require L(Gj ) ∩ L ⊆ L(Gk ) ∩ L. Now, “least” language
is interpreted with respect to the intersection with L. This learning model is called monotonic inference (cf. Definition 5, (B)). Strong-monotonic and weak-monotonic learning havebeen introduced by Jantke [8] and monotonic learning goes back to Wiehagen [24]. Subsequently, we have studied their learning capabilities in the setting of learning indexed families(cf. Lange and Zeugmann [11]). Again, the power of all the monotonic learning models
heavily depends on the choice of the hypothesis space (cf. Lange and Zeugmann [12]).
In what follows we study the impact of set-drivenness and rearrangement-independenceon all the learning models described above in dependence on the hypothesis space. The
results obtained prove that rearrangement-independent learning does not constitute a restriction except in case one learns monotonically. These results have been achieved by
non-trivial applications of the characterizations of all types of monotonic learning in termsof finite tell-tales (cf. Lange and Zeugmann [10]). Furthermore, we show that set-drivenness
cannot be achieved in general. However, class-comprising conservative learning is exactlyas powerful as class-comprising set-driven conservative inference. Moreover, we characterize class-comprising set-driven learning in the limit by equating the collection of learnableindexed families with the collection of class-comprisingly conservatively inferable indexedfamilies. We regard these results as a particular answer to the question of how a “natural”
learning algorithm may be designed.

2. Preliminaries
By IN = {0, 1, 2, ...} we denote the set of all natural numbers. We set IN+ = IN \ {0}.
Let ϕ0 , ϕ1 , ϕ2 , ... denote any fixed acceptable programming system of all (and onlyall) partial recursive functions over IN, and let Φ0 , Φ1 , Φ2 , ... be any associated complexity
measure (cf. Machtey and Young [17]). 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.,4hx, yi = ((x + y)2 + 3x + y)/2 for all x, y ∈ IN.
In what follows we assume familiarity with formal language theory (cf. Hopcroft and
Ullman [7]). By Σ we denote any fixed finite alphabet of symbols. Let Σ∗ be the freemonoid over Σ, and let Σ+ = Σ∗ \ {ε}, where ε denotes the empty string. Any subset
L ⊆ Σ∗ is called a language. Let L be a language and t = s0 , s1 , s2 , ... an infinite sequenceof strings from Σ∗ such that range(t) = {sk k ∈ IN} = L. Then t is said to be a text for Lor, synonymously, a positive presentation. Let L be a language. By text(L) we denotethe set of all positive presentations of L. Moreover, let t be a text and let x be a number.
Then, tx denotes the initial segment of t of length x + 1, and t+
x =df {sk k ≤ x}.
Next, we introduce the notion of the canonical text that turned out to be very helpful inproving several theorems. Let L be any nonempty recursive language, and let s0 , s1 , s2 , ... be
the lexicographically ordered text of Σ∗ . The canonical text of L is obtained as follows. Test
sequentially whether sz ∈ L for z = 0, 1, 2, ... until the first z is found such that sz ∈ L. Since
L 6= ∅ there must be at least one z fulfilling the test. Set t0 = sz . We proceed inductively.
For all x ∈ IN we define:tx+1 =
 tx · sz+x+1 ,

if



 t

otherwise, where s is the last string in tx .

x · s,

sz+x+1 ∈ L,

In what follows we deal with the learnability of indexed families of uniformly recursive
languages defined as follows (cf. Angluin [2]). A sequence L0 , L1 , L2 , ... is said to be anindexed family L of uniformly recursive languages provided all Lj are nonempty and there
is a recursive function f such that for all numbers j and all strings s ∈ Σ∗ we havef (j, s) =



 1,

if


 0,

otherwise.

s ∈ Lj ,In the following we refer to indexed families of uniformly recursive languages as indexedfamilies for short. Note that an indexed family is directly connected with the grammars
behind the enumerated languages. In particular, we can consider the indices as compiled
grammars (cf. Hopcroft and Ullman [7]). Next, we extend the notion of text(L) to indexedfamilies. Let L be an indexed family, then we set text(L) =S

L∈range(L) text(L).

As in Gold [6] we define an inductive inference machine (abbr. IIM) to be an algo5rithmic device which works as follows: The IIM takes as its input larger and larger initial
segments of a text t and it either requests the next input string, or it first outputs a hypothesis, i.e., a number encoding a certain computer program, and then it requests the next
input string.
At this point we specify the semantics of the hypotheses an IIM outputs. For that
purpose we have to clarify what hypothesis spaces we choose. We require the inductive
inference machines to output indices of grammars, since this learning goal fits well with
the intuitive idea of language learning. Furthermore, since we exclusively deal with indexedfamilies L = (Lj )j∈IN we always take as a space of hypotheses an enumerable family ofgrammars G0 , G1 , G2 , ... over the terminal alphabet Σ satisfying range(L) ⊆ {L(Gj ) j ∈IN}. Moreover, we require that membership in L(Gj ) is uniformly decidable for all j ∈ IN
and all strings s ∈ Σ∗ . When an IIM outputs a number j, we interpret it to mean that themachine is hypothesizing the grammar Gj . Furthermore, let G = (Gj )j∈IN be any hypothesis
space. For notational convenience we use L(G) to denote (L(Gj ))j∈IN . Note that L(G)constitutes itself an indexed family for all hypothesis spaces G = (Gj )j∈IN.
Let t be a text, and x ∈ IN. Then we use M (tx ) to denote the last hypothesis produced
by M when successively fed tx . The sequence (M (tx ))x∈IN is said to converge in the limit
to the number j if and only if either (M (tx ))x∈IN is infinite and all but finitely many termsof it are equal to j, or (M (tx ))x∈IN is nonempty and finite, and its last term is j. Now wedefine some concepts of learning. We start with learning in the limit.
Definition 1. (Gold [6]) 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–identifies L from text withrespect to G iff for every text t for L, there exists a j ∈ IN such that the sequence (M (tx ))x∈IN
converges in the limit to j and L = L(Gj ).
Furthermore, M CLIM –identifies L with respect to G iff, for each L ∈ range(L), M
CLIM –identifies L from text with respect to G.
Finally, let CLIM denote the collection of all indexed families L for which there are an
IIM M and a hypothesis space G such that M CLIM –identifies L with respect to G.
Suppose, an IIM identifies some language L. That means, after having seen only finitely
6many data of L the IIM reached its (unknown) point of convergence and it computed acorrect and finite description of a generator for the target language. Hence, some form oflearning must have taken place. Therefore, we use the terms infer and learn as synonyms
for identify.
In the above Definition LIM stands for “limit.” Furthermore, the prefix C is used toindicate class-comprising learning, i.e., the fact that L may be learned with respect tosome hypothesis space comprising range(L). The restriction of CLIM to class preserving
inference is denoted by LIM . That means LIM is the collection of 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 withrespect to the hypothesis space L itself, then we replace the prefix C by E, i.e., ELIM is thecollection of indexed families that can be exactly learned in the limit. Finally, we adopt
this convention in defining all the learning types below.
Moreover, an IIM is required to learn the target language from every text for it. Thismight lead to the impression that an IIM mainly extracts the range of the information fed
to it, thereby neglecting the length and order of the data sequence it reads. IIMs reallybehaving thus are called set-driven. More precisely, we define:
Definition 2. (Wexler and Culicover, Sec. 2.2, [23]) Let L be an indexed family.
An IIM M is said to be set-driven with respect to L iff its output depends only on
the range of its input; that is, iff M (tx ) = M (t̂y ) for all x, y ∈ IN, all texts t, t̂ ∈ text(L)+provided t+
x = t̂y .

Whenever the relevant indexed family L is clear from the context we refer to set-driven
with respect to L as set-driven for short. Schäfer-Richter [20] as well as Fulk [5], later, andindependently proved that set-driven IIMs are less powerful than unrestricted ones. Fulk
[5] interpreted the weakening 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
fixed computable function depending exclusively on the size of the range of the input, sinceotherwise set-drivenness would not restrict the learning power. Indeed, Osherson, Stob andWeinstein [19] proved that any non-recursive IIM M may be replaced by a non-recursive

7

set-driven IIM M̂ learning at least as much as M does. With the next definition we consider
a natural weakening of Definition 2.
Definition 3. (Schäfer-Richter [20], Osherson et al. [19]) Let L be an indexedfamily. An IIM M is said to be rearrangement-independent with respect to L iff its
output depends only on the range and on the length of its input; that is, iff M (tx ) = M (t̂x )+for all x ∈ IN, all texts t, t̂ ∈ text(L) provided t+
x = t̂x .

Whenever the relevant indexed family L is clear from the context we refer to rearrangement-independent with respect to L as rearrangement-independent for short. Furthermore,
we make the following convention. For all the learning models in this paper we use theprefix s-, and r- to denote the learning model restricted to set-driven and rearrangementindependent IIMs, respectively. For example, s-LIM denotes the collection of all indexedfamilies that are LIM –inferable by some set-driven IIM. Next we formalize the other inference
models that we have mentioned in the introduction.
Definition 4. (Gold [6]) Let L be an indexed family, let L be a language, and let
G = (Gj )j∈IN be a hypothesis space. An IIM M CFIN–identifies L from text iff forevery text t for L, there exists a j ∈ IN such that M, when successively fed t, outputs the
single hypothesis j, L = L(Gj ), and stops thereafter.
Furthermore, M CFIN –identifies L with respect to G iff, for each L ∈ range(L), M
CFIN –identifies L from text with respect to G.
The resulting learning type is denoted by CFIN .
Consequently, every hypothesis produced by a finitely working IIM has to be a correct
guess.
The next definition formalizes the different notions of monotonicity.
Definition 5. (Jantke [8], Wiehagen [24]) 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 withrespect to G(A) strong-monotonically(B) monotonically8(C) weak-monotonicallyiff
M CLIM –identifies L from text with respect to G and for any text t ∈ text(L) as well
as for any two consecutive hypotheses jx , jx+k which M has produced when fed tx and tx+k
where 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 ).
By CSMON CMON , and CWMON , we denote the collection of all indexed families
L for which there are an IIM M and a hypothesis space G such that M infers L strongmonotonically, monotonically, and weak–monotonically, respectively, with respect to the
hypothesis space G.
Note that the learning types λSMON , λMON , and λWMON do heavily depend on
λ ∈ {E, ε, C} as the following proposition shows (cf. Lange and Zeugmann [12, 14] andLange, Zeugmann and Kapur [16]).
Proposition 1.
ELIM

=

∪

LIM

=

∪

CLIM
∪

EWMON ⊂ WMON ⊂ CWMON
∪
EMON

∪
⊂

∪
ESMON

⊂

∪
⊂

∪
EFIN

MON

∪

SMON

∪
⊂

∪
=

FIN

CMON

CSMON
∪

=

CFIN

Next, we define conservative learning. Intuitively speaking, conservative IIMs maintaintheir actual hypothesis at least as long they have not seen data contradicting it. Hence,
9

whenever a conservative IIM performs a mind change it is because it has perceived clear
inconsistency between its guess and the input.
Definition 6. (Angluin [2]) 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–identifies L
from text with respect to G iff(1) M CLIM –identifies L from text with respect to G,(2) for every text t for L the following condition is satisfied:
if M on input tx makes the guess jx and then outputs the hypothesis jx+k 6= jx at somesubsequent step, then t+
x+k 6⊆ L(Gjx ).
Finally, M CCONSERVATIVE –identifies L with respect to G iff, for each L ∈ range(L),M CCONSERVATIVE –identifies L from text with respect to G.
The collection of indexed families CCONSERVATIVE is defined in an analogous manner
as above. The following proposition completely clarifies the relations between conservative
and weak-monotonic learning.
Proposition 2. (Lange and Zeugmann [11])λWMON = λCONSERVATIVE for all λ ∈ {C, ε, E}.
Finally, some of the proofs given below use the notion of uniformly recursively generable
families of finite sets (Tj )j∈IN . Therefore, we present the definition here. A family of finite
sets (Tj )j∈IN is said to be uniformly recursively generable iff there is a total effective
procedure which, on every input j, generates all elements of Tj and stops. If the procedure
stops without any output, the corresponding set is empty.

3. Learning with Set-driven IIMs
In this section we study the question under what circumstances set-drivenness does restrict
the power of the learning models defined above. We start with finite learning. The next
theorem in particular states that finite learning is invariant with respect to the specific choiceof the hypothesis space. Moreover, for every hypothesis space comprising the target indexed10

family L there is a set-driven IIM that finitely learns L.
Theorem 1. EFIN = FIN = CFIN = s-EFIN .
Proof. EFIN = FIN = CFIN is due to Lange and Zeugmann [12]. It remains to showthat EFIN ⊆ s-EFIN .
Let L ∈ EFIN . From the characterization theorem for finite learning (cf. Lange andZeugmann [10]) it follows that there exists a recursively generable family (Tj )j∈IN of finite
nonempty sets such that(1) for all j ∈ IN, Tj ⊆ Lj ,(2) for all j, k ∈ IN, if Tj ⊆ Lk , then Lk = Lj .
Using this recursively generable family (Tj )j∈IN we define an IIM M witnessing L ∈s-EFIN . Let L ∈ range(L), t ∈ text(L), and x ∈ IN.
IIM M: “On input tx do the following: If x = 0 or x > 0 and M , when successively fed
tx−1 , does not stop, then execute Stage x.
+
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, output nothing and request the next input.”
It remains to show that M s-EFIN –infers L. By construction, M uses L as its hypothesis
space.
Claim 1. M finitely infers L.
Let L ∈ range(L) and let t ∈ text(L). We have to show that M stops sometimes, saywith j, and that L = Lj . Let k be the least number satisfying L = Lk . By Property (1),Tk ⊆ Lk . Since range(t) = L, there must be an x such that Tk ⊆ t+
x . Now, there is only one
case imaginable that could prevent M stopping. Namely, there exists a j < k with L ⊂ Lj+
and Tj 6⊆ L. Clearly, in this case M would verify t+y ⊆ Lj but it never verifies Tj ⊆ ty .

However, since L ⊂ Lj , and L = Lk we conclude Tk ⊆ Lj . Therefore, L = Lj by Property(2), a contradiction. Consequently, M has to stop sometimes. Suppose, M , when fed ty ,11

outputs j and stops. But then, in accordance with M ’s definition, M has verified t+y ⊆ Ljand Tj ⊆ t+y . Hence, Tj ⊆ Lk . By Property (2), we directly obtain Lj = Lk = L. This
proves Claim 1.
Claim 2. M is set-driven.
Let L, L̂ ∈ range(L), let t ∈ text(L), t̂ ∈ text(L̂), and let x, y ∈ IN be any numbers+
such that t+
x = t̂y . We have to show that M (tx ) = M (t̂y ). Suppose, M executes Stage x

for tx and Stage y for t̂y , respectively. Since L ∈ range(L), there exist numbers k, m suchthat L = Lk and L̂ = Lm , respectively. Hence, M finds least indices i, j for tx and t̂y ,+++respectively, such that t+x ⊆ Li and t̂y ⊆ Lj . Because of tx = t̂y , we may conclude i = j.

Since the tell-tale sets Tj are uniformly recursively generable, M can effectively compute Tj .
+If Tj 6⊆ t+
x , then Tj is not a subset of t̂y either. Hence, in this case M does not output a+hypothesis when fed tx and t̂y , respectively. On the other hand, if Tj ⊆ t+
x then Tj ⊆ t̂y .

Therefore, M (tx ) = M (t̂y ) = j.
Finally, suppose M has stopped when successively fed tx−1 . Clearly, then M has output
a hypothesis, say j. We have to show that M (t̂y ) = j. Since M finitely infers L, we knowthat Lj = L. Moreover, M has verified that Tj ⊆ t+z ⊆ Lj for some z < x. By assumption,+++t+
x = t̂y , and therefore tz ⊆ t̂y . We distinguish the following two cases.

Case 1. M when successively fed t̂y−1 does not stop.
In accordance with M ’s definition we know that M executes Stage y on input t̂y . Since+
j is the least index with Tj ⊆ t+z ⊆ Lj and since Lj = L, we conclude tx ⊆ Lj . Because
+
+
+
+
of t+
x = t̂y and Tj ⊆ tz ⊆ t̂y , it immediately follows that Tj ⊆ t̂y ⊆ Lj . Hence, M , whensuccessively fed t̂y , has to output a hypothesis, say n, and to stop. Suppose, n 6= j. Since+++
Tj ⊆ t̂+y ⊆ Lj , we directly obtain n < j. On the other hand, tz ⊆ t̂y and t̂y ⊆ Ln imply+t+z ⊆ Ln . Therefore, if Tn 6⊆ tr for all r < x then M does not stop when successively fed

tx−1 . However, by assumption M has stopped. Thus it must have verified Tn ⊆ t+z , sincez < x. Consequently, M (tz ) = n, a contradiction to n 6= j. Hence, M , when executing Stagey, outputs j and stops.
Case 2. M when successively fed t̂y−1 stops.

12By construction, M , when successively fed t̂y−1 , executes some Stage r, r ≤ y −1, outputs
a hypothesis, say n, and stops. Hence, M has verified Tn ⊆ t̂+r ⊆ Ln . We have to show thatn = j. Suppose the converse, i.e., j 6= n. Again, since j is the least index with Tj ⊆ t+z ⊆ Lj++and since Lj = L as well as Lj ⊇ t+
x = t̂y , we may conclude t̂r ⊆ Lj . Therefore, j 6= n

implies n < j. On the other hand, n = M (t̂r ) implies Ln = L̂, since M finitely learns L.
++
Because of Ln ⊇ t̂+y = tx , it immediately follows that tz ⊆ Ln . Finally, since M (tz ) = j, thedefinition of M directly implies j < n, a contradiction. Hence, we obtain j = n.

2

As we have already mentioned, the examples of Schäfer-Richter [20] and Fulk [5] witnessing the restriction of set-driven learners are not indexed families. Hence, we ask whether
the uniform recursiveness of all target languages may compensate the impact to learn with
set-driven IIMs. The answer is no as the following theorem impressively shows.
Theorem 2. s-CLIM ⊂ ELIM = LIM = CLIM .
Proof. The part ELIM = LIM = CLIM is due to Lange and Zeugmann [14]. It remains
to show that s-CLIM ⊂ ELIM .
The desired indexed family 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 bm1 ≤ 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.
Claim 1. L 6∈ s-CLIM .
Since the halting problem is undecidable, Claim 1 follows by contraposition of the following Claim 2.
13

Claim 2. If there exists an IIM M witnessing L ∈ s-CLIM , then one can effectively
construct an algorithm deciding for all k ∈ IN whether or not ϕk (k) converges.
Let M be any IIM that learns L in the limit with respect to some hypothesis space G
comprising range(L). We define an algorithm A that solves the halting problem.
Algorithm A: “On input k execute (A1) and (A2).
(A1) For z = 0, 1, 2, ... generate successively the canonical text t of Lhk,0i until M on
k z+2
input tz outputs for the first time a hypothesis j such that t+} ⊆ L(Gj ).
z ∪ {a b(A2) Test whether Φk (k) ≤ z + 1. In case it is, output ‘ϕk (k) converges.’
Otherwise output ‘ϕk (k) diverges’ and stop.
Since M has to infer Lhk,0i in particular from t, there has to be a least z such that M
k z+2
on input tz computes a hypothesis j satisfying t+} ⊆ L(Gj ). Moreover, the testz ∪ {a bk z+2
whether or not t+} ⊆ L(Gj ) can be effectively performed, since membership inz ∪ {a b

L(Gj ) is uniformly decidable. By the definition of a complexity measure, Instruction (A2)is effectively executable. Hence, A is an algorithm.
It remains to show that ϕk (k) diverges, if ¬ Φk (k) ≤ z + 1. Suppose the converse; thenthere exists a y > z + 1 with Φk (k) = y. In accordance with the definition of L, we obtain
L = t+z ∈ L. Hence, tz is also an initial segment of a text t̂ for L. Due to the definition of A,
we have L(Gj ) 6= L. Since M is a set-driven IIM, L = t+z implies M (t̂z+r ) = j for all r ∈ IN.
Therefore, M fails to infer L from its text t̂. This contradicts our assumption that M is a
set-driven IIM which CLIM –infers L with respect to G. Hence, Claim 2 is proved.
Claim 3. L ∈ ELIM .
After a little reflection, it is easy to verify that the following IIM M infers L in the limit
with respect to the hypothesis space L. Let L ∈ range(L), let t ∈ text(L), and let x ∈ IN.
We define:
IIM M: “On input tx do the following: Determine the unique k such that t0 = ak bm forsome m ∈ IN. Test whether or not Φk (k) ≤ x. In case it is, goto (1). Otherwise,
output hk, 0i and request the next input.
14

(1) Test whether or not ak bΦk (k)+n ∈ t+
x for some n ∈ IN. In case it is, output hk, 0i
and request the next input. Otherwise, goto (2).
(2) Determine the maximal z ∈ IN such that ak bz ∈ t+
x . Output hk, 2 · Φk (k) − zi andrequest the next input.”2
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 careful choice ofthe hypothesis space deserves special attention whenever set-drivenness is desired. The first
result nicely contrasts the fact that unconstraint language learning is invariant with respect
to the particular choice of the hypothesis space.
Theorem 3. s-ELIM ⊂ s-LIM ⊂ s-CLIM .
Proof. By definition s-ELIM ⊆ s-LIM ⊆ s-CLIM . It remains to show that the statedinclusions are proper. First, we separate s-LIM and s-ELIM .
The target indexed family L = (Lhk,ji )k,j∈IN is defined as follows. Without loss of generality, we may assume that Φk (k) ≥ 1 for all k ∈ IN. We set Lhk,0i = {ak b} ∪ {ak bΦk (k)+1 } for allk ∈ IN. Notice that {ak bΦk (k)+1 } equals the empty set, if ϕk (k) is undefined. Furthermore,
for all j ≥ 1 we distinguish the following cases.
Case 1. ¬ Φk (k) = j
Then let Lhk,ji = {ak b, ak bj+1 }.
Case 2. Φk (k) = j
Then we set Lhk,ji = {ak b}.
Obviously, L = (Lhk,ji )k,j∈IN constitutes an indexed family.
Claim 1. L ∈ s-LIM .
Consider the following hypothesis space G = (Ghk,ji )k,j∈IN . For all k, j ∈ IN let L(Ghk,ji ) ={ak b, ak bj+1 }. After a little reflection, it is not hard to see that range(L(G)) = range(L).
Now, a set-driven IIM M which LIM–infers L with respect to G can be designed as follows.
Given any initial segment tx of any text t for any language L ∈ range(L), M simply deter15

mines the relevant k and searches the least index j such that t+
x ⊆ Ghk,ji . Then it outputs
the hypothesis hk, ji. We omit the details.
Claim 2. L 6∈ s-ELIM .
This claim is proved via the following lemma.
Lemma 1. Let M be any set-driven IIM witnessing L ∈ ELIM . Then M may be used
to decide the halting problem.
Proof. We define an algorithm B as follows.
Algorithm B: “On input k execute Instruction (B).
(B) Compute hk, ji = M (ak b). If j = 0, output ‘ϕk (k) ↑’ and stop.
Else, output ‘ϕk (k) ↓,’ and stop.”
By assumption, M has to learn {ak b} in the limit from its unique text t = ak b, ak b, .... Since
M is set-driven, it must make an output on input ak b. Moreover, this output has to be acorrect hypothesis, i.e., M (ak b) = hk, ji, and {ak b} = Lhk,ji . Therefore, B terminates on
every input k. It remains to show that B behaves correctly.
Suppose, B outputs ‘ϕk (k) ↑’ but ‘ϕk (k) ↓.’ Let Φk (k) = y. By assumption, y ≥ 1. Now,
looking at L’s definition, one easily verifies that Lhk,0i = {ak b, ak by+1 }. But this directly
contradicts Lhk,0i = {ak b}. Hence, B behaves correctly if it outputs ‘ϕk (k) ↑.’Now suppose that B outputs ‘ϕk (k) ↓.’ By construction, j 6= 0, and as already mentioned Lhk,ji = {ak b}. Taking L’s definition into account we can conclude that j = Φk (k).
Consequently, ϕk (k) is indeed defined. This proves Lemma 1.
Since the halting problem is not recursive, the contraposition of Lemma 1 yields Claim 2.
Finally, we have to separate s-CLIM and s-LIM . However, this separation is an immediate consequence of the following slightly stronger theorem, and therefore we omit its proof
2

here.
Theorem 4. There is an indexed family L such that
(1) L ∈ r-ESMON ,16

(2) L ∈/ s-LIM ,(3) L ∈ s-CSMON .
Proof. The desired indexed family L = (Lhk,ji )k,j∈IN is defined as follows. For all k ∈ IN
we set Lhk,0i = {ak bm

m ∈ IN+ }. For all j ∈ IN+ we distinguish the following cases.

Case 1. ¬ Φk (k) ≤ j
Then we define Lhk,ji = Lhk,0i .
Case 2. Φk1 (k1 ) ≤ j
Then we set Lhk,ji = {ak b}.
Claim 1. L ∈ r-ESMON .
We have to define an IIM witnessing L ∈ r-ESMON . This is done as follows: Let
L ∈ range(L), t ∈ text(L), and x ∈ IN.
IIM M: “On input tx do the following: Compute the unique k such that ak bm ∈ t+x forksome m ∈ IN. As long as t+
x = {a b} execute (A).

Otherwise, output hk, 0i and request the next input.
(A) Test whether or not ¬ Φk (k) ≤ x. In case it is, output nothing and request thenext input.
Otherwise, output hk, Φk (k)i and request the next input.”
Obviously, M is rearrangement-independent. In order to prove that M ESMON –infers
L we distinguish the following cases.
Case 1. ϕk (k) ↑In accordance with the definition of the indexed family L we directly obtain L = Lhk,0i =k
Lhk,ji for all j ∈ IN. Since t ∈ text(L), there has to be an x such that t+
x 6= {a b}. Conse-

quently, after having seen tx the IIM M always outputs hk, 0i, a correct hypothesis. Moreover, M obviously behaves strong-monotonically.
Case 2. ϕk (k) ↓17

Suppose, L = {ak b}. Since t ∈ text(L), M executes Instruction (A) on every input tx .
Moreover, there exists an x0 such that Φk (k) ≤ x for all x ≥ x0 . Hence, after having seentx0 the IIM M always outputs the correct hypothesis hk, Φk (k)i.
Now, let us assume L = Lhk,0i . As we have shown in Case 1, there exists an x ∈ INksuch that t+
x 6= {a b}. Consequently, for all y ≥ x we have M (ty ) = hk, 0i and M again

learns L. Finally, it might happen that M outputs hk, Φk (k)i on some initial segment oft and changes its mind to hk, 0i afterward. Clearly, this mind change fulfills the strongmonotonicity constraint. Hence, M witnesses L ∈ r-ESMON .
Claim 2. L ∈/ s-LIM .
Applying mutatis mutandis the same idea underlying the proof of Theorem 3, Claim 2,L∈/ s-LIM can be shown by reducing the halting problem to L ∈ s-LIM . For the sake ofcompleteness we present the modification of Algorithm B.
Algorithm B̃: “On input k execute Instruction (B1).
(B1) Simulate M on input ak b. If M requests the next input without outputting a hypothesis, then output ‘ϕk (k) ↑,’ and stop.
Otherwise, let z = M (ak b). Execute Instruction (B2).
(B2) Test whether or not ak b2 ∈ L(Gz ).
In case it is, output ‘ϕk (k) ↑.’Else, output ‘ϕk (k) ↓,’ and stop.”
Claim 3. L ∈ s-CSMON .
First of all we define the desired class-comprising hypothesis space. For all j ∈ IN we set
L(Gj ) = Lhk,0i ,if j = 2k, {ak b},

if j = 2k + 1.

Obviously, G = (Gj )j∈IN is an admissable hypothesis space. A set-driven IIM M witnessing L ∈ CSMON may be easily defined as follows. As long as it receives an initial segmentkk+
tx of a text t such that t+
x = {a b} it outputs 2k + 1. If {a b} ⊂ tx , it hypothesizes 2k. We

2omit the details.
18

Theorem 4 directly yields the following corollary which relates the power of set-driven
and unrestricted IIMs to one another.
Corollary 5. For all ID ∈ {SMON , MON , WMON }:(1) s-EID ⊂ EID,
(2) s-ID ⊂ ID.
Proof. By Theorem 4 we have r-ESMON \s-LIM 6= ∅. This yields all the proper inclusions
mentioned, since ESMON ⊂ SMON , ESMON ⊂ EID ⊂ ID for all ID ∈ {MON , WMON }(cf. Proposition 1) as well as s-EID ⊆ s-ID ⊆ s-LIM for all ID ∈ {SMON , MON , WMON }2

by definition.

As we have seen, set-drivenness constitutes a severe restriction. While this is true ingeneral as long as exact and class-preserving learning is considered, the situation is different
in the class-comprising case. On the one hand, learning in the limit cannot always beachieved by set-driven IIMs (cf. Theorem 2). On the other hand, conservative learners may
always be designed to be set-driven, if the hypothesis space is appropriately chosen.
Theorem 6.

s-CCONSERVATIVE = CCONSERVATIVE.

Proof. We partition the proof into two parts. First, we show that every indexed family in
CCONSERVATIVE belongs to r-CCONSERVATIVE (cf. Lemma 2) below. Then we apply
this result and show that set-drivenness does not restrict the power of class-comprisingconservative learning (cf. Lemma 3).
Lemma 2. r-CCONSERVATIVE = CCONSERVATIVE.
Let L ∈ CCONSERVATIVE . By Theorem 14 in Lange and Zeugmann [13] there exista hypothesis space G = (Gj )j∈IN and a recursively generable tell-tale family (Tj )j∈IN of finite
and nonempty sets such that(1) range(L) ⊆ range(L(G)),(2) for all j ∈ IN, Tj ⊆ L(Gj ),(3) for all j, k ∈ IN, if Tj ⊆ L(Gk ), then L(Gk ) 6⊂ L(Gj ).
19

Using this tell-tale family, we define a new recursively generable family (T̂j )j∈IN of finite
and nonempty sets that allows the design of a rearrangement-independent IIM inferring L
S

conservatively with respect to G. For all j ∈ IN we set T̂j = n≤j Tn ∩ L(Gj ).
It is easy to see that (T̂j )j∈IN fulfills (2) and (3), too. Next, we show the following evenstronger result.
Statement 1. L(G) ∈ r-ECONSERVATIVE.
The desired IIM is defined as follows. Let L ∈ range(L(G)), t ∈ text(L), and x ∈ IN.
IIM M: “On input tx do the following: 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, andrequest the next input.
Otherwise, output nothing and request the next input.”
Obviously, M is rearrangement-independent.
Claim 1. M is conservative.
Let k and j be two distinct 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 < k+Suppose, 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 Tj ⊆ tx ⊆ L(Gj ).
Finally, since j < k we conclude M (tx ) = j, a contradiction. Hence, Claim 1 is proved.
Claim 2. M infers L from t.
Let z be the least k such that L(Gk ) = L, hereafter denoted as z = µk [L(Gk ) = L].
Therefore, L(Gj ) 6= L for all j < z. Applying 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, Claim 2 follows and Statement 1 is proved.
20

Finally, since range(L) ⊆ range(L(G)), we may conclude that M r -CCONSERVATIVE –infers L. This completes the proof of Lemma 2.
Lemma 3. Let L be any indexed family. If L ∈ CCONSERVATIVE , then there exista hypothesis space G̃ = (G̃j )j∈IN and an IIM M̃ witnessing L ∈ s-CCONSERVATIVE withrespect to G̃.
First, we define the hypothesis space G̃ = (G̃j )j∈IN as follows. Applying Lemma 2, there
are a hypothesis space G = (Gj )j∈IN and an IIM M such that M r -CCONSERVATIVE –learns
L with respect to G. Moreover, M witnesses L(G) ∈ r -ECONSERVATIVE . Afterwards, we
use the latter statement and show a more general result which turns out to be quite helpful
in order to prove Corollary 7. The hypothesis space G̃ is the canonical enumeration of all
grammars from G and all finite languages over the underlying alphabet Σ. Second, the main
ingredient to the definition of the desired IIM M̃ is the machine M from Lemma 2. However,before defining it we introduce 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 ).
Statement 2. L(G) ∈ s-CCONSERVATIVE with respect to G̃.
Now, let L ∈ range(L(G)), t ∈ text(L), and x ∈ IN.
IIM M̃: “On input tx do the following: Compute rf (tx ). If M on input rf (tx ) outputs ahypothesis, say j, then output 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.”
Claim 3. M̃ is set-driven.
+
Let t, t̂ ∈ text(L), and let x, y ∈ IN such that t+
x = t̂y . We have to show that M̃ (tx ) =M̃ (t̂y ). Clearly, length(rf (tx )) = length(rf (t̂y )), and therefore we conclude M (rf (tx )) =M (rf (t̂y )), since M is rearrangement-independent. That means, either M outputs in bothcases the same hypothesis or it outputs nothing on input rf (tx ) and rf (t̂y ), respectively.
This proves Claim 3.
Claim 4. M̃ is conservative.
21

By construction, M̃ outputs on every input a hypothesis. Let j = M̃ (tx ) and k = M̃ (tx+1 )+with j 6= k. Since M̃ is set-driven, we obtain t+
x ⊂ tx+1 . We consider the following cases.

Case 1. M on input rf (tx ) does not output a hypothesis.
+
Then L(G̃j ) = t+
x , and consequently, tx+1 6⊆ L(G̃j ). Hence, M̃ performs a justified mindchange.
Case 2. M on input rf (tx ) outputs a hypothesis.
Obviously, rf (tx ) is a proper initial segment of rf (tx+1 ). Suppose, M on input rf (tx+1 )produces a hypothesis, too. Since M is conservative, we immediately obtain tx+1 6⊆ L(G̃j ).
Hence, it remains to consider the scenario in which M on input rf (tx+1 ) does not produce ahypothesis. Looking at M ’s definition, we see that M could be prevented from doing it only
by detecting an inconsistency. Consequently, M̃ is conservative, and Claim 4 is proved.
Claim 5. M̃ infers L from t.
Again, we distinguish two cases.
Case 1. L is finite.
Then there exists an x ∈ IN such that t+
x = L. Moreover, if M on input rf (tx ) producesa hypothesis, then it is a correct one, since M is conservative. Hence, in this case M̃ infers
L from t. On the other hand, if M on input rf (tx ) does not output a hypothesis, then M̃converges to the canonical index of the finite language t+
x in G̃, since M̃ is set-driven.
Case 2. L is infinite.
Since L is infinite, rf (t) is a text for L, too. Moreover, M has to infer L in particularfrom rf (t). Therefore, there exists an x ∈ IN such that M (rf (t)x+r ) = k with L(Gk ) = L for
all r ∈ IN. Hence, after some point M̃ exclusively outputs the canonical index of L(Gk ) inG̃. Consequently, M̃ infers L. This completes the proof of Claim 5.
Therefore, Statement 2 is proved. Since range(L) ⊆ range(L(G)), we immediately may
conclude that M̃ CCONSERVATIVE –learns L with respect to G̃. This completes the proof
2of Lemma 3.
Corollary 7.

Let L ∈ CCONSERVATIVE . Then, there exists a hypothesis space22Ĝ = (Ĝj )j∈IN comprising range(L) such that L(Ĝ) ∈ s-ECONSERVATIVE .
Proof. Let L ∈ CCONSERVATIVE . Furthermore, due to the latter theorem, there are a
set-driven IIM M̃ and a hypothesis space G̃ such that M̃ conservatively infers L with respect
to G̃. Let M̃ and G̃ be defined as in Lemma 3.
Recall that G̃ is a canonical enumeration of G = (Gj )j∈IN with range(L) ⊆ range(L(G))
and of 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 ) ∈ range(L(G)).
Hence, M̃ s-CCONSERVATIVE –learns L(G̃j ) with respect to G̃. Otherwise, L(G̃j ) is a
finite language.
We start with the definition of the desired hypothesis space Ĝ = (Ĝj )j∈IN If j is even,then we set Ĝj = G̃j . Otherwise, we distinguish the following cases. If M , when fed thelexicographically ordered enumeration of all strings in L(G̃j ) outputs the hypothesis j, thenwe 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 .
Let L ∈ range(L(Ĝ)), t ∈ text(L), and x ∈ IN.
IIM M: “On input tx do the following: Simulate M̃ on input tx . If M̃ does not output any
hypothesis, then output nothing and request the next input.
Otherwise, let j = M̃ (tx ). 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, since M̃
s-CCONSERVATIVE –infers L. Therefore, since M simulates M̃ , we are done.
Now, let us suppose, L 6= L(Ĝ2k ) for all 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 for all 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 all y ≥ x. Consequently, M learns L.
Next we characterize class-comprising set-driven learning in the limit.
23

2

Theorem 8.

s-CLIM = CCONSERVATIVE .

Proof. CCONSERVATIVE ⊆ s-CLIM immediately follows from Theorem 6. It remains
to handle the part s-CLIM ⊆ CCONSERVATIVE .
Let L be any indexed family and M̂ a set-driven IIM which learns L with respect to ahypothesis space Ĝ = (Ĝj )j∈IN . Without loss of generality, we may assume that M̂ , when fed
any finite sequences σ of strings over the terminal alphabet Σ, always outputs a consistenthypothesis, i.e., if M̂ (σ) = j then σ + ⊆ L(Ĝj ) (cf. Lange, Zeugmann and Kapur [16] for a
detailed discussion).
We show that M̂ can be simulated by a conservative IIM M which also learns L. First,
we define a suitable hypothesis space G = (Ghj,ki )j,k∈IN .
For the sake of readability, in the following we consider the set-driven IIM M̂ as a learning device which receives finite sets of strings as input instead of finite sequences. Let
F0 , F1 , F2 , . . . denote any effective repetition-free enumeration of all finite subsets fromΣ∗ . Given any finite set F ⊆ Σ∗ , we denote by #(F ) the uniquely determined index n with
Fn = F . For all j, k ∈ IN let us distinguish the following cases.
If M̂ (Fk ) 6= j, then we set L(Ghj,ki ) = Fk . Otherwise, i.e., M̂ (Fk ) = j, the language
L(Ghj,ki ) will be specified as a subset of L(Ĝj ) such that Fk ⊆ L(Ghj,ki ). For that purpose,
we define L(Ghj,ki ) via its characteristic function fL(Ghj,ki ) .
Let s0 , s1 s2 , . . . be the lexicographically ordered enumeration of all strings in Σ∗ . Let
m = 0. If s0 ∈ Fk , then set fL(Ghj,ki ) (s0 ) = 1. If s0 ∈ L(Ĝj ) \ Fk and M̂ (Fk ∪ {s0 }) = j, thenlet fL(Ghj,ki ) (s0 ) = 1. Otherwise, we set fL(Ghj,ki ) (s0 ) = 0. Now we proceed inductively. Letn ≤ m, fL(Ghj,ki ) (sn ) = 1}. Then we define:m ∈ IN and F = {sn




1,






if sm+1 ∈ Fk ,fL(Ghj,ki ) (sm+1 ) =  1, if sm+1 ∈ L(Ĝj ) \ Fk , M̂ (Fk ∪ V ∪ {sm+1 }) = j for all V ⊆ F,







0, otherwise.

By construction, G defines a hypothesis space having a uniformly decidable membershipproblem. First we show that range(L) ⊆ range(L(G)). Let L ∈ range(L). Since M̂ is a
set-driven IIM that learns L, there has to be a finite set F ⊆ L such that, for all finite sets24V ⊆ L, M̂ (F ) = M̂ (F ∪ V ) = j, and L(Ĝj ) = L (cf. Fulk [5]). Hence, we may conclude that
L = L(Ghj,ki ), where k = #(F ). Consequently, G defines an admissible hypothesis space
which comprises range(L).
Furthermore, G’s definition immediately implies:
Observation 1. Let V ⊆ L(Ĝj ) and k ∈ IN such that M̂ (Fk ) = j. Then V ⊆ L(Ghj,ki )implies M̂ (Fk ∪ V ) = j.
Now, we are ready to define the desired conservative IIM M which works with respect tothe hypothesis space G. Let L ∈ range(L), t ∈ text(L), and x ∈ IN.
IIM M: “On input tx do the following: If x = 0, compute M̂ (t+0 ) = j. Output the guess
hj, #(t+0 )i and request the next input. Otherwise, goto (A).
(A) Let M (tx−1 ) = hj, ki. Test whether or not t+
x ⊆ L(Ghj,ki ). In case it is, output
hj, ki and request the next input.
+
Else, compute M̂ (t+x ) = z. Output the guess hz, #(tx )i and request the next

input.”
By definition, M outputs in every step a guess. Moreover, M performs exclusively justified
mind changes. Thus, M is a conservative IIM. Next we show that M learns L from text t.
Claim 1. When fed t, M never outputs a guess z such that L ⊂ L(Gz ).
Let x ∈ IN, M (tx ) = z, and let y ≤ x be the least index such that M (ty ) = z. By definition++z = hj, ki where M̂ (t+y ) = j and k = #(ty ). Thus M̂ (ty ) = M̂ (Fk ) = j, and consequently

L(Ghj,ki ) ⊆ L(Ĝj ) in accordance with the definition of G. Recall that t+x ⊆ L(Ghj,ki ). Hence,t+x ⊆ L(Ĝj ), too. Therefore, the assumptions of Observation 1 are fulfilled and we concludeM̂ (t+x ) = j. We distinguish the following two cases:
Case 1. t+
x = L
Therefore, L(Ĝj ) = L, since M̂ is a set-driven IIM which learns L. Because of t+x ⊆L(Ghj,ki ) ⊆ L(Ĝj ), we may conclude L = L(Ghj,ki ).
Case 2. t+
x ⊂ L
Suppose the converse, that is L ⊂ L(Ghj,ki ). Because of L(Ghj,ki ) ⊆ L(Ĝj ), we also25

have L ⊂ L(Ĝj ). Since M̂ learns L, there is an r ∈ IN+ such that M̂ (t+x+r ) = n andL(Ĝn ) = L. Obviously, L ⊂ L(Ĝj ) implies t+
x+r ⊆ L(Ĝj ). On the other hand, L ⊂ L(Ĝj )yields immediately j 6= n. Thus, by contraposition of Observation 1, we may conclude that+t+x+r 6⊂ L(Ghj,ki ). This contradicts L ⊂ L(Ghj,ki ), since tx+r ⊆ L.

It remains to show that M , when fed t, converges to a correct guess for L. Since M never
outputs an overgeneralized hypothesis and, additionally, M exclusively performs justified
mind changes, it suffices to show:
Claim 2. When fed t, M outputs at least once a correct guess.
Since M̂ is a set-driven IIM which learns L, there has to be a a finite set F ⊆ L suchthat, for all finite sets V ⊆ L, M̂ (F ) = M̂ (F ∪ V ) = j, and L(Ĝj ) = L (cf. Fulk [5]). By
G’s definition L(Ghj,#(F )i ) = L as well as L(Ghj,#(F ∪V )i ) = L for all finite sets V ⊆ L. Sincet defines a text for L there has to be a least x ∈ IN such that F ⊆ t+
x . Let M (tx ) = z. If
z = hj, #(t+x )i, we are done. Otherwise, L \ L(Gz ) 6= ∅ by Claim 1. Again, since t is a text
for L, there has to be a least r ∈ IN+ such that t+
x+r 6⊆ L(Gz ). By its definition M changes
ist mind to the correct guess hj, #(t+x+r )i when processing tx+r .
Hence, M converges to a correct hypothesis for L. To sum up, M conservatively infers L
2with respect to the hypothesis space G.

At this point it is only natural to ask whether or not the latter theorem remains valid ifclass-comprising learning is replaced by class-preserving inference and exact identification,
respectively. The negative answer is provided by our next theorem. Additionally, thistheorem gives some more evidence that set-drivenness is not that restrictive as it might
seem.
Theorem 9.
(1) s-SMON \ EWMON 6= ∅,(2) s-CSMON \ WMON 6= ∅,(3) s-ELIM \ WMON 6= ∅,(4) s-EWMON \ MON 6= ∅.
26

Proof. First of all, we show Assertion (1). Let us consider the following indexed family
Lsm = (Lhk,ji )j,k∈IN . For all k ∈ IN we set Lhk,0i = {ak bn n ∈ IN+ }. For all k ∈ IN and allj ∈ IN+ we distinguish the following cases:
Case 1. ¬ Φk (k) ≤ j
We set Lhk,ji = Lhk,0i .
Case 2. Φk (k) ≤ j
Then we set Lhk,ji = {ak bm 1 ≤ m ≤ Φk (k)}.
In Lange and Zeugmann [12] it was already shown that the family Lsm is witnessing
SMON \ EWMON 6= ∅. Hence, it remains to show the following claim.
Claim 1. Lsm ∈ s-SMON .
We have to show that there are a hypothesis space G = (Gj )j∈IN with range(Lsm ) =range(L(G)) and a set-driven IIM M such that M strong-monotonically infers L with respect
to G.
TFirst of all, we define the hypothesis space G. For all k ∈ IN, we set L(G2k ) = j∈IN Lhk,jiand L(G2k+1 ) = Lhk,0i .
Since Lsm is an indexed family, it is easy to verify that membership is uniformly decidable
for G. Moreover, we have range(Lsm ) = range(L(G)).
Let L ∈ range(L)sm , let t be any text for L, and let x ∈ IN. The desired IIM M is defined
as follows.
IIM M: “On input tx do the following: Determine the unique k such that t0 = ak bm forsome m ∈ IN. Test whether or not t+
x ⊆ L(G2k ). In case it is, output 2k. Otherwise,
output 2k + 1.”
Obviously, M changes its mind at most once. Since L(G2k ) ⊆ L(G2k+1 ), this mindchange satisfies the strong-monotonicity requirement. Furthermore, M converges to a correct
hypothesis for L. Accordingly to the definition, it is easy to see that M is indeed a set-driven
IIM. This proves Claim 1, and therefore (1) follows.
In order to prove Assertion (2), we use the following indexed family Lcsm = (Lhk,ji )j,k∈IN .
27

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
We set Lhk,ji = Lhk,0i .
Case 2. Φk (k) ≤ j
Then we set Lhk,ji = {ak bm 1 ≤ m ≤ Φk (k)} ∪ {ak bm m ≥ j}.
By reducing the halting problem to Lcsm ∈ WMON , one may prove that Lcsm 6∈ WMON .
An IIM M witnessing Lcsm ∈ s-CSMON can be easily designed, if one chooses the followingThypothesis space G = (Ghk,ji )j,k∈IN . For all k, j ∈ IN, we set L(Ghk,0i ) = j∈IN Lhk,ji andL(Ghk,j+1) ) = Lhk,ji . We omit further details.
Furthermore, the family Lcsm is witnessing Assertion (3) as well. To see this, recall thats-CSMON ⊆ CLIM = ELIM . Assume any IIM M̂ which ELIM –identifies L. Since L
contains exclusively infinite languages, it is easy to see that the following set-driven IIM M
infers L, too. Let L ∈ range(Lcsm ), let t be any text for L, and let x ∈ IN. We define:
IIM M: “On input tx do the following: Rearrange the strings contained in t+
x in lexicographical order without repetitions. Let t̂y = w0 , . . . , wy , y ≤ x, be the sequenceobtained.
If M̂ on input t̂y outputs a hypothesis, then output the same guess and request thenext input.
Otherwise, output nothing and request the next input.”
The remaining part can be easily shown. One has simply to choose the indexed family
used in Lange and Zeugmann [11] to separate WMON and MON .
We finish this section with the following corollary.
Corollary 10.
(1) s-ELIM # ECONSERVATIVE ,(1) s-LIM # CONSERVATIVE .
28

2

Proof. By Theorem 9 and Proposition 2 we obtain s-ELIM \ ECONSERVATIVE 6= ∅ aswell as s-LIM \ CONSERVATIVE 6= ∅. Moreover, Theorem 4 together with Proposition 1
and 2 imply ECONSERVATIVE \ s-LIM 6= ∅, and hence Assertion (1) and (2) follow.

2

4. Learning with Rearrangement-Independent IIMs
In this section we study the impact of rearrangement-independence on the learning powerof IIMs. We start with learning in the limit. Angluin [2] characterized the learnability of
those indexed families L that are inferable with respect to the hypothesis space L in termsof finite, and recursively enumerable tell-tales. Actually, she proved the slightly stronger
result that r-ELIM = ELIM . Recently, we showed ELIM = LIM = CLIM (cf. Lange
and Zeugmann [14]), and hence we know that rearrangement-independence does not restrict
the inference power of IIMs that learn in the limit. However, this general result is also a
direct consequence of theorems obtained by Schäfer-Richter [20], and later, but independently by Fulk [5] who proved that any IIM M learning in the limit may be replaced bya rearrangement-independent IIM that infers as least as much than M does. Moreover,Schäfer-Richter’s [20] and Fulk’s [5] result is much stronger than Angluin’s [2], since it is not
restricted to the learnability of indexed families. By the next theorem we summarize theknown results.
Theorem 11. (Angluin [2], Schäfer-Richter [20], Fulk [5])r-ELIM = ELIM = LIM = CLIM .
However, neither Schäfer-Richter’s [20] nor Fulk’s [5] transformation does preserve anyof the monotonicity requirements defined above. And indeed, the situation is more subtle
than we expected. Furthermore, since the power of all types of monotonic language learning
heavily depends on the choice of the hypothesis space, we have to consider separately all the
resulting cases. We start with strong-monotonic inference.
Theorem 12.
(1) r-ESMON = ESMON ,(2) r-SMON = SMON .
29

Proof. First, we prove Assertion (2).
Let L ∈ SMON . Applying the characterization theorem for SMON (cf. Lange andZeugmann [10]), we know that there exist a class- preserving hypothesis space G = (Gj )j∈IN
as well as a recursively generable family (Tj )j∈IN of finite nonempty sets such that(i) for all j ∈ IN, Tj ⊆ L(Gj ),(ii) for all j, k ∈ IN, if Tj ⊆ L(Gk ), then L(Gj ) ⊆ L(Gk ).
On the basis of this family (Tj )j∈IN we define an IIM M witnessing L ∈ r-SMON . So let
L ∈ range(L), t ∈ text(L), and x ∈ IN.
IIM M: “On input tx do the following: Search for the least j ≤ x for which Tj ⊆ t+x ⊆L(Gj ). If it is found, output j and request the next input.
Otherwise, output nothing and request the next input.”
Obviously, M is a rearrangement-independent IIM. It remains to show that M SMON –infers L with respect to the hypothesis space G.
Claim 1. M infers L from text t.
Let k = µz[L(Gz ) = L]. Hence, there is a least x0 such that Tk ⊆ t+
x0 . Therefore, M will
output sometimes a hypothesis. For all j < k with Tj ⊆ L we may conclude that L(Gj ) ⊆ L,
since Tj ⊆ L(Gk ) implies L(Gj ) ⊆ L(Gk ) = L (cf. Property (ii)). Moreover, the choice of kyields L(Gj ) 6= L. Thus, we have L(Gj ) ⊂ L. Hence, for every j < k with Tj ⊆ L there exists
a yj such that t+
yj 6⊆ L(Gj ). Therefore, M (tx ) = k for all x > max{x0 , yj

j < k, Tj ⊆ L}.

This proves Claim 1.
Claim 2. M is strong-monotonic.
Let M (tx ) = j and M (tx+r ) = k for some x ∈ IN and r ∈ IN+ . Due to the definition of M ,+we have Tj ⊆ t+x ⊆ L(Gj ), and Tk ⊆ tx+r ⊆ L(Gk ). Therefore, Tj ⊆ L(Gk ). Now, Property(ii) implies L(Gj ) ⊆ L(Gk ). This proves Claim 2.
To sum up, M is witnessing L ∈ r-SMON . Thus, Assertion (2) is shown.
30

Next, we prove Assertion (1). Let L ∈ ESMON . Because of ESMON ⊆ SMON as well asof Assertion (2), there exist a rearrangement-independent IIM M̂ as well as a class-preserving
hypothesis space G such that M̂ r-SMON –learns L with respect to the hypothesis space G.
Applying Theorem 4 of Lange and Zeugmann [12], we know that there exists some total
recursive function f : IN × IN → IN satisfying(iii) for all j ∈ IN, limx→∞ f (j, x) = k exists and satisfies L(Gj ) = Lk ,(iv) for all j, x ∈ IN, Lf (j,x) ⊆ Lf (j,x+1) .
That means, f is a limiting recursive strong-monotonic compiler from G into L.
Given the IIM M̂ , the hypothesis space G as well as the limiting recursive strongmonotonic compiler f , we define an IIM M witnessing L ∈ r-ESMON . So, let L ∈ range(L),t ∈ text(L), and x ∈ IN.
IIM M: “On input tx do the following: Simulate M̂ on input tx . If M̂ when successively
fed tx does not output any guess, then output nothing and request the next input.
Otherwise, let j = M̂ (tx ). If t+
x ⊆ L(Gj ), then execute (1). Otherwise, output nothing
and request the next input.
(1) Find the least y ∈ IN for which t+x ⊆ Lf (j,y) . Output f (j, y) and request the next
input.”
Since the membership problem for G is uniformly decidable, the test ‘t+x ⊆ L(Gj )’ can beeffectively performed. Additionally, since L is an indexed family, the test within Instruction(1) can be effectively accomplished, too. Furthermore, by Property (iii) of f and sincet+x ⊆ L(Gj ), Instruction (1) has to terminate for every j ∈ IN. Hence, M is indeed an IIM.
Due to its definition, M is a rearrangement-independent IIM, since the IIM M̂ simulated by
M is rearrangement-independent by assumption.
It remains to show that M strong-monotonically infers L from text t. Since M̂ infers Lfrom text t and by Property (iii) of f , M converges to a correct hypothesis for L. Finally,31

we show that M fulfills the strong-monotonicity constraint. Let f (j, y) and f (k, z) denote
two hypotheses successively generated by M . Hence, M (tx ) = f (j, y) and M (tx+r ) = f (k, z)
for some x ∈ IN, r ∈ IN+ . We distinguish the following cases.
Case 1. j = k
Due to the definition of M , we may conclude y ≤ z. Hence, Property (iv) of f guarantees
Lf (j,y) ⊆ Lf (j,z) .
Case 2. j 6= k
Since f satisfies Properties (iii) and (iv), we obtain Lf (j,y) ⊆ L(Gj ). Furthermore, M ’s
definition implies t+
x+r ⊆ Lf (k,z) . Hence, the given IIM M̂ has generated the hypothesis j on
an initial segment of a text for Lf (k,z) ∈ L. Since M̂ behaves strong-monotonically on every
text for every language L ∈ range(L), we may conclude that L(Gj ) ⊆ Lf (k,z) . Together withLf (j,y) ⊆ L(Gj ), we get Lf (j,y) ⊆ Lf (k,z) .
Thus, M is rearrangement-independent and strong-monotonic.

2

Next we deal with exact and class-preserving monotonic learning.
Theorem 13.
(1) s-EMON ⊂ r-EMON ⊂ EMON ,(2) s-MON ⊂ r-MON ⊂ MON .
Proof. First of all, we show r-EMON \s-MON 6= ∅. By definition, this yields immediately
s-EMON ⊂ r-EMON as well as s-MON ⊂ r-MON .
Lemma 4. r-EMON \ s-MON 6= ∅.
By Theorem 4 we already know that r-ESMON \ s-LIM 6= ∅. It is easy to verify
that r-ESMON ⊆ r-EMON . By definition, s-MON ⊆ s-LIM . Hence, we may conclude
r-EMON \ s-MON 6= ∅. This proves Lemma 4.
It remains to show EMON \ r-MON 6= ∅. This statement directly implies r-EMON ⊂EMON and r-MON ⊂ MON , and hence, the theorem will be proved.
Lemma 5. EMON \ r-MON 6= ∅.
32

First of all, we define a corresponding family L = (Lk )k∈IN . For all k ∈ IN and allz ∈ {0, . . . , 3} we define: {ak b} ∪ Ak ,





 {ak c} ∪ Bk ,L4k+z = {ak b, ak c} ∪ Ak ,






 {ak b, ak c} ∪ Bk ,if z = 0,
if z = 1,
if z = 2,
if z = 3.

The remaining languages Ak and Bk will be defined via their characteristic functions fAk
and fBk , respectively. For all k ∈ IN and all strings s ∈ {a, b, c}∗ we set:fAk (s) =fBk (s) =



 1,

if s = bk am and Φk (k) = m, 0,otherwise.



 1,

if s = ck am and Φk (k) = m, 0,otherwise.

After a little reflection, it is easy to see that L is indeed an indexed family.
Claim 1. L ∈ EMON .
We define an IIM which monotonically infers every L ∈ range(L) from any text t for L
with respect to the hypothesis space L itself. So let us assume any L ∈ range(L), any text
t for L and any x ∈ IN.
IIM M: “On input tx do the following: If x = 0 or M has not produced any hypothesis
when successively fed tx−1 , then execute (1). Otherwise, goto (2).
(1) If ak b ∈ t+
x for some k ∈ IN, then output 4k and request the next input.
If ak c ∈ t+
x for some k ∈ IN, then output 4k + 1 and request the next input.
Otherwise, output nothing and request the next input.
(2) Let j = M (tx−1 ). If t+
x ⊆ Lj , then repeat the hypothesis j and request the next
input.
Otherwise, goto (3).
33

(3) If j = 4k or j = 4k + 1, respectively, for some k ∈ IN, then output the hypothesisj + 2 and request the next input.
If j = 4k + 2 for some k ∈ IN, output 4k + 3 and request the next input.
Otherwise, output 4k + 2 and request the next input.”
It remains to show that L ∈ EMON is witnessed by M . Obviously, for every k ∈ IN, M
identifies L4k as well as L4k+1 from every text for the corresponding language. Thereby, M
does not perform any mind change at all. Hence, M is monotonic on every t ∈ text(L4k )∪text(L4k+1 ), k ∈ IN. Let us assume any k ∈ IN such that t is either a text for L4k+2 or
for L4k+3 . In order to show that M satisfies the monotonicity constraint we distinguish thefollowing cases.
Case 1. ϕk (k) ↑Consequently, we obtain L4k+2 = L4k+3 . Since t is a text for the finite language L4k+2 ,there is an x ∈ IN such that t+
x = L4k+2 . Hence, M (tx+r ) = j with Lj = L4k+2 , for all
r ∈ IN+ . Furthermore, M has generated at most one different hypothesis before this point.
Therefore, M is monotonic. Note that M may converge to different hypotheses on different
texts for the same finite language. Consequently, M is not rearrangement-independent.
Case 2. ϕk (k) ↓Since L4k+2 as well as L4k+3 define finite languages, it is easy to see that M converges toa correct hypothesis. We distinguish the following subcases.
Subcase 2.1. t is a text for L4k+2 .
If M first generates the hypothesis 4k, then it needs only one mind change to infer L4k+2 .
Consequently, M is monotonic. Otherwise, 4k + 1 is M ’s first hypothesis. Now, it is easy
to verify that M produces the sequence of hypotheses 4k + 1, 4k + 3 and 4k + 2. Dueto the definition of the family L, L4k+1 ∩ L4k+2 ⊂ L4k+3 directly implies L4k+1 ∩ L4k+2 ⊆L4k+3 ∩ L4k+2 ⊆ L4k+2 . Hence, M is again monotonic.
Subcase 2.2. t is a text for L4k+3 .
Then, a quite similar argumentation yields that M fulfills the monotonicity constraint. If
M outputs the hypothesis 4k + 1 as its first guess, then again, one mind change suffices to34

identify L4k+3 . Otherwise, M produces the sequences of hypotheses 4k, 4k + 2 and 4k + 3.
Due to the definition of the family L, L4k ∩ L4k+3 ⊂ L4k+2 . As before, this directly implies
that M is monotonic.
Therefore, M witnesses L ∈ EMON , and Claim 1 is proved.
Claim 2. L 6∈ r-MON .
Suppose the converse, i.e., there are a class-preserving hypothesis space G = (Gj )j∈IN andan IIM M that witnesses L ∈ r-MON with respect to G.
Claim 3. Given G and any program for M witnessing L ∈ r-MON , one can effectively
construct an algorithm deciding whether or not ϕk (k) converges.
Next, we define the desired algorithm.
Algorithm C: “On input k execute (C1) until (α1) or (α2) is fulfilled, respectively. Afterwards, execute (C2).
(C1) For all x = 0, 1, . . ., execute in parallel (α1) and (α2) until one of them is successful.
(α1) Test whether Φk (k) ≤ x.
(α2) Simulate M when fed the initial segments tx and t̂x of the uniquely definedtexts for L = {ak b} and L̂ = {ak c}, respectively. If M outputs on both
initial segments a hypothesis, say m and m̂, respectively, then test whether
ak b ∈ L(Gm ), ak c ∈/ L(Gm ), ak c ∈ L(Gm̂ ), and ak b 6∈ L(Gm̂ ).
(C2) If (α1) happens first, then output ‘ϕk (k) converges’ and stop.
Otherwise, in parallel execute (β1) or (β2) for y = 1, 2, . . ., until one of them issuccessful.
(β1) Test whether Φk (k) ≤ x + y.
(β2) Test whether M , when fed tx+y = ak b, . . . , ak b, ak c, . . . , ak c, generates a con|

{z

} |

{z

y−times(x+1)−times
sistent hypothesis n, i.e., M (tx+y ) = n and t+⊆
L(Gn ).
x+y

If (β1) happens first, then output ‘ϕk (k) converges’ and stop.
Otherwise, output ‘ϕk (k) diverges’ and stop.”35}

Due to the definition of a complexity measure, (α1) and (β1) can be effectively accomplished. Furthermore, since M is an IIM, and since membership is uniformly decidable for
L(G), (α2) and (β2) can be effectively accomplished, too. Hence, C is indeed an algorithm.
First, we show that C terminates for all k ∈ IN. Let us assume that the execution of (C1)does not terminate for some k ∈ IN. Obviously, then ϕk (k) diverges. Consequently, L4k = L
and L4k+1 = L̂. Now, since (α2) will never terminate successfully, M fails to infer at least
one of the languages {ak b}, {ak c} from its uniquely defined text, a contradiction. Applying
the same argument one can show that the execution of (C2) has to terminate, too. Hence,
C terminates on every input k ∈ IN.
It remains to show that C works correctly. Obviously, if C stops its computation with‘ϕk (k) converges,’ then ϕk (k) is indeed defined. Suppose that C has finished its computation
with ‘ϕk (k) diverges.’ Furthermore, assume that ϕk (k) is defined. Due to our definition, there+
exists an x ∈ IN such that M (tx ) = m and M (t̂x ) = m̂ with t+x ⊆ L(Gm ) as well as t̂x ⊆L(Gm̂ ). Since G is a class-preserving hypothesis space, L(Gm ) = L4k and L(Gm̂ ) = L4k+1 ,respectively, follows immediately (cf. L’s definition). Additionally, there exists a y ∈ IN+
such that M (tx+y ) = n with t+x+y ⊆ L(Gn ). Since M is rearrangement-independent, we+
may conclude that M (t̂x+y ) = n, where t̂x+y = ak c, . . . , ak c, ak b, . . . , ak b, since t+
x+y = t̂x+y .

|

{z

} |

(x+1)−times{zy−times}

Because {ak b, ak c} ⊆ L(Gn ) as well as L(Gn ) ∈ range(L), it suffices to distinguish thefollowing two cases.
Case 1. L(Gn ) = L4k+2
Clearly, t̂x+y is an initial segment of a text for L4k+3 , too. On this text, M has alreadygenerated the hypotheses m̂ and n in some subsequent steps. Since ϕk (k) is defined, by
assumption we obtain L4k+1 ∩ L4k+3 6⊆ L4k+2 ∩ L4k+3 . Therefore, L(Gm̂ ) = L4k+1 andL(Gn ) = L4k+2 directly imply that M violates the monotonicity requirement, a contradiction.
Case 2. L(Gn ) = L4k+3
Using similar arguments, it is easy to see that M violates the monotonicity requirement
when inferring L4k+2 from any of its texts having the initial segment tx+y .
This proves the correctness of Algorithm C. Thus, Claim 3 is shown.
36

On the other hand, the halting problem is undecidable. Therefore, Claim 2 follows, and2

Lemma 5 is proved.

Finally, we consider rearrangement-independence in the context of exact and class-preserving conservative learning. Since conservative learning is exactly as powerful as weakmonotonic one, by the latter Theorem it might be expected that rearrangement-independence
is a severe restriction under the weak-monotonic constraint, too. On the other hand, looking
at Theorem 6 we see that conservative learning has its peculiarities. And indeed, exact andclass-preserving learning can always be performed by 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 14. Let L be an indexed family. Then, L ∈ ECONSERVATIVE if and only ifthere exists a recursively generable family (Tjy )j,y∈IN of finite sets such that(1) for all L ∈ range(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 .
Proof. Necessity. Let L ∈ ECONSERVATIVE . Then there is an IIM M that conservatively learns L with respect to L. The desired tell-tale family (Tjy )j,y∈IN is defined as follows.
Let j, y ∈ IN; then we set

Tjy =




range(tjz ) with z = min{x











x ≤ y, M (tjx ) = j}, if there is an x ≤ ysuch that M (tjx ) = j∅,

otherwise,

where tj denotes the canonical text of Lj . Obviously, the sets Tjy are uniformly recursively
generable and finite. It remains to show that the Properties (1) through (3) are fulfilled.
By construction, (2) is trivially satisfied. In order to prove (1), let L ∈ range(L) and lettL be the canonical text of L. Since M has to infer L from its canonical text, too, there
exists a j such that j = M (tLx ) for almost all x ∈ IN and L = Lj . Let y = µx[M (tLx ) = j].
Then Tjy 6= ∅ and Tjy = Tjy+r for all r ∈ IN. This proves Property (1). Finally, we have37

to show (3). Suppose, there are j, y, z ∈ IN such that ∅ =6 Tjy ⊆ Lz and Lz ⊂ Lj . By thedefinition of the tell-tale sets, there exists an x ≤ y such that M on input tjx outputs j.
Furthermore, Tjy ⊆ Lz and therefore, tjx is an initial segment of a text for Lz , too. Since M
has to infer Lz from every text, it has to perform at least one mind change on every text t ∈text(Lz ) beginning with tjx that cannot be caused by an inconsistency. This contradiction
proves (3).
Sufficiency. The desired IIM is defined as follows. Let L ∈ range(L), t ∈ text(L), andx ∈ IN.
IIM M: “On input tx do the following: If x = 0 or x > 0 and M on input tx−1 does notproduce any hypothesis, then goto (B).
Otherwise, goto (A).
(A) Let j be M ’s last hypothesis on input tx−1 . Test whether or not t+
x ⊆ Lj . In case
it is, output j and request the next input.
Otherwise, goto (B).
(B) Generate Tjy for all j, y = 1, ..., x and test whether or not Tjy 6= ∅. For all nonempty
Tjy check whether or not Tjy ⊆ t+x ⊆ Lj . In case there is one j fulfilling the test,
output the minimal one, and request the next input.
Otherwise, output nothing and request the next input.”
Using the same arguments as in the proof of Theorem 1 in Lange and Zeugmann [10], itis easy to see that M ECONSERVATIVE –learns L. We omit the details.

2

Now we are ready to prove the announced theorem stating that rearrangement-independence does not restrict exact and class-preserving conservative learning.
Theorem 15.
(1) r-ECONSERVATIVE = ECONSERVATIVE ,(2) r-CONSERVATIVE = CONSERVATIVE .

38

Proof. First we prove Assertion (1). Let L ∈ ECONSERVATIVE . By Theorem 14 there
exists a recursively generable family (Tjy )j,y∈IN fulfilling Properties (1) through (3). Using
this family, we define a new recursively generable family (T̂jy )j,y∈IN that satisfies (1), (2), and(3), too. However, the new family allows the design of a rearrangement-independent IIM,
while the IIM described in the proof of Theorem 14 is not rearrangement-independent.
We set T̂jy = ∅, if j ≥ y. Now, let j < y; we defineT̂jy−1 ,







T̂jy =  ∅,





S



y
k≤y−1 Tk ∩ Lj ,ifT̂jy−1 6= ∅,ifT̂jy−1 = ∅, Tjy = ∅,otherwise.

Since (Tjy )j,y∈IN is a recursively generable family and because of the uniform decidabilityof the membership problem for L, the family (T̂jy )j,y∈IN is recursively generable, too. It iseasy to see that (T̂jy )j,y∈IN fulfills Properties (1) through (3) of Theorem 14. We proceed witha technical claim that will be very useful in proving the rearrangement-independence of the
IIM defined below.
Claim 1. Let j, k, m, n ∈ IN such that m = µy[T̂jy 6= ∅] and n = µy[T̂ky 6= ∅]. Then,
T̂kn ∩ Lj ⊆ T̂jm provided n ≤ m.
In accordance with the definition of the family (T̂jy )j,y∈IN we know that m > j as well asn > k. Furthermore, T̂jm =T̂kn ∩ Lj =

S

S

S
m
n
n
z≤m−1 Tz ∩ Lj and T̂k = z≤n−1 Tz ∩ Lk . Hence, we obtain:

S
S
S
n
n
m
m
m
z≤n−1 Tz ∩ Lk ∩ Lj ⊆ z≤n−1 Tz ∩ Lj ⊆ z≤n−1 Tz ∩ Lj ⊆ z≤m−1 Tz ∩ Lj = T̂j .

This proves Claim 1.
Now we define the desired rearrangement-independent IIM as follows. Let L ∈ range(L),t ∈ text(L), and x ∈ IN.
IIM M: “On input tx do the following: Test for all k ≤ x whether or not T̂kx 6= ∅. For all
nonempty T̂kx check whether or not T̂kx ⊆ t+x ⊆ Lk .
In case there is no k fulfilling the test, output nothing and request the next input.
Otherwise, compute yk = µy[T̂ky 6= ∅] for all k fulfilling the test. Output the minimal
k for which yk is minimal, and request the next input.”39

It remains to show that M witnesses L ∈ r-ECONSERVATIVE .

Obviously, M isrearrangement-independent.
Claim 2. M is conservative.
Let j and k, j 6= k, be two hypotheses produced by M on input tx and tx+r , respectively.
We have to show that t+
x+r 6⊆ Lj . In accordance with M ’s definition we directly obtainT̂jx 6= ∅ =6 T̂kx+r . We consider the following cases.
Case 1. T̂kx = ∅.
Then we have t+
x+r 6⊆ Lj . This can be seen as follows. M on input tx+r has to computeyj and yk . Since T̂kx = ∅, we know that yj < yk . Consequently, if t+
x+r ⊆ Lj , then M outputs
j, a contradiction.
Case 2. T̂kx 6= ∅.
Let m = µy[T̂jy 6= ∅] and n = µy[T̂ky 6= ∅]. We distinguish the following subcases.
Subcase 2.1. m < nApplying the same arguments as in Case 1 directly yields t+
x+r 6⊆ Lj .
Subcase 2.2. m = n
Suppose j < k. Again, by the same arguments as in Case 1 one directly obtains t+
x+r 6⊆ Lj .
We proceed with k < j. By Claim 1 we get T̂kn ∩ Lj ⊆ T̂jm . Suppose, t+
x+r ⊆ Lj . Sincennk = M (tx+r ), we immediately obtain that T̂kn ⊆ t+x+r ⊆ Lk . Consequently, T̂k ∩ Lj = T̂k ,and hence T̂kn ⊆ T̂jm ⊆ t+
x , since j = M (tx ). But this implies M (tx ) = k, since j > k, acontradiction.
Subcase 2.3.: m > n
Again, by Claim 1 we know that T̂kn ∩ Lj ⊆ T̂jm . Moreover, by assumption j = M (tx ),n+and therefore ∅ 6= T̂jm ⊆ t+
x . Because of m > n, we furthermore conclude that T̂k 6⊆ tx ,n+since otherwise M (tx ) = k. On the other hand, T̂kn ⊆ t+
x+r , since T̂k 6⊆ tx+r directly implies
n
n
m
n
+
k 6= M (tx+r ). Finally, if t+
x+r ⊆ Lj , then T̂k ∩ Lj = T̂k ⊆ T̂j . But this would imply T̂k ⊆ tx ,again a contradiction.
Hence, M is conservative, and Claim 2 is proved.
40

Claim 3. M infers L.
Let L ∈ range(L) and let t ∈ text(L). Moreover, let K = {kLk = L, T̂ky 6= ∅ foralmost all y ∈ IN}. By Property (1) of the family (T̂jy )j,y∈IN we know that K 6= ∅. Let
k = min K, and let yk = µy[T̂ky 6= ∅]. Since t is a text for L, there exists an x ≥ yk suchthat T̂kyk ⊆ t+x ⊆ Lk = L. Hence, on every input tx+r the IIM M has to output a hypothesis.
We consider the set C of possible hypotheses that might be output by M after having readtx+r , r ≥ 0. Let yj = µy[T̂jy 6= ∅], then C may be written as C = {j
yk ,

y
T̂j j

j ∈ IN, yj ≤⊆ range(t)}. Due to the definition of the family (T̂jy )j,y∈IN the condition T̂jy 6= ∅implies y < j. Therefore, j > yk directly yields yj > yk . Hence, we may rewrite C as
C = {jy

j ≤ yk , yj ≤ yk , T̂j j ⊆ range(t)}. Consequently, C is finite. Finally, applying

Property (3) of Theorem 14 we may conclude Lk 6⊂ Lj for all j ∈ C with j 6= k. Hence, forall j ∈ C with Lj 6= Lk there exists an xj such that t+
xj 6⊆ Lj . Since C is finite, it successively
shrinks to Ĉ = {k} ∪ {` ` ≤ yk , L` = Lk }, and hence M sometimes outputs an element k̂
from Ĉ. Since M is conservative (see Claim 2), M has to repeat k̂ in every subsequent step,and thus it converges.
This proves Assertion (1) of the theorem. Assertion (2) can be proved analogously as
2Lemma 1 in the proof of Theorem 6.

5. Summary
In the present paper we have studied the question whether or not the order of information
presentation does really influence the capabilities of learning algorithms that infer indexedfamilies from positive data. On the one hand, it has been known that set-driveness constitutes
a severe restriction for learning classes of recursively enumerable languages (cf. SchäferRichter [20], and Fulk [5]). On the other hand, the knowledge concerning the learnabilityof indexed families has been much more restricted. Our results provide a thorough analysis
concerning the learning capabilities of set-driven and rearrangement-independent IIMs inthe setting of learning indexed families. In particular, the theorems obtained relate thelearning power of IIMs that satisfy the subset principle to different extends and of IIMs
that simultaneously learn order independently to one another. Moreover, our results provide
41strong evidence that the choice of the relevant hypothesis space is of particular importanceif one is interested in superior learning algorithms. In this regard, the Theorems 6, 8 as
well as Corollary 7 may be considered as a partial answer to the problem of what a naturallearning algorithm should look like. Putting them all together we obtain the following. An
indexed family L can be class-comprisingly inferred in the limit by a set-driven IIM if andonly if there are a hypothesis space G with range(L) ⊆ range(L(G)) and a conservativeand set-driven IIM that learns all languages from L(G). Moreover, since s-CLIM equals
CCONSERVATIVE, the latter result may simplify the design of superior learning algorithms.
In a preliminary version of this paper we left it open to what extend set-drivenessand rearrangement-independence, respectively, influences the capabilities of class-comprisingstrong-monotonic and monotonic learning.

Inspired by our results, Stephan [21] com-pletely solved these questions. In particular, he proved that s-CSMON = CSMON ands-CMON ⊂ r-CMON = CMON .
We continue with the following figure that summarizes our results and the results obtainedby Stephan [21].

FIN

exact

class-preserving

class-comprisinglearning

learning

learning

set+

drivenness
independence

independence

independence

independence

independence

independence

independence

set+

rearrangement–+

independence
set

+

+

drivenness

rearrangement++

drivenness

rearrangement+

rearrangement
LIM+

rearrangement–

rearrangement
WMON

independence

set
drivenness

rearrangement+

rearrangementMON+drivenness

rearrangement
SMON

set

rearrangement+

independence+

For every mode of learning ID mentioned “rearrangement-independence +” indicates r-ID =42

ID as well as s-ID ⊂ ID. “Rearrangement-independence –” implies s-ID ⊂ r-ID ⊂ ID
whereas “set-drivenness +” should be interpreted as s-ID = ID and, therefore, r-ID = ID,too.
Let us continue with an intuitive explanation of the results displayed in the figure above.
As the proof of Theorem 1 shows finite learning can always be achieved by set-driven IIMs
that are allowed to perform unbounded search in the relevant hypothesis space. The unbounded search for the first consistent hypothesis is combined with a test for equality enabling the IIM to decide whether or not it has reached its learning goal. The effectivenessof the equality test is guaranteed by the properties of the relevant family of uniformly recursively generable finite sets that reflect the topological structure of the target indexedfamily.
Looking at strong-monotonic learning the situation considerably changes. As long as
exact and class-preserving learning are concerned unbounded search is no longer an option.
Instead, the actual input length is used to bound the actual set of admissible hypotheses.
However, the relevant family of uniformly recursively generable finite sets is still the main ingredient to solve the subset problem (cf. Theorem 12). As a result, exact and class-preserving
strong-monotonic learning can be always performed by rearrangement-independent IIMs but
in general not by set-driven learning devices. As Stephan [21] showed, class-comprisingstrong-monotonic inference can be generally realized by set-driven IIMs. Again, these learning algorithms perform unbounded search within an appropriate hypothesis space.
As the above figure shows monotonic learning has its peculiarities. Intuitively, the maindifficulty any monotonic IIM has to handle can be described as follows. The demand to its
output is closely related to the whole target language. However, at each learning step the
IIM has only access to the finite subset of the target language that it provided as input.
Furthermore, that the intersection of the hypothesized language and the target language
may yield a language outside the class-preserving hypothesis space has to be taken into
account. Now it becomes evident that every monotonic IIM is in serious trouble wheneverit has no access to its previously performed learning steps. Clearly, the requirement to learn
rearrangement-independently or even set-drivenly complicates any such access. And indeed,43

as the proof of Theorem 13 shows the resulting information loss may lead to the unsolvabilityof the monotonic learning task.
Concerning conservative learning the situation again slightly differs. The main reason
for that phenomenon can be intuitively explained by the replacement of global demands onthe created hypotheses by local ones. If the actual hypothesis is consistent, then the stateof the art already reached during the learning process is expressed with sufficient accuracy.
However, this only true as long as the subset problem can be effectively handled. Hence,
Theorem 8 impressively shows the equivalence of set-drivenness and the recursive solvabilityof the subset problem for the resolution of a learning problem. However, at this point, thechoice of the relevant hypothesis space again becomes important, since the descriptions andenumeration chosen may heavily influence the algorithmic solvability of the subset problem.
Next, we point to further problems that are closely related to the impact of order independence to learning. First, it would be highly desirable to elaborate characteristic conditions
under what circumstances set-drivenness does not restrict the learning power. We expectthat such characterizations might allow much more insight into the problem how to handle
simultaneously both, finite and infinite languages in the learning process. Next, as we haveseen, an algorithmically solvable learning problem might become infeasible, if one tries tosolve 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 are interested in
knowing whether the “high-level” theorem separating set-driven learning from unrestricted
one, has an analogue in terms of complexity theory. For example, it is well conceivable thatan indexed family L may be learned in polynomial time but no set-driven algorithm canefficiently infer L provided P 6= N P. Recently, a similar approach has been successfully
undertaken concerning consistent and inconsistent learning algorithms (cf. Wiehagen and
Zeugmann [25]).
Finally, many researchers considered the learnability of languages from both positive andnegative data (cf., e.g., Gold [6], Lange and Zeugmann [15], Mukouchi [18], Wiehagen and
Zeugmann [25]). In this setting, a learner is successively fed all strings over the underlying

44alphabet which are classified with respect to their containment in the target language. Hence,
it is only natural to ask whether or not order is of the same importance in this model.
Concerning learning in the limit the negative answer has been provided by Blum and Blum[3] for the general case of learning recursively enumerable languages. However, the equality of
set-driven learning in the limit and unrestricted identification in the limit for indexed families
goes back to Gold [6]. We refer the reader to Zeugmann and Lange [27] for a more detailed
discussion. Moreover, these results extend to all the models of monotonic language learningfrom positive and negative data. In particular, by characterizing all types of monotonic
language learning from positive and negative data in terms of uniformly recursively generable
families of positive and negative finite sets Lange and Zeugmann [15] showed the following.
There is exactly one learning algorithm that can perform every learning task under the
relevant monotonicity constraint. As a matter of fact, this algorithm is set-driven, too.

Acknowledgement
Most of this work has been done while the first author was visiting ISIS FUJITSU Labs.
at Numazu, Japan. He is greatfully indebted to Y. Takada and Y. Sakakibara for providing
inspiring working conditions.
Furthermore, the first author has been partially supported by the German Ministry for
Research and Technology (BMFT) under grant no. 01 IW 101.
Finally, we heartily thank the anonymous referees for their careful reading and for many
valuable comments on the preparation of this paper.

6. References[1] D. Angluin, Finding patterns common to a set of strings, Journal of Computer and
System Sciences 21 (1980), 46 – 62.
[2] D. Angluin, Inductive inference of formal languages from positive data, Information
and Control 45 (1980), 117 – 135.
[3] L. Blum and M. Blum, Toward a mathematical theory of inductive inference, Information and Control 28 (1975), 122 – 155.

45

[4] R. Berwick, The Acquisition of Syntactic Knowledge, MIT Press, Cambridge, Mass.,
1985.
[5] M. Fulk, Prudence and other restrictions in formal language learning, Information andComputation 85 (1990), 1 – 11.
[6] E.M. Gold, Language identification in the limit, Information and Control 10 (1967),
447 – 474.
[7] J.E. Hopcroft and J.D. Ullman, Formal Languages and their Relation to Automata,Addison-Wesley, Reading, Mass., 1969.
[8] K.P. Jantke, Monotonic and non-monotonic inductive inference, New Generation Computing 8 (1991), 349 – 360.
[9] S. Lange and R. Wiehagen, Polynomial-time inference of arbitrary pattern languages,
New Generation Computing 8 (1991), 361 – 370.
[10] S. Lange and T. Zeugmann, Types of monotonic language learning and their characterization, Proc. 5th Annual ACM Workshop on Computational Learning Theory, ACM
Press, New York, 1992, pp. 377 – 390.
[11] S. Lange and T. Zeugmann, Monotonic versus non-monotonic language learning, Proc.
2nd International Workshop on Nonmonotonic and Inductive Logic (G. Brewka, K.P.
Jantke and P.H. Schmitt, Eds.), Springer-Verlag, Berlin, 1993, Lecture Notes in Artificial Intelligence 659, pp. 254 – 269.
[12] S. Lange and T. Zeugmann, Language learning in dependence on the space of hypotheses, Proc. 6th Annual ACM Conference on Computational Learning Theory, ACM
Press, New York, 1993, pp. 127 – 136.
[13] S. Lange and T. Zeugmann, The learnability of recursive languages in dependence on
the hypothesis space, HTWK Leipzig, FB Mathematik, Informatik und Naturwissenschaften, GOSLER–Report 20/93, 1993.
[14] S. Lange and T. Zeugmann, Learning recursive languages with bounded mind changes,
International Journal of Foundations of Computer Science 4 (1993), 157 – 178.

46

[15] S. Lange and T. Zeugmann, Characterization of language learning from informant
under various monotonicity constraints, Journal of Experimental and Theoretical Artificial Intelligence 6 (1994), 71 – 94.
[16] S. Lange, T. Zeugmann and S. Kapur, Monotonic and dual-monotonic language learning, Theoretical Computer Science 155 (1996), 365 – 410.
[17] M. Machtey and P. Young, An Introduction to the General Theory of Algorithms,
North-Holland, New York, 1978.
[18] Y. Mukouchi, Inductive inference with bounded mind changes, Proc. 3rd Workshop on
Algorithmic Learning Theory (S. Doshita, K. Furukawa, K.P. Jantke and T. Nishida,Eds.), Springer-Verlag, Berlin, 1993, Lecture Notes in Artificial Intelligence 743, pp.
125 – 134.
[19] D. Osherson, M. Stob and S. Weinstein, Systems that Learn: An Introduction to Learning Theory for Cognitive and Computer Scientists, MIT Press, Cambridge, Mass., 1986.
[20] G. Schäfer-Richter, Über Eingabeabhängigkeit und Komplexität von Inferenzstrategien, Rheinisch Westfälische Technische Hochschule Aachen, Dissertation, 1984.
[21] F. Stephan, Personal communication[22] K. Wexler, The subset principle is an intensional principle, In Knowledge and Language:
Issues in Representation and Acquisition (E. Reuland and W. Abraham, Eds.), Vol. 1,
From Orwell’s Problem to Plato’s Problem, Chapter 9, Kluwer Academic Publishers,
1993.
[23] K. Wexler and P. Culicover, Formal Principles of Language Acquisition, MIT Press,
Cambridge, Mass., 1980.
[24] R. Wiehagen, A thesis in inductive inference, Proc. First International Workshop on
Nonmonotonic and Inductive Logic (J. Dix, K.P. Jantke and P.H. Schmitt, Eds.),
Springer-Verlag, Berlin, 1991, Lecture Notes in Artificial Intelligence 543, pp. 184 –
207.
[25] R. Wiehagen and T. Zeugmann, Ignoring data may be the only way to learn efficiently,
Journal of Experimental and Theoretical Artificial Intelligence 6 (1994), 131 – 144.

47

[26] T. Zeugmann, Lange and Wiehagen’s pattern language learning algorithm: An averagecase analysis with respect to its total learning time, RIFIS Technical Report RIFISTR-CS-111, RIFIS, Kyushu University 33, 1995.
[27] T. Zeugmann and S. Lange, A guided tour across the boundaries of learning recursive languages, Algorithmic Learning for Knowledge-Based Systems (K.P. Jantke and
S. Lange, Eds.), Springer-Verlag, Berlin, 1995, Lecture Notes in Artificial Intelligence961, pp. 190 – 258.

48