On the Impact of Order Independence to the Learnability of
Recursive Languages
Ste en LangeHTWK Leipzig
FB Mathematik und Informatik
PF 66
04275 Leipzig
ste en@informatik.th-leipzig.de

Thomas Zeugmann

TH Darmstadt
Institut fur Theoretische Informatik
Alexanderstr. 1064283 Darmstadt
zeugmann@iti.informatik.th-darmstadt.de

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

Abstract
The present paper deals with the learnability of indexed families of uniformly recursive languages from positive data under various postulates of naturalness. 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 theirlearning power is studied in dependence on the hypothesis space the learners may use. Furthermore, we consider the in uence of set-drivenness and rearrangement-independence for learning
devices that realize the subset principle to di erent extents. Thereby we distinguish between
strong-monotonic, monotonic and weak-monotonic or conservative learning.
The results obtained are twofold. First, rearrangement-independent learning does not constitute a restriction except the case of monotonic learning. Second, we prove that for all but
one of the considered learning models set-drivenness is a severe restriction. However, set-driven
conservative learning is exactly as powerful as unrestricted conservative learning provided the
hypothesis space is appropriately chosen. These results considerably extend previous work donein the eld (cf. e.g. Schafer (1984) and Fulk (1990)).

1. Introduction
Language acquisition is one of the main topics in cognitive science, epistemology, linguistic andpsycholinguistic 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 ction.
Formal language learning may be characterized as the study of systems that map evidence on alanguage into hypotheses about it. Of special interest is the investigation of scenarios in which theMost of this work has been done while the author was visiting ISIS FUJITSU Labs. at Numazu, Japan. It has
been partially supported by the German Ministry for Research and Technology (BMFT) under grant no. 01 IW 101.
1

sequence of hypotheses stabilizes to an accurate and nite description (a grammar) of the target
language. Clearly, then some form of learning must have taken place. In his pioneering paper, Gold
(1967) gave precise de nitions 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 (1986)
and the references therein). Most of the work done in the eld has been aimed at two goals: thecharacterization of those collections of languages that can be learned, and to study the impact ofseveral postulates on the behavior of learners to their learning power.
In this paper we aim to investigate the learning capabilities of learners that ful ll simultaneously
various combinations of desirable properties. For the purpose of motivation and discussion of ourresearch next to we introduce some notations.
A text of a language L is an in nite sequence of strings that eventually contains all strings of L.
An algorithmic learner, henceforth called inductive inference machine (abbr. IIM), takes as input
initial segments of a text, and outputs, from time to time, a hypothesis about the target language.
The set G of all admissible hypothesis is called hypothesis space. Furthermore, the sequence of
hypotheses has to converge to a hypothesis correctly describing the language to be learned, i.e.,
after some point, the IIM stabilizes to an accurate hypothesis. If there is an IIM that learns alanguage L from all texts for it, then L is said to be learnable in the limit with respect to the
hypothesis space G .
A rst question directly arising when dealing with learning in the limit is whether or not theorder of information presentation does really in uence the capabilities of IIMs. An IIM is said
to be set-driven, if its output does only depend on the range of its input. Surprisingly enough,Schafer (1984) and Fulk (1990) proved that set-driven IIMs are less powerful than unrestricted
ones. Intuitively, the weakness of set-driven IIMs is caused by the diculties to handle both, nite
and in nite languages. A natural weakening of set-drivenness is rearrangement-independence. An
IIM is called rearrangement-independent if its output does only depend on the range and lengthof 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. Schafer (1984), Fulk (1990)). However,
the weakness of set-driven IIMs has been proved in a setting allowing self-referential arguments.
This might lead to the impression that this result is far beyond any practical relevance, sinceself-referential arguments are exclusively applicable in settings where the membership problem for
languages is undecidable in general.
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 of non-empty and uniformly
recursive languages. A famous example for an indexed family is the collection of all pattern languages (cf. Angluin (1980a)). Although this indexed families contains nite and in nite languages,
Lange and Wiehagen (1991) succeeded in designing a set-driven IIM learning it. Consequently, it
is only natural to ask whether or not any learnable indexed family may be learned by a set-driven
IIM, too.
A major problem, one has to deal with when learning from text, is to avoid or to detect overgeneralization (also called the subset problem), i.e., hypotheses that describe proper supersets ofthe target language. The impact of this problem results simply from the fact that a text cannot
supply counterexamples to such hypotheses. IIMs that strictly avoid overgeneralized hypotheses
are called conservative (cf. De nition 6). As it turns out, neither Schafer's (1984) nor Fulk's (1990)
transformation of an arbitrary IIM into a rearrangement-independent one preserves conservative2

ness. 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 in uence the learnability of indexed families (cf. Lange and Zeugmann (1993b)). Hence, we have to
distinguish between exact learning, class preserving inference, and class comprising learning. If an
indexed family L can be 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 ahypothesis space G = (Gj )j 2IN such that any Gj describes a language from L and M learns L withrespect to G . That means, if one learns class preservingly, then one has the freedom to change theenumeration as well as the description of the languages from L. Finally, if any hypothesis space
G = (Gj )j2IN comprising the range of L may be taken by the learning algorithm, then we call itclass comprising. In this setting one has to freedom to change the enumeration, the description andto add elements Gk not describing any language >from L to the hypothesis space. However, sincemembership in L is uniformly decidable, we restrict ourselves to consider exclusively hypothesis
spaces having a uniformly decidable membership problem.
Several authors proposed the so-called subset principle to solve the problem of avoiding overgeneralization (cf. e.g. Berwick (1985), Wexler (1992)). Informally, the subset principle requires thelearner to hypothesize the \least" language from the hypothesis space with respect to set inclusionthat ts with the data the IIM has read so far. Therefore, we present some formalizations of learning
realizing the subset principle to di erent extents. First, we require the learning algorithm to produce a sequence of hypotheses describing an augmenting chain of languages, i.e., L(Gj )  L(Gk ), if
k is hypothesized on an extension of the text segment that led to j (cf. De nition 5, (A)). We calllearners 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 learners are allowed to output any hypothesis (cf. De nition 5,(C)). Third, we re ne strong-monotonic 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 modelis called monotonic inference (cf. De nition 5, (B)). Strong-monotonic and weak-monotonic learning has been introduced by Jantke (1991) and monotonic learning goes back to Wiehagen (1991).
Subsequently, we have studied their learning capabilities in the setting of learning indexed families(cf. Lange and Zeugmann (1993a)). Again, the power of all the monotonic learning models heavily
depends on the choice of the hypothesis space (cf. Lange and Zeugmann (1993b).
In the sequel we study the impact of set-drivenness and rearrangement-independence on all thelearning models described above in dependence on the hypothesis space. The results obtained provethat 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 characterizationsof all types of monotonic learning in terms of nite tell-tales. Moreover, we show that set-drivenness
cannot be achieved in general. However, class comprising weak-monotonic learning is exactly as
powerful than class comprising set-driven weak-monotonic inference. We regard this result as aparticular answer to the question how a \natural" learning algorithm may be designed.

2. Preliminaries
By IN = f0; 1; 2; :::g we denote the set of all natural numbers. We set IN+ = IN n f0g. Let
3

'0 ; '1 ; '2 ; ::: denote any xed programming system of all (and only all) partial recursive functions
over IN, and let 0 ; 1 ; 2 ; ::: be any associated complexity measure (cf. Machtey and Young, 1978).
Then 'k is the partial recursive function computed by program k in the programming system.
Furthermore, let k; x 2 IN. If 'k (x) is de ned (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. Moreover, we use h:; :; :i : IN  IN 
IN ! IN to denote the following encoding: hx; y; z i =df hx; hy; z ii for all x; y; z 2 IN.

In the sequel we assume familiarity with formal language theory (cf. Hopcroft and Ullman(1969)). By  we denote any xed nite alphabet of symbols. Let  be the free monoid over. Any subset L   is called a language. By co L we denote the complement of L. Let L
be a language and t = s0 ; s1 ; s2 ; ::: an in nite sequence of strings from  such that range(t) =fsk k 2 INg = L. Then t is said to be a text for L or, synonymously, a positive presentation. Let
L be a language. By text(L) we denote the 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, andt+x =df fsk k  xg.
Next, we introduce the notion of canonical text that turned out to be very helpful in proving
several theorems. Let L be any non-empty recursive language, and let s0 ; s1 ; s2 ; ::: be the lexicographically ordered text of  . The canonical text of L is obtained as follows. Test sequentiallywhether sz 2 L for z = 0; 1; 2; ::: until the rst z is found such that sz 2 L. Since L 6= ; there mustbe at least one z ful lling the test. Set t0 = sz . We proceed inductively. For all x 2 IN we de ne:8< tx; sz+x+1; if sz+x+1 2 L;
tx+1 = :tx ; s;otherwise; where s is the last string in tx :In the sequel we deal with the learnability of indexed families of uniformly recursive languagesde ned as follows (cf. Angluin, 1980b). A sequence L0 ; L1 ; L2 ; ::: is said to be an indexed family Lof uniformly recursive languages provided all Lj are non-empty and there is a recursive function fsuch that for all numbers j and all strings s 2  we havef (j; s) =(1; if s 2 Lj ;0; otherwise:

In all what follows we refer to indexed families of uniformly recursive languages as indexedfamilies for short. Moreover, we often denote an indexed family and its range by the same symbol
L. The meaning will be clear from the context.
As in Gold (1967) we de ne an inductive inference machine (abbr. IIM) to be an algorithmic
device which works as follows: The IIM takes as its input larger and larger initial segments of atext t and it either requests the next input string, or it rst 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 wehave to clarify what hypothesis spaces we choose. We require the inductive inference machines to
output indices of grammars, since this learning goal ts well with the intuitive idea of language
learning. Furthermore, since we exclusively deal with indexed families L = (Lj )j 2IN we always takeas space of hypotheses an enumerable family of grammars G0 ; G1 ; G2 ; ::: over the terminal alphabet4 satisfying L  fL(Gj ) j 2 INg. Moreover, we require that membership in L(Gj ) is uniformly
decidable for all j 2 IN and all strings s 2  . The numbers j that the IIM outputs are theninterpreted as L(Gj ). Moreover, for notational convenience we use L(G ) to denote fL(Gj ) j 2 INg
for every hypothesis space G = (Gj )j 2IN.
A sequence (jx )x2IN of numbers is said to be convergent in the limit i there is a number j suchthat jx = j for almost all numbers x. Now we de ne some concepts of learning. We start withlearning in the limit.
De nition 1. (Gold, 1967) Let L be an indexed family of languages, L 2 L; and let G =(Gj )j 2IN be a space of hypotheses. An IIM M LIM {identi es L from a text t with respect to G
i it almost always outputs a hypothesis and the sequence (M (tx ))x2IN converges in the limit to anumber j such that L = L(Gj ).
Furthermore, M LIM {identi es L i M LIM {identi es L from every text t 2 text(L). We
set:
LIM (M ) = fL 2 L M LIM {identi es Lg.
Finally, let LIM denote the collection of all indexed families L for which there is an IIM M
such that L  LIM (M ).
Suppose, an IIM identi es some language L. That means, after having seen only nitely many
data of L the IIM reached its (unknown) point of convergence and it computed a correct and nite
description of a generator for the target language. Hence, some form of learning must have takenplace. Therefore, we use the terms infer and learn as synonyms for identify.
Moreover, an IIM is required to learn the target language from every text for it. This mightlead 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 really behaving thus are called
set-driven. More precisely, we de ne:
De nition 2. (Wexler and Culicover, Sec. 2.2, (1980)) An IIM is said to be set-driven
i its output depends only on the range of its input; that is, i M (tx ) = M (t^y ) for all x; y 2 IN, alltexts t; t^ provided t+x = t^+y .
Schafer (1984) as well as Fulk (1990), later, and independently proved that set-driven IIMs areless powerful than unrestricted ones. Fulk (1990) interpreted the weakening in the learning powerof set-driven IIMs by the need of IIMs for time to \re ect" on the input. However, this time cannot
be bounded by any a priorily xed computable function depending exclusively on the size of therange of the input, since otherwise set-drivenness would not restrict the learning power. Indeed,
Osherson, Stob and Weinstein (1986) proved that any non-recursive IIM M may be replaced by anon-recursive set-driven IIM M^ learning at least as much as M does. With the next de nition we
consider a natural weakening of De nition 2.
De nition 3. Schafer-Richter (1984), Osherson et al. (1986)) An IIM is said to berearrangement-independent i its output depends only on the range and on the length of its input;that is, i M (tx ) = M (t^x ) for all x 2 IN, all texts t; t^ provided t+x = t^+x .
We make the following convention. For all the learning models in this paper we use the pre xs-, and r- to denote the learning model restricted to set-driven and rearrangement-independent
IIMs, respectively. For example, s LIM denotes the collection of all indexed families that are
LIM {inferable by some set-driven IIM. Next we formalize the other inference models that we havementioned in the introduction.
5

De nition 4. (Gold, 1967) Let L be an indexed family of languages, L 2 L and let G =(Gj )j 2IN be a space of hypotheses. An IIM M FIN {identi es L from text t with respect to G i it

outputs only a single and correct hypothesis j , i.e., L = L(Gj ), and stops.
Furthermore, M FIN {identi es L, i M FIN {identi es L from every t 2 text(L). We set:
FIN (M ) = fL 2 L M FIN {identi es Lg and de ne the resulting learning type FIN to be thecollection of all nitely inferable indexed families.
Consequently, every hypothesis produced by a nitely working IIM has to be a correct guess.
The next de nition formalizes the di erent notions of monotonicity.
De nition 5. (Jantke (1991), Wiehagen (1991)) Let L be an indexed family of languages,
L 2 L and let G = (Gj )j 2IN be a space of hypotheses. An IIM M is said to identify a language Lfrom text(A) strong-monotonically(B) monotonically(C) weak-monotonicallyi

M LIM {identi es L and for any text t 2 text(L) as well as for any two consecutive hypotheses jx ,jx+k which M has produced when fed tx and tx+k for some k  1; k 2 N , the following conditions

are satis ed:(A) L(Gj )  L(Gj + )(B) L(Gj ) \ L  L(Gj + ) \ L(C) if tx+k  L(Gj ) then L(Gj )  L(Gj + ).
x

x k

x

x k

x

x

x k

By SMON; MON , and WMON , we denote the family of all sets L of indexed families forwhich there is an IIM inferring it strong-monotonically, monotonically, and weak-monotonically,
respectively.
De nition 6. (Angluin, 1980b) Let L be an indexed family, L 2 L, and let G = (Gj )j2IN bea space of hypotheses. An IIM M CONSERVATIVE{identi es L from text with respect to G i forevery text t the following conditions are satis ed:(1) L 2 LIM (M ) w.r.t. G ,(2) 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(Gj ).
x

CONSERVATIVE(M ) as well as the collections of sets CONSERVATIVE are de ned in an
analogous manner as above. Note that WMON = CONSERVATIVE (cf. Lange and Zeugmann(1993a)). Additionally, every conservatively working IIM satis es the monotonicity constraints aweak-monotonically working IIM has to ful ll.
We conclude this subsection with the following convention. For any model of inference de ned
above, the pre x E denotes the requirement to learn an indexed family L with respect to the6hypothesis space L (exact learning). Furthermore, class comprising inference is denoted by the
pre x C , e.g. CLIM denotes the set of all indexed families L inferable with respect to somehypothesis space G = (Gj )j 2IN such that L  fL(Gj ) j 2 INg. If no pre x is used, then classpreserving learning is meant, i.e., inference with respect to a hypothesis space G = (Gj )j 2IN suchthat range(L) = fL(Gj ) j 2 INg. For example, r MON denotes the collection of all indexedfamilies L that may be monotonically identi ed by a rearrangement-independent IIM with respect
to some class preserving hypothesis space.

3. Learning with Set-driven IIMs.
Theorem 1. EFIN = FIN = CFIN = s EFIN

Proof. EFIN = FIN = CFIN is due to Lange and Zeugmann (1993b). It remains to showthat EFIN  s EFIN .
Let L 2 EFIN . From the characterization theorem for nite learning (cf. Lange and Zeugmann,
1992) it follows that there exists a recursively generable family (Tj )j 2IN of nite non-empty setssuch that(1) For all j 2 IN, Tj  Lj ,(2) For all j; k 2 IN, if Tj  Lk , then Lk = Lj .
Using this recursively generable family (Tj )j 2IN we de ne a IIM M witnessing L 2 s EFIN . Let
L 2 L, t 2 text(L), and x 2 IN.

M (tx ) = \ If x = 0 or M when fed successively with 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  t+x .
In case it is, output j and stop.

Otherwise, request the next input and output nothing."
It remains to show that L  s EFIN (M ). By construction, M uses L as hypothesis space.
Claim 1. M nitely infers L.
Let t 2 text(L). It remains to show that M stops sometimes, say with j , and that L = Lj . Let
k be the least number satisfying L = Lk . By property (1), Tk  Lk . Since t+ = L, there must
be an x such that Tk  t+x . Now, there is only one case imaginable that could prevent M to stop.
Namely, it exists a j < k with L  Lj and Tj 6 L. Clearly, in this case M would verify t+y  Lj
but it never veri es Tj  t+y . 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 outputs j and stops. But then, in accordance with M 's de nition, M has veri ed
t+y  Lj and Tj  t+y . Hence, Tj  Lk . By property (2), we directly obtain Lj = Lk = L. This
proves the claim.
Claim 2. M is set-driven.
Let tx and t^y be two initial text segments of a language L 2 L such that t+x = t^+y . We have toshow that M (tx ) = M (t^y ). Suppose, M executes stage x or y, respectively. Since L 2 L, there
exists a least number k such that L = Lk . Hence, M nds indices i; j such that t+x  Li and7t^+y  Lj . Because of t+x = t^+y , we may conclude i = j . Since the tell-tale sets Tj are uniformly
recursively generable, M can e ectively 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 ahypothesis, say j . We have to show that M (t^y ) = j . Since M nitely infers L, we know that
Lj = L. Moreover, M has veri ed that Tj  t+z  Lj for some z < x. By assumption, t+x = t^+y ,and therefore t+z  t^+y . We distinguish the following two cases.
Case 1. M when successively fed t^y 1 does not stop.
Since j is the least index with t+z  Lj and since Lj = L, we conclude that j is the smallest
number such that t^+y  Lj . Hence, Tj  t+z  t^+y , and M outputs j .
Case 2. M when successively fed t^y 1 stops.
Suppose M (t^m ) = k for some m < y. As above, then Lk = L. However, as we already seen in
the proof of Claim 1, M always outputs the least index of the language it actually learns. Hence,
we obtain k = j . This proves the claim.

q.e.d.
As we have already mentioned, the examples of Schafer (1984) and Fulk (1990) 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 (1993b). It remains
to show that s CLIM  ELIM .
The desired indexed family L is de ned as follows. For all k 2 IN we set Lhk;0i = fak bn n 2 IN+ g.
For all k 2 IN and all j 2 IN+ we distinguish the following cases:

Case 1. : k (k)  j
Then we set Lhk;j i = Lhk;0i .

Case 2. k (k)  j
Let d = 2  k (k) j . Now, we set:
( km
fa b 1  m  dg; if d  1;
Lhk;j i =fak bg;otherwise:L = (Lhk;ji)j;k2IN is an indexed family of recursive languages, since the predicate \i (y)  z" isuniformly decidable in i; y; and z .
Claim A. L 62 s CLIM
Since the halting problem is undecidable, Claim A follows by contraposition of the following
Claim B.
Claim B. If there exists an IIM M with L  s CLIM (M ), then one can e ectively construct
an algorithm deciding for all k 2 IN whether or not 'k (k) converges.
8Let M be any IIM that learns L in the limit w.r.t. some hypothesis space G comprising L. We
de ne 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 lexicographically ordered text t of Lhk;0i until
M on input tz outputs for the rst time a hypothesis j such that t+z [fak bz+1 g  L(Gj ).
(A2) Test whether k (k)  z . In case it is, output \'k (k) converges."
Otherwise output \'k (k) diverges."

Since M has to infer Lhk;0i in particular from t, there has to be a least z such that M on
input tz computes a hypothesis j satisfying t+z [ fak bz+1 g  L(Gj ). Moreover, the test whether or
not t+z [ fak bz+1 g  L(Gj ) can be e ectively performed, since membership in L(Gj ) is uniformly
decidable. By the de nition of a complexity measure, instruction (A2) is e ectively executable.
Hence, A is an algorithm.
It remains to show that 'k (k) diverges, if : k (k)  z . Suppose the converse; then there exists
a y > z with k (k) = y. In accordance with the de nition of L, we obtain L = t+z 2 L. Hence, tz
is also an initial segment of a text t^ for L. Due to the de nition of A, we have L(Gj ) 6= L. Since
M is a set-driven IIM, L = t+z implies M (t^x+r ) = j for all r 2 IN. Therefore, M fails to infer L on
its text t^. This contradicts our assumption that L  s CLIM (M ). Hence, Claim B is proved.
Claim C. L 2 ELIM
After a bit of re ection, it is easy to verify that the following IIM M infers L w.r.t. the hypothesis
space L. Let L 2 L, let t 2 text(L), and let x 2 IN. We de ne:

M (tx ) = \Determine the unique k such that t0 = ak bm for some m 2 IN. Test whether or notk (k)  x. In case it is, goto (A). Otherwise, output hk; 0i and request the next input.
(A) Test whether or not ak b (k)+n 2 t+x for some n 2 IN. In case it is, output hk; 0i andkrequest the next input. Otherwise, goto (B).
(B) Determine the maximal z 2 IN such that ak bz 2 t+x . Output hk; 2  k (k) z i and request
the next input."
q.e.d.
As the latter theorem shows, sometimes there is no way to design a set-driven IIM. However,with the following theorems we mainly intend to show that the careful choice of the hypothesis
space deserves special attention whenever set-drivenness is desired.
Theorem 3. There is an indexed family L such that
(1) L 2 r ESMON ,(2) L 6 LIM (M ) for all IIM M , provided M is set-driven,(3) there is an IIM M such that L  s CSMON (M ).
Proof. The desired indexed family L = (Lhk;j i)k;j 2N is de ned as follows. For all k 2 N we set
Lhk;0i = fak bm j m 2 N +g. For all j 2 IN+ we distinguish the following cases.

9Case 1. : k (k)  j
Then we de ne Lhk;j i = Lhk;0i .
Case 2. k1 (k1 )  j
Then we set Lhk;j i = fak bg.
Claim 1. L 2 r ESMON .
We have to de ne an IIM witnessing L 2 ESMON . This is done as follows: Let L 2 L, t 2text(L), and x 2 IN.

M (tx ) = \Compute the unique k such that ak bm 2 t+x for some m 2 N . As long as t+x = fak bg
execute (A).
Otherwise, output hk; 0i and request the next input.
(A) Test whether : k (k)  x. In case it is, output nothing and request the next input.
Otherwise, output hk; k (k)i and request the next input."

Obviously, M is rearrangement-independent. In order to prove L  r ESMON (M ) we distinguish
the following cases.
Case 1. 'k (k) "In accordance with the de nition of the indexed family L we directly obtain L = Lhk;0i = Lhk;j i
for all j 2 N . Since t 2 text(L), there has to be an x such that t+x 6= fak bg. Consequently, after
having seen tx the IIM M always outputs hk; 0i, a correct hypothesis. Moreover, M obviously
works strong-monotonically.
Case 2. 'k (k) #Suppose, L = fak bg. Since t 2 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 seen tx0 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 2 IN such thatt+x 6= fak bg. 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 of t and changes its mind
to hk; 0i afterwards. Clearly, this mind change ful lls the strong-monotonicity constraint. Hence,L  r ESMON (M ).
Claim 2. L 6 LIM (M ) for all IIM M , provided M is set-driven.
This claim is proved via the following lemma.
Lemma 1. Let M be any set-driven IIM such that L  LIM (M ) w.r.t. some class preserving
hypothesis space G = (Gj )j 2IN . Then M may be used to decide the halting problem.
Proof. We de ne an algorithm A as follows.
Algorithm A: \On input k execute instruction (A1).
(A1) 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 (A2).
10(A2) Test whether or not ak b2 2 L(Gz ).
In case it is, output \'k (k) "."Else, output \'k (k) #," and stop."
Obviously, A is an algorithm. It remains to show that A behaves correctly. Suppose, A outputs\'k (k) "" but \'k (k) #." By de nition of L, L = fak bg 2 L. Since M is supposed to be set-driven,
it has to output a correct hypothesis after having seen ak b. But it does not, since A has terminatedwith \'k (k) "." This contradiction directly yields that A behaves correctly if it outputs \'k (k) "".
Now, let us assume A terminates with \'k (k) #." Taking into account that G = (Gj )j 2IN is aclass preserving hypothesis space, we directly see that ak b2 62 L(Gz ) implies L(Gz ) = fak bg. Hence,\'k (k) #." This proves the lemma.
Since the halting problem is not recursive, the contraposition of Lemma 1 implies Claim 2.
Claim 3. L 2 s CSMON .
First of all we de ne the desired class comprising hypothesis space. For all k 2 IN we set

8< Lhk;0i; if j = 2k;
L(Gj ) = : kfa bg; if j = 2k + 1:

Obviously, G = (Gj )j 2IN is an admissable hypothesis space. A set-driven IIM M witnessing L 2
CSMON may be easily de ned as follows. As long as it receives an initial segment tx of a text t
such that t+x = fak bg it outputs 2k + 1. If fak bg  t+x , it hypothesizes 2k. We omit the details.
q.e.d.
Theorem 3 directly yields the following corollary which relates the power of set-driven andunrestricted IIMs to one another.
Corollary 4. For all ID 2 fSMON; MON; WMON g:(1) s EID  EID(2) s ID  ID
Proof. This corrollary follows immediately from Theorem 3. There, we have shown r ESMON ns LIM 6= ;. This yields all the proper inclusions mentioned, since ESMON  SMON ,ESMON  EID  ID for all ID 2 fMON; WMON g (cf. Lange and Zeugmann (1993b)) as
well as s EID  s ID  s LIM for all ID 2 fSMON; MON; WMON g by de nition.

q.e.d.
As we have seen, set-drivenness constitutes a severe restriction. While this is true in general as
long as exact and class preserving learning is considered, the situation looks di erently in the classcomprising case. On the one hand, learning in the limit cannot always be achieved 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 5. 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 1) below. Then we apply thisresult and show that set-drivenness does not restrict the power of class comprising conservative
learning (cf. Lemma 2).
11

Lemma 1. r{CCONSERVATIVE = CCONSERVATIVE
Let L 2 CCONSERVATIVE . By Theorem 14 in Lange and Zeugmann (1993c) there exists
a hypothesis space G = (Gj )j 2IN and a recursively generable tell-tale family (Tj )j 2IN of nite andnon-empty sets such that(1) range(L)  L(G ),(2) for all j 2 N , Tj  L(Gj ),(3) for all j; k 2 IN, if Tj  L(Gk ), then L(Gk ) 6 L(Gj ).
Using this tell-tale family, we de ne a new recursively generable family (T^j )j 2IN of nite and nonempty sets that allows the design ofSa rearrangement-independent IIM inferring L conservatively
w.r.t. G . For all j 2 IN we set T^j = nj Tn \ L(Gj ).
It is easy to see that (T^j )j 2IN ful lls (1) through (3), too. Next, we even show the following
stronger result.
Statement 1. L(G ) 2 ECONSERVATIVE.
The desired IIM is de ned as follows. Let L 2 L(G ), t 2 text (L), and x 2 N .
M (tx ) = \Generate T^k for all k  x and test whether T^k  t+x  L(Gk ). In case there is one k
ful lling the test, output the minimal one, and request the next input.
Otherwise, output nothing and request the next input."
Obviously, M is rearrangement-independent.
Claim 1. M works conservatively.
Let k and j be two hypotheses produced by M on input tx and tx+r , respectively. We have toshow that t+x+r 6 L(Gk ). For that purpose we distinguish the following cases.
Case 1. k < j
Due to M 's de nition we immediately obtain t+x+r 6 L(Gk ).
Case 2. j < kSuppose, t+x+r  L(Gk ). In accordance with its de nition, M has veri ed that T^j  t+x+r L(Gj ). Moreover, the de nition of the tell-tale family directly yields T^j  T^k , since j < k andT^j  t+x+r  L(Gk ). Taking into account that T^k  t+x , this implies T^j  t+x  L(Gj ). Finally, since
j < k we conclude M (tx ) = j , a contradiction. Hence, the claim is proved.
Claim 2. M infers L from t.
Let z = k [L(Gk ) = L]. Therefore, L(Gj ) 6= L for all j  z . Applying property (3), we obtainthat L n L(Gj ) 6= ; for all j < z provided T^j  L. Consequently, every candidate hypothesis j < z
is sometimes rejected by M , and M converges to z . Hence, the claim follows and Statement 1 isproved.
Finally, since L  L(G ), we may easily conclude that L  r CCONSERVATIVE (M ). This
proves Lemma 1.
Lemma 2. Let L be any indexed family. If L 2 CCONSERVATIVE , then there exists a
hypothesis space G~ = (G~ j )j 2IN and an IIM M~ such that L  s CCONSERVATIVE (M~ ) w.r.t. G~.
12

First, we de ne the hypothesis space G~ = (G~ j )j 2IN as follows. Applying Lemma 1, there exists
a hypothesis space G = (Gj )j 2IN and and IIM such that L  r CCONSERVATIVE (M ) w.r.t. G
as well as L(G )  r ECONSERVATIVE (M ). Afterwards, we use the latter statement and show
a more general result which turns out to be quite helpful in order to prove Corollary 6. The
hypothesis space G~ is the canonical enumeration of all grammars from G and all nite languages
over the underlying alphabet . Second, the main ingredient to the de nition of the desired IIM M~
is the machine M from Lemma 1. However, before de ning 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 2 rf (tx)+ , and rf (tx+1) = rf (tx); sx+1 otherwise.
Obviously, given any initial segment tx of a text t one can e ectively compute rf (tx).
Statement 2. L(G ) 2 s CCONSERVATIVE
Now, let L 2 L(G ), t 2 text (L), and x 2 IN.

M~ (tx ) = \Compute rf (tx). If M on input rf (tx) outputs a hypothesis, 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 1. M~ is set-driven.
Let tx and t^y be be two initial text segments of a language L 2 L(G ) 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 weconclude M (rf (tx )) = M (rf (t^y )), since M works rearrangement-independent. That means, either
M outputs in both cases the same hypothesis or it outputs nothing on input rf (tx) and rf (t^y ),respectively. This proves the claim.
Claim 2. M~ works conservatively.
By construction, M~ outputs on any 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  t+x+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, t+x+1 6 L(G~ j ). Hence, M~ performs a justi ed mind change.
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) producesa hypothesis, too. Since M works conservatively, 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 a hypothesis.
Looking at M 's de nition, we see that M could be prevented from doing it only by detecting an
inconsistency. Consequently, M~ works conservatively.
Claim 3. M~ infers L from t.
Again, we distinguish two cases.
Case 1. L is nite.
Then there exists an x 2 IN such that t+x = L. Moreover, if M on input rf (tx) produces ahypothesis, then it is a correct one, since M works conservatively. Hence, in this case M~ infers Lfrom 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 nite language t+x in G~, since M~ is set-driven.
Case 2. L is in nite.

13

Since L is in nite, rf (t) is a text for L, too. Moreover, M has to infer L in particular fromrf (t). Therefore, there exists an x 2 IN such that M (rf (t)x+r ) = k with L(Gk ) = L for all r 2 IN.
Hence, after some point M~ exclusively outputs the canonical index of L(Gk ) in G~. Consequently,
it infers L.
Therefore, Statement 2 is proved. Since L  L(G ), it follows L  CCONSERVATIVE (M~ ).
q.e.d.
Corollary 6. Let L 2 CCONSERVATIVE . Then, there is a hypothesis space G = (Gj )j2IN
comprising L such that L(G ) 2 s ECONSERVATIVE .
Proof. Let L 2 CCONSERVATIVE . Furthermore, due to the latter theorem, there is an IIM
M~ and a hypothesis space G~ such that L  s CCONSERVATIVE (M~ ) w.r.t. G~. Let M~ and G~ bede ned as in Lemma 2.
Recall that G~ is a canonical enumeration of grammars de ning all languages in L and of all nitelanguages over the underlying alphabet. Without loss of generality we may assume that G~ ful lls
the following property. If j is even, then L(G~ j ) 2 s CCONSERVATIVE (M ). Otherwise, L(G~ j )is a nite language.
We start with the de nition of the desired hypothesis space G = (Gj )j 2IN . If j is even, then weset Gj = G~j . Otherwise, we distinguish the following cases. If M when fed the lexicographicallyordered enumeration of all strings in L(G~ j ) outputs the hypothesis j , then we set Gj = G~j . In caseit does not, we set Gj = G~ j 1.
Now we are ready to de ne the desired IIM M witnessing L(G ) 2 s ECONSERVATIVE . Let
L 2 L(G ), t 2 text (L), and x 2 IN.

M (tx ) = \Simulate M~ on input tx . If M~ does not output any hypothesis, then output nothing andrequest the next input.
Otherwise, let M~ (tx ) = j . Output j and request the next input."

Since M~ is a conservatively working and set-driven IIM, M behaves thus. It remains toshow that M learns L. Obviously, if L = L(G2k ) for some k 2 IN, then M~ infers L, since
L 2 s CCONSERVATIVE (M~ ). Therefore, since M simulates M~ , we are done.
Now, let us suppose, L 6= L(G2k ) for some k 2 IN. By de nition of G , we know that L is nite.
Moreover, since t is a text for L, there exists an x such that t+y = L for all y  x. Recallingthe de nition 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(Gj ). Hence, M (tx) = j , too. Finally, since M is set-driven, we
directly get M (ty ) = j for all y  j . Consequently, M learns L.
q.e.d.
The next theorem gives some more evidence that set-drivenness is not that restrictive as it might
seem.

Theorem 7.

(1) s SMON n EWMON 6= ;,(2) s CSMON n WMON 6= ;,(3) s EWMON n MON 6= ;.
14

Proof. First of all, we show assertion (1). Let us consider the following indexed family Lsm =(Lhk;j i )j;k2IN. For all k 2 IN, we set Lhk;0i = fak bn n 2 IN+g. For all k 2 IN and all j 2 IN+ , wedistinguish the following cases:
Case 1. : k (k)  j .
We set: Lhk;j i = Lhk;0i .
Case 2. k (k)  j .
Then, we set: Lhk;j i = fak bm 1  m  k (k)g.

In Lange and Zeugmann (1993b) it was already shown that the family Lsm is witnessing SMON n

EWMON 6= ;. Hence, it remains to show the following claim.
Claim A. Lsm 2 SMON .

We have to show that there are a space of hypotheses G = (Gj )j 2IN with range(Lsm ) = L(G )and a set-driven IIM M such that M does strong-monotonically infer L w.r.t. G .
TFirst of all, we de ne the space of hypotheses G . For all k 2 IN, we set L(G2k ) = j 2IN Lhk;j i andL(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 ) = L(G ).
Let L 2 Lsm , let t be any text for L, and let x 2 IN. The desired IIM M is de ned as follows.

M (tx ) = \Determine the unique k such that t0 = ak bm for some m 2 IN. Test whether or not
t+x 2 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 mind change
satis es the monotonicity requirement. Furthermore, M converges to a correct hypothesis for L.
Accordingly to the de nition, it is easy to see that M is indeed a set-driven IIM. This proves ClaimA, and therefore (1) follows.
In order to prove assertion (2), we use the following indexed family Lcsm = (Lhk;j i )j;k2IN . For all
k 2 IN we set Lhk;0i = fak bn n 2 IN+ g. For all k 2 IN and all j 2 IN+ we distinguish the following
cases:
Case 1. :k (k) > j
We set: Lhk;j i = Lhk;0iCase 2. k (k)  j
Let d = j k (k). Then, we set:
Lhk;j i = fak bm 1  m  k (k)g [ fak bk (k)+2(d+m) m 2 IN+ g

By reducing the halting problem to Lcsm 2 WMON , one may prove that Lcsm 62 WMON .
An IIM M witnessing Lcsm 2 s CSMON can be easily designed, if one choose theT following
space of hypotheses G = (Ghk;j i)j;k2IN . For all k; j 2 IN, we set L(Ghk;0i ) = j 2IN Lhk;j i andL(Ghk;j +1)) = Lhk;j i. We omit further details.
15

The remaining part can be easily shown. One has simply to choose the same indexed family as
used in Lange and Zeugmann (1993a) in order to separate WMON and MON .
q.e.d.

4. Learning with Rearrangement-Independent IIMs.
In this section we study the impact of rearrangement-independence on the learning power of
IIMs. We start with learning in the limit. Angluin (1980b) characterized the learnability of thoseindexed families L that are inferable w.r.t. the hypothesis space L in terms of nite, 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 (1993d)), and hence weknow 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 Schafer(1984), and later, but independently by Fulk (1990) who proved that any IIM M learning in thelimit may be replaced by a rearrangement-independent IIM that infers as least as much than M
does. Moreover, Schafer's (1984) and Fulk's (1990) is much stronger than Angluin's (1980b), since
it is not restricted to the learnability of indexed families. By the next theorem we summarize theknown results.

Theorem 8. (Angluin (1980b), Schafer (1984), Fulk (1990))
r ELIM = ELIM = LIM = CLIM

However, neither Schafer's (1984) nor Fulk's (1990) transformation does preserve any of themonotonicity requirements de ned 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 9.

(1) r ESMON = ESMON ,(2) r SMON = SMON .
Proof. First, we prove assertion (2).
Let L 2 SMON . Applying the characterization theorem for SMON (cf. Lange and Zeugmann(1992)), we know that there exists a class preserving space of hypothesis G = (Gj )j 2IN as well as arecursively generable family (Tj )j 2IN of nite non-empty sets such that(i) for all j 2 IN, Tj  L(Gj ),(ii) for all j; k 2 IN, if Tj  L(Gk ), then L(Gj )  L(Gk ).
On the basis of this family (Tj )j 2IN we de ne a IIM M witnessing L 2 r SMON . So let L 2 L,t 2 text(L), and x 2 IN.

M (tx ) = \Search for the least j  x for which Tk  t+x  L(Gk ). If it is found, output j andrequest the next input.
Otherwise, output nothing and request the next input."
16

Obviously, M is a rearrangement-independent IIM. It remains to show that L 2 SMON (M )w.r.t. the hypothesis space G .
Claim 1. M infers L on text t.
Let j = z [L(Gz ) = L]. Hence, there is a least x such that Tj  t+x . Therefore, M will output
ones a hypothesis. For all k < j with Tk  L we may conclude that L(Gk )  L. Otherwise, we
obtain L(Gj ) = L(Gk ) = L, because of Tk  L(Gk ) and Tj  L(Gj ) (cf. (ii)). Hence, there exists
a y such that t+y 6 L(Gk ) for all k < j with Tk  L. Therefore, M (ty+r ) = j for all r 2 IN. This
proves the claim.
Claim 2. M works strong-monotonically.
Let M (tx ) = j and M (tx+r ) = k for some x 2 IN and r 2 IN+ . Due to the de nition of M , wehave Tj  t+x  L(Gk ). Therefore, L(Gj )  L(Gk ) (cf. (ii)). This proves the claim.
To sum up, M is witnessing L 2 r SMON . Thus assertion (2) is shown.
Next, we prove assertion (1). Let L 2 ESMON . Because of ESMON  SMON as well as
of assertion (2), there exists a rearrangement-independent IIM M^ as well as a class preserving
hypothesis space G such that L  r SMON (M ) w.r.t. the hypothesis space G .
Applying Theorem 4 of Lange and Zeugmann (1993b), we know that there exists some total
recursive function f : IN  IN ! IN satisfying(i) for all j 2 IN, limx!1f (j; x) = k exists and satis es L(Gj ) = Lk ,(ii) for all j; x 2 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 strong-monotonic
compiler f , we de ne an IIM M witnessing L 2 r ESMON . So, let L 2 L, t 2 text(L), andx 2 IN.

M (tx ) = \Simulate M^ on input tx. If M^ when fed successively tx does not output any guess, thenoutput nothing and request the next input.
Otherwise, let j = M^ (tx ). If t+x  L(Gj ), then execute (A1). Otherwise, output nothing andrequest the next input.
(A1) Find the least y 2 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 be e ectively performed. Additionally, since L is an indexed family, the test within instruction (A1) can bee ectively accomplished, too. Furthermore, by property (i) of f and since t+x  L(Gj ), instruction(A1) has to terminate for every j 2 IN. Hence, M is indeed an IIM. Due to its de nition, M isrearrangement-independent IIM, since the IIM M^ simulated by M is rearrangement-independentby assumption.
It remains to show that M strong-monotonically infers L from text t. Since M^ infers L fromtext t and by property (i) of f , M converges to a correct hypothesis for L. Finally, we showthat M ful lls the strong-monotonicity constraint. Let f (j; y) and f (k; z ) denote two successively
17

hypotheses generated by M . Hence, M (tx ) = f (j; y) and M (tx+r ) = f (k; z ) for some x 2 IN,
r 2 IN+. We distinguish the following cases.
Case 1. j = k
Due to the de nition of M , we may conclude y  z . Hence, property (ii) guarantees Lf (j;y) 
Lf (j;z).
Case 2. j 6= k
Since f satis es (i) and (ii), we obtain Lf (j;y)  L(Gj ). Furthermore, M 's de nition implies+
tx+r  Lf (k;z). Hence, the given IIM M^ has generated the hypothesis j on an initial segment of atext for Lf (k;z) 2 L. Since M^ works strong-monotonically on every text for every language L 2 L,
we may conclude that L(Gj )  Lf (k;z) . Together with Lf (j;y)  L(Gj ), we get Lf (j;y)  Lf (k;z) .
Thus, M is rearrangement-independent and it works strong-monotonically. This proves thetheorem.
q.e.d.
It remains open whether or not the above theorem extends to the class comprising case. Next
we consider monotonic language learning. Now, the situation is completely di erent, since we havethe following theorem.

Theorem 10.

(1) s EMON  r EMON  EMON ,(2) s MON  r MON  MON .
Proof. First of all, we show r EMON n s MON 6= ;. By de nition, this yields immediately
s EMON  r EMON as well as s MON  r MON .
Lemma 1. r EMON n s MON 6= ;By Theorem 3 we already know that r ESMON n s LIM 6= ;. It is easy to verify thatr ESMON  r EMON . By de nition, s MON  s LIM . Hence, we may conclude
r EMON n s MON 6= ;. This proves the lemma.
It remains to show EMON nr MON 6= ;. This statement directly implies r EMON  EMON
and r MON  MON , and hence, the is theorem is proved.
Lemma 2. EMON n r MON 6= ;First of all, we de ne a corresponding family L = (Lk )k2IN . For all k 2 IN and all z 2 f0; : : : ; 3g

we de ne:8>
fak bg [ Ak ;><kk;
L4k+z = > fak b;faak ccgg [[ BA;>
: fak b; ak cg [ Bk ;kif z = 0;
if z = 1;
if z = 2;
if z = 3:

The remaining languages Ak and Bk will be de ned via their characteristic functions fA andfB , respectively. For all k 2 IN and all strings s 2 fa; b; cg+ we set:(
; if s = bk am and k (k) = m;fA (s) = 01;; otherwise
:
k

k

k

18

(

fB (s) = 01;;k

if s = ck am and k (k) = m;otherwise:

After a bit of re ection, it is easy to see that L is indeed an indexed family.
Claim 1. L 2 EMON
We de ne an IIM which monotonically infers every L 2 L from any text t for L w.r.t. thehypothesis space L itself. So let us assume any L 2 L, any text t for L and any x 2 IN.

M (tx ) = \If x = 0 or M has not produced any hypothesis when successively fed tx 1 , then execute(A1). Otherwise, goto (A2).
(A1) If ak b 2 t+x for some k 2 IN, then output 4k and request the next input.
If ak c 2 t+x for some k 2 IN, then output 4k + 1 and request the next input.
Otherwise, output nothing and request the next input.
(A2) Let M (tx 1 ) = j . If t+x  Lj , then repeat the hypothesis j and request the next input.
Otherwise, goto (A3).
(A3) If j = 4k or j = 4k + 1, respectively, for some k 2 IN, then output the hypothesis j + 2
and request the next input.
Otherwise, goto (A4).
(A4) If j = 4k + 2 for some k 2 IN, output 4k + 3 and request the next input.
Otherwise, output 4k + 2 and request the next input."

It remains to show L  EMON (M ). Obviously, for every k 2 IN, M identi es L4k as wellas L4k+1 on every text for the corresponding language. Thereby, M does not perform any mindchange at all. Hence, M works monotonically on every t 2 text(L4k )[ text(L4k+1 ), k 2 IN. Let us
assume any k 2 IN such that t is either a text for L4k+2 or for L4k+3 . In order to show that M
satis es the monotonicity constraint we distinguish the following cases.
Case 1. 'k (k) "Consequently, we obtain L4k+2 = L4k+3 . Since t is a text for the nite language L4k+2 , there
is an x 2 IN such that t+x = L4k+2 . Hence, M (tx+r ) = j with Lj = L4k+2 , for all r 2 IN+ .
Furthermore, M has generated at most one di erent hypothesis before this point. Therefore, M
works monotonically. Note that M may converge to di erent hypotheses on di erent texts for thesame nite language. Consequently, M is not rearrangement-independent.
Case 2. 'k (k) #Since L4k+2 as well as L4k+3 de ne nite languages, it is easy to see that M converges to acorrect hypothesis. We distinguish the following subcases.
Subcase 2.1. t is a text for L4k+2
If M rst generates the hypothesis 4k, then it needs only one mind change to infer L4k+2 .
Consequently, M works monotonically. Otherwise, 4k +1 is M 's rst hypothesis. Now, it is easy toverify that M produce the sequence of hypotheses 4k + 1, 4k + 3 and 4k + 2. Due to the de nitionof the family L, L4k+1 \ L4k+2  L4k+3 directly implies L4k+1 \ L4k+2  L4k+3 \ L4k+2  L4k+2 .
Hence, M works monotonically.
Subcase 2.2. t is a text for L4k+3
19

Then, a quite similar argumentation yields that M works monotonically. If M outputs the
hypothesis 4k +1 as its rst guess, then again, one mind change suces to identify L4k+3 . Otherwise,
M produces the sequences of hypotheses 4k, 4k + 2 and 4k + 3. Due to the de nition of the family
L, L4k \ L4k+3  L4k+2. As before, this directly implies that M works monotonically.
Therefore, we obtain L  EMON (M ), and the claim is proved.
Claim 2. L 62 r MON
Suppose the converse, i.e., there is a class preserving hypothesis space G = (Gj )j 2IN and an IIM
M such that L  r MON (M ) w.r.t. G .
Claim 3. Given G and any program for M witnessing L 2 r MON , one can e ectively construct
an algorithm deciding whether or not 'k (k) #.
Next to, we de ne the desired algorithm.

Algorithm A: \On input k execute (A1) until ( 1) or ( 2) are ful lled, respectively. Afterwards,

execute (A2).
(A1) 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 de ned texts
for L = fak bg and L^ = fak cg, respectively. If M outputs on both initial segmentsa hypothesis, say m and m^ , respectively, then test whether ak b 2 L(Gm ) and ak c 2
L(Gm^ ).
(A2) If ( 1) happens rst, then output \'k (k) converges" and stop.
Otherwise, in parallel execute ( 1) or ( 2) for y = 1; 2; : : :, until one of them is successful.
( 1) Test whether k (k)  x + y.
( 2) Test whether M when fed tx+y = a| k b; :{z: : ; ak b}; a| k c; :{z: : ; ak c} generates a consistenty times(x+1) times+
hypothesis n, i.e., M (tx+y ) = n and tx+y  L(Gn).
If ( 1) happens rst, then output \'k (k) converges" and stop.
Otherwise, output \'k (k) diverges" and stop."

Due to the de nition of a complexity measure, ( 1) and ( 1) can be accomplished e ectively.
Furthermore, since M is an IIM as well as membership is uniformly decidable for L(G ), ( 2) and( 2) can be accomplished e ectively, too. Hence, A is indeed an algorithm.
First, we show that A terminates for all k 2 IN. Let us assume that the execution of (A1)does not terminate for some k 2 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
the languages fak bg, fak cg from its uniquely de ned text, a contradiction. Applying the same
arguments one can show that the execution of (A2) has to terminate, too. Hence, A terminates on
every input k 2 IN.
It remains to show that algorithm A works correctly. Obviously, if A stops its computation with\'k (k) converges", then 'k (k) is indeed de ned. Suppose that A has nished its computation with\'k (k) diverges". Furthermore, assume that 'k (k) is de ned. Due to our de nition, there exists an
x 2 IN such that M (tx ) = m and M (t^x ) = m^ with t+x  L(Gm) as well as t^+x  L(Gm^ ). After a bit20

of re ection, one can easily verify that L(Gm ) = L4k and L(Gm^ ) = L4k+1 . This is caused by theassumption that M works monotonically w.r.t. a class preserving hypothesis space. Additionally,
there exists a y 2 IN+ such that M (tx+y ) = n with t+x+y  L(Gn). Since M is rearrangementindependent, we may conclude that M (t^x+y ) = m, where t^x+y = |ak c; :{z: : ; ak c} a| k b; :{z: : ; ak b}, since

t+x+y = t^+y+x .

(x+1) times y timeskkBecause fa b; a cg  L(Gn ) as well as L(Gn ) 2 L, it suces to distinguish thefollowing two cases.
Case 1. L(Gn) = L4k+2
Since A terminates with \'k (k) diverges", we obtain k (k) > x + y. Therefore, t^x+y is an initial
segment of a text for L4k+3 . On this text, M has already generated the hypotheses m^ and n in somesubsequent steps. Since 'k (k) is de ned, by assumption we obtain L4k+1 \ L4k+3 6 L4k+2 \ L4k+3.
Therefore, L(Gm^ ) = L4k+1 and L(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 wheninferring L4k+2 from any of its texts having the initial segment tx+y .
This proves the correctness of algorithm A. Thus, Claim 3 is shown.
On the other hand, the halting problem is undecidable. Therefore, Claim 2 follows, and thetheorem is proved.
q.e.d.
Finally, we consider rearrangement-independence in the context of exact and class preserving
conservative learning. Since conservative learning is exactly as powerful as weak-monotonic one,by the latter Theorem one might expect that rearrangement-independence is a severe restriction
under the weak-monotonic constraint, too. On the other hand, looking at theorem 5 we see thatconservative learning has its peculiarities. And indeed, exact and class preserving learning canalways be performed by rearrangement-independent IIMs. In order to prove this, we rst characterize ECONSERVATIVE in terms of nite tell-tales. We present this theorem separately, since it
is interesting in its own right.
Theorem 11. Let L be an indexed family. Then, L 2 ECONSERVATIVE if and only if there
exists a recursively generable family (Tjy )j;y2IN of nite sets such that(1) for all L 2 L there exists a j with Lj = L and Tjy 6= ; for almost all y 2 IN,(2) for all j; y 2 IN, Tjy 6= ; implies Tjy  Lj and Tjy = Tjy+1 ,(3) for all j; y; z 2 IN, ; 6= Tjy  Lz implies Lz 6 Lj .
Proof. Necessity. Let L 2 ECONSERVATIVE . Then there is an IIM M such that L 
ECONSERVATIVE(M ) w.r.t. L. The desired tell-tale family (Tjy )j;y2IN is de ned as follows. Letj; y 2 IN; then we set

8< range tjz ;yTj = :;;

if z = minfx j x  y; M (tjx ) = j g;otherwise;21

where tj denotes the canonical text of Lj . Obviously, the sets Tjy are uniformly recursively
generable and nite. It remains to show that the properties (1) through (3) are ful lled.
By construction, (2) is trivially satis ed. In order to prove (1), let L 2 L and let tL be thecanonical text of L. Since M has to infer L from its canonical text, too, there exists a j suchthat j = M (tLx ) for almost all x 2 IN and L = Lj . Let y = x[M (tLx ) = j ]. Then Tjy 6= ; andTjy = Tjy+r for all r 2 IN. This proves property (1). Finally, we have to show (3). Suppose, there
are j; y; z 2 IN such that ; 6= Tjy  Lz and Lz  Lj . By the de nition of the tell-tale sets, there
exists an x  y such that M on input w0 ; :::; wx outputs j , where w0 ; :::; wx are the strings of Tjy
written in canonical order w.r.t. Lj . Furthermore, Tjy  Lz and therefore, w0 ; :::; wx is an initial
segment of a text for Lz . Since M has to infer Lz from every text, it has to perform at least one
mind change on every text t 2 text(Lz ) beginning with w0 ; :::; wx that cannot be caused by aninconsistency. This contradiction proves (3).
Suciency. The desired IIM is de ned as follows. Let L 2 L, t 2 text(L), and x 2 IN.

M (tx ) = \If x = 0 or x > 0 and M on input tx 1 does not produce 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 non-empty Tjy
check whether or not Tjy  t+x  Lj . In case there is one j ful lling the test, output theminimal 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 (1992), it iseasy to see that L  ECONSERVATIVE (M ). We omit the details.
q.e.d.
Now we are ready to prove the announced theorem stating that rearrangement-independence
does not restrict exact and class preserving conservative learning.

Theorem 12.

(1) r ECONSERVATIVE = ECONSERVATIVE ,(2) r CONSERVATIVE = CONSERVATIVE .
Proof. First we prove assertion (1). Let L 2 ECONSERVATIVE . By Theorem 11 there exists
a recursively generable family (Tjy )j;y2IN ful lling properties (1) through (3). Using this family, wede ne a new recursively generable family (T^jy )j;y2IN that satis es (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 11 is not rearrangement-independent.
We set T^jy = ;, if j  y. Now, let j < y; we de ne
8 ^y 1>Tj ;if T^jy 1 6= ;;><T^jy = ;;if T^jy 1 = ;; Tjy = ;;

>
>
:S

y
ky 1 Tk \ Lj ;22otherwise:Since (Tjy )j;y2IN is a recursively generable family and because of the uniform decidability of themembership problem for L, the family (T^jy )j;y2IN is recursively generable, too. It is easy to see that(T^jy )j;y2IN ful lls properties (1) through (3) of Theorem 11. We proceed with a technical claim thatwill be very useful in proving the rearrangement-independence of the IIM de ned below.
Claim 1. Let j; k; m; n 2 IN such that m = y[T^jy 6= ;] und n = y[T^ky 6= ;]. Then, T^kn \ Lj  T^jm
provided n  m.
In accordance with the de nition of the family (T^jy )j;y2IN we know that m > j as well as n > k.
S
S
Furthermore, T^jm = zm 1 Tzm \ Lj and T^kn = zn 1 Tzn \ Lk . Hence, we obtain:T^kn \ Lj = Szn 1 Tzn \ Lk \ Lj  Szn 1 Tzn \ Lj  Szn 1 Tzm \ Lj  Szm 1 Tzm \ Lj = T^jm .
This proves the claim.
Now we de ne the desired rearrangement-independent IIM as follows. Let L 2 L, t 2 text(L),and x 2 N .
M (tx ) = \Test for all k  x whether or not T^kx 6= ;. For all non-empty T^kx check whether or notT^kx  t+x  Lk .
In case there is no k ful lling the test, output nothing and request the next input.
Otherwise, compute yk = y[T^ky 6= ;] for all k ful lling the test. Output the minimal k forwhich yk is minimal, and request the next input."
It remains to show that L  r ECONSERVATIVE (M ). Obviously, M is rearrangementindependent.
Claim 2. M works conservatively.
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 de nition we directly obtain T^jx 6= ; 6= T^kx+r .
We consider the following cases.
Case 1. T^kx = ;.
Then we have tx+r 6 Lj . This can be seen as follows. M on input tx+r has to compute yj
and yk . Since T^kx = ;, we know that yj < yk . Consequently, if tx+r  Lj , then M outputs j , acontradiction.
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 . Weproceed with k < j . By Claim 1 we get T^kn \ Lj  T^jm . Suppose, t+x+r  Lj . Since k = M (tx+r ), we
immediately obtain that T^kn  t+x+r  Lk . Consequently, T^kn \ Lj = T^kn , and hence T^kn  T^jm  t+x ,since j = M (tx ). But this implies M (tx ) = k, since j > k, a contradiction.
Subcase 2.3.: m > n
Again, by Claim 1 we know that T^kn \ Lj  T^jm . Moreover, by assumption j = M (tx ), and23

therefore ; 6= T^jm  t+x . Because of m > n, we furthermore conclude that T^kn 6 t+x , since otherwise
M (tx ) = k. On the other hand, T^kn  t+x+r , since T^kn 6 t+x+r directly implies k 6= M (tx+r ). Finally,
if t+x+r  Lj , then T^kn \ Lj = T^kn  T^jm . But this would imply T^kn  t+x , again a contradiction.
Hence, M works conservatively, and the claim is proved.
Claim 3. M infers L.
Let L 2 L and let t 2 text(L). Moreover, let K = fk j Lk = L; T^ky 6= ; for almost all y 2 INg.
By property (1) of the family (T^jy )j;y2IN we know that K 6= ;. Let k 2 K be such that there isno k^ with k^ < k and y[T^k^y 6= ;]  y[T^ky 6= ;]. We show that M converges to k. By Claim 1,
we conclude that T^k^x 6= ; and T^ky 6= ; implies T^k^x  T^ky for all k^ 2 K with k^ 6= k. Therefore, if M
outputs at least once a correct hypothesis for L, then this hypothesis is k. Let yk = y[T^ky 6= ;].
Since t is a text for L, there exists a x  yk such that T^ky  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 thatmight be output by M . Let yj = y[T^jy 6= ;], then C may written as follows.
C = fj j j 2 IN; yj  yk ; T^jy  t+ g:
Due to the de nition of the family (T^jy )j;y2IN the condition T^jy 6= ; implies y < j . Therefore, j > yk
directly yields yj > yk . Hence, we may rewrite C as C = fj j j  yk ; yj  yk ; T^jy  t+ g.
Consequently, C is nite. Finally, applying property (3) of Theorem 11 we may conclude Lk 6 Lj
for all j 2 C with j 6= k. Hence, for all j 2 C with j 6= k there exists an xj such that tx 6 Lj .
Since C is nite, it successively shrinks to fkg, and hence M converges to k.
This proves assertion (1) of the theorem. Assertion (2) can be proved analogously as Lemma 1
in the proof of Theorem 5.
q.e.d.
kjjj

5. Summary
We start with the following gure that summarizes the results obtained and points to questions
that remain open. We shall discuss them and some less obvious ones in this section.
exact
learning

set+
drivenness
SMON rearrangement
independence +MON rearrangement
independence {WMON rearrangement
independence +LIM rearrangement
independence +FINclass preserving
learning
set+
drivenness
rearrangement +independence
rearrangement {independence
rearrangement +independence
rearrangement +independence
24class comprisinglearning
set+
drivenness

?
?
set
+
drivenness
rearrangement +independenceFor every mode of learning ID mentioned \rearrangement-independence +" indicates r ID =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.

Besides the two open problems we have pointed to in the gure above, there are two more
intriguing questions deserving attention. First, it would be highly desirable to elaborate characteristic conditions under what circumstances set-drivenness does not restrict the learning power. We
expect that such charcterizations might allow much more insight into the problem how to handle
simultaneously both, nite and in nite languages in the learning process. Next, as we have seen,
an algorithmically solvable learning problem might become infeasible, if one tries to solve it with
set-driven IIMs. On the other hand, when dealing with particular learning problems it might often
be possible to design a set-driven learning algorithm solving it. But what about the complexity oflearning in such circumstances? More precisely, we are interested in knowing whether the \highlevel" theorem separating set-driven learning from unrestricted one, has an analogue in terms ofcomplexity theory. For example, it is well conceivable that an indexed family L may be learned inpolynomial time but no set-driven algorithm can eciently infer L provided P 6= NP .

6. References[1] Angluin, D. (1980a), Finding patterns common to a set of strings, Journal of Computerand System Sciences 21, 46 - 62.
[2] Angluin, D. (1980b), Inductive inference of formal languages from positive data, Information
and Control 45, 117 - 135.
[3] Berwick, R. (1985), \The Acquisition of Syntactic Knowledge," Cambridge, Mass.: MIT
Press.
[4] Fulk, M. (1990), Prudence and other restrictions in formal language learning, Information
and Computation 85, 1 - 11.
[5] Gold, E.M. (1967), Language identi cation in the limit, Information and Control 10, 447 474.
[6] Hopcroft, J.E., and Ullman, J.D (1969), \Formal Languages and their Relation to
Automata," Addison-Wesley, Reading, Massachusetts.
[7] Jantke, K.P. (1991) Monotonic and non-monotonic inductive inference, New Generation
Computing 8, 349 - 360.
[8] Lange, S., and Wiehagen, R. (1991), Polynomial-time inference of arbitrary pattern languages, New Generation Computing 8, 361 - 370.
[8] Lange, S., and Zeugmann, T. (1992), Types of monotonic language learning and theircharacterization, in \Proceedings 5th Annual ACM Workshop on Computational Learning
Theory," July 27 - 29, Pittsburgh, pp. 377 - 390, ACM Press.
[9] Lange, S., and Zeugmann, T. (1993a), Monotonic versus non-monotonic language learning, in \Proceedings 2nd International Workshop on Nonmonotonic and Inductive Logic,"
December 1991, Reinhardsbrunn, (G. Brewka, K.P. Jantke and P.H. Schmitt, Eds.), Lecture
Notes in Arti cial Intelligence 659, pp. 254 - 269, Springer-Verlag, Berlin.
25[10] Lange, S., and Zeugmann, T. (1993b), Language learning in dependence on the spaceof hypotheses, in \Proceedings 6th Annual ACM Conference on Computational Learning
Theory," Santa Cruz, July 1993, pp. 127 - 136, ACM Press, New York.
[11] Lange, S., and Zeugmann, T. (1993c), The learnability of recursive languages in dependence on the hypothesis space, GOSLER{Report 20/93, FB Mathematik, Informatik und
Naturwissenschaften, HTWK Leipzig.
[12] Lange, S., and Zeugmann, T. (1993d), Learning recursive languages with bounded mindchanges, International Journal of Foundations of Computer Science, to appear.
[13] Machtey, M., and Young, P. (1978) \An Introduction to the General Theory of Algorithms," North-Holland, New York.
[14] Osherson, D., Stob, M., and Weinstein, S. (1986), \Systems that Learn, An Introduction to Learning Theory for Cognitive and Computer Scientists," MIT-Press, Cambridge,
Massachusetts.
[15] Schafer-Richter, G. (1984), \U ber Eingabeabhangigkeit und Komplexitat von Inferenzstrategien." Dissertation, Rheinisch Westfalische Technische Hochschule Aachen.
[16] Wexler, K. (1992), The subset principle is an intensional principle, in \Knowledge andLanguage: Issues in Representation and Acquisition," (E. Reuland and W. Abraham, Eds.),
Kluwer Academic Publishers.
[17] Wexler, K., and Culicover, P. (1980), \Formal Principles of Language Acquisition,"
Cambridge, Mass.: MIT Press.
[18] Wiehagen, R. (1991), A thesis in inductive inference, in \Proceedings First International
Workshop on Nonmonotonic and Inductive Logic," December 1990, Karlsruhe, (J. Dix, K.P.
Jantke and P.H. Schmitt, Eds.), Lecture Notes in Arti cial Intelligence Vol. 543, pp. 184 207, Springer-Verlag, Berlin.

26