Characterizations of Class Preserving Monotonic andDual Monotonic Language Learning
Thomas Zeugmann

Steffen Lange1

TH Darmstadt

TH Leipzig

Institut für Theoretische Informatik

FB Mathematik und Informatik

Alexanderstr. 10

PF 66

W–6100 Darmstadt

O–7030 Leipzig

zeugmann@iti.informatik.th-darmstadt.desteffen@informatik.th-leipzig.de

Shyam Kapur2
Institute for Research in Cognitive Science
University of Pennsylvania
3401 Walnut Street Rm 412C
Philadelphia, PA 19104, USA
skapur@linc.cis.upenn.edu

1992

1 This research has been supported by the German Ministry for Research and Technology(BMFT) under grant no. 01 IW 101.
2 This work was supported in part by ARO grant DAAL 03-89-C-0031, DARPA grant N0001490-J-1863, NSF grant IRI 90-16592 and Ben Franklin grant 91S.3078C-1.

Abstract
The present paper deals with monotonic and dual monotonic language learning frompositive as well as from positive and negative examples. The three notions of monotonicity reflect different formalizations of the requirement that the learner has to always
produce better and better generalizations when fed more and more data on the concept
to be learnt.
The three versions of dual monotonicity describe the concept that the inference device
has to exclusively produce specializations that fit better and better to the target language.
We characterize strong–monotonic, monotonic, weak–monotonic, dual strong–monotonic,
dual monotonic and monotonic & dual monotonic as well as finite language learning frompositive data in terms of recursively generable finite sets.

1. Introduction
The process of hypothesizing a general rule from eventually incomplete data is called
inductive inference. Many philosophers of science have focused their attention on problems
in inductive inference. Some of the principles developed are very much alive in algorithmic
learning theory, a rapidly emerging science since the seminal papers of Solomonoff (1964)
and of Gold (1967). The state of the art is excellently surveyed in Angluin and Smith(1983, 1987).
The present paper deals with formal language learning. In this field, many interestingand sometimes surprising results have been obtained within the last decades (cf. e.g.
Osherson, Stob and Weinstein (1986), Case (1988), Fulk (1990)). The general situation
investigated in language learning can be described as follows: Given more and more
eventually incomplete information concerning the language to be learnt, the inference
device has to produce, ¿from time to time, a hypothesis about the phenomenon to beinferred. The information given may contain only positive examples, i.e., exactly all
the strings contained in the language to be recognized, or both positive and negative
examples, i.e., arbitrary strings over the underlying alphabet which are classified withrespect to their containment to the unknown language. The sequence of hypotheses has
to converge to a hypothesis correctly describing the object to be learnt. There are many
possible requirements on the sequence of all actually created hypotheses. In all what
follows we restrict ourselves to deal exclusively with class preserving language learning,i.e., we demand that all the hypotheses produced describe a language that is contained in
the family of all target languages. This requirement seems to be a very natural one, since
any hypothesis not fulfilling it cannot be correct. Furthermore, in the present paper, we
mainly study language learning ¿from positive examples.
Monotonicity requirements have been introduced by Jantke (1991A, 1991B) and Wiehagen (1991) in the setting of inductive inference of recursive functions. We have adopted
their definitions to the inference of formal languages (cf. Lange and Zeugmann (1991,
1992A, 1992B)). Subsequently, Kapur (1992B) introduced the dual versions of monotonic language learning. The main underlying question can be posed as follows: Would it
be possible to infer the unknown language in a way such that the inference device only
outputs better and better generalizations and specializations, respectively?
The strongest interpretation of this requirement means that we are forced to produce
an augmenting (descending) chain of languages, i.e., Li ⊆ Lj (Li ⊇ Lj ) iff Lj is guessed
later than Li (cf. Definition 4 and 6, part (A)).
Wiehagen (1991) proposed to interpret “better” with respect to the language L having
to be identified, i.e., now we require Li ∩ L ⊆ Lj ∩ L iff Lj appears later in the sequenceof guesses than Li does (cf. Definition 4 (B)). That means, a new hypothesis is neverallowed to reject some string that a previously generated guess already correctly includes.
On the other hand, it is only natural to consider the dual version of the latter requirement as well. Intuitively speaking, dual monotonicity describes the following requirement:

1If, at any stage, the learner outputs a hypothesis correctly excluding a string s from thelanguage to be learnt, then any subsequent guess has to behave in the same way (cf.
Definition 6 (B)).
The third version of monotonicity, which we call weak–monotonicity and dual weak–
monotonicity, respectively, is derived from non–monotonic logics and adopts the conceptof cumulativity and of its dual analogue, respectively. Hence, we only require Li ⊆ Lj
(Li ⊇ Lj ) as long as there are no data fed to the inference device after having produced
Li that contradict Li (cf. Definition 4 and 6, part (C)).
In all what follows we restrict ourselves to deal exclusively with the learnability ofindexed families of non–empty uniformly recursive languages. This case is of special interest with respect to potential applications. The first problem arising naturally is torelate all types of monotonic language learning one to the other as well as to previously
studied modes of inference. This question has been completely answered in Lange, Zeugmann and Kapur (1992). In particular, weak–monotonically working learning devices areexactly as powerful as conservatively working ones. A learning algorithm is said to beconservative iff it only performs justified mind changes. That means, the learner may
change its guess only in case the former hypothesis “provably misclassifies” some wordwith respect to the data seen so far. Considering learning from positive and negative
examples in the setting of indexed families it is not hard to prove that conservativenessdoes not restrict the inference capabilities. Surprisingly enough, in the general setting oflearning recursive functions the situation is totally different (cf. Freivalds, Kinber andWiehagen (1992)). Looking at learning from positive data, the main problem consists
in detecting or avoiding guesses that are supersets, i.e., overgeneralizations, of the language to be inferred. Obviously, conservative learners are never allowed to output anovergeneralized hypothesis. This restriction directly yields a limitation of learning power(cf. Angluin (1980), Lange, Zeugmann and Kapur (1992)). Moreover, Angluin (1980)
proved a characterization theorem for inference from positive data that turned out to bevery useful in applications. However, it remained open whether learning ¿from positive
data that avoids overgeneralization may be characterized too. We solve this problem bycharacterizing almost all types of monotonic and dual monotonic language learning aswell as of finite inference from positive data of recursive languages in terms of recursively
generable families of recursive, non–empty and finite sets. As we shall see, the characterization theorems lead to a deeper insight into the problem of what may be inferredmonotonically and dual monotonically. Moreover, in characterizing almost all types ofmonotonic and of dual monotonic inference, we provide a unifying framework to language
learning. We shall discuss these issues throughout the paper in some more detail, since
within the current level of precision nothing more satisfactory can be added.
Characterization theorems for monotonic as well as for dual monotonic language learning on informant can be found in Lange and Zeugmann (1992B).
The paper is structured as follows. Section 2 presents preliminaries, i.e., notations anddefinitions. The characterization theorems are established in Section 3 and the subsections
therein. In Section 4, we discuss the results obtained and outline open problems. All2

references are given in Section 5.

2. Preliminaries
By N = {1, 2, 3, ...} we denote the set of all natural numbers. In the sequel weassume familiarity with formal language theory (cf. e.g. Bucher and Maurer (1984)).
By Σ we denote any fixed finite alphabet of symbols. Let Σ∗ be the free monoid overΣ. The length of a string s ∈ Σ∗ is denoted by |s|. Any subset L ⊆ Σ∗ is called alanguage. By co − L we denote the complement of L, i.e., co − L = Σ∗ \ L. Let L
be a language and t = s1 , s2 , s3 , ... an infinite sequence of strings from Σ∗ such that
range(t) = {sk | k ∈ N } = L. Then t is said to be a text for L or, synonymously, a
positive presentation. Furthermore, let i = (s1 , b1 ), (s2 , b2 ), ... be an infinite sequence ofelements of Σ∗ × {+, −} such that range(i) = {sk | k ∈ N } = Σ∗ , i+ = {sk | (sk , bk ) =(sk , +), k ∈ N } = L and i− = {sk | (sk , bk ) = (sk , −), k ∈ N } = co − L. Then we refer to i
as an informant. If L is classified via an informant then we also say that L is represented
by positive and negative data. Moreover, let t, i be a text and an informant, respectively,
and let x be a number. Then tx , ix denote the initial segment of t and i of length x,
respectively, e.g., i3 = (s1 , b1 ), (s2 , b2 ), (s3 , b3 ). Let t be a text and let x ∈ N . Then we set+−t+
x = {sk | k ≤ x}. Furthermore, by ix and ix we denote the sets {sk | (sk , +) ∈ i, k ≤ x}
and {sk | (sk , −) ∈ i, k ≤ x}, respectively.
Following Angluin (1980), we restrict ourselves to deal exclusively with indexed familiesof recursive languages defined as follows:
A sequence L1 , L2 , L3 , ... is said to be an indexed family L of recursive languages provided
all Lj are non–empty and there is a recursive function f such that for all numbers j andall strings s ∈ Σ∗ we have(f (j, s) =if s ∈ Lj
otherwise.

10

As an example, we consider the set L of all context–sensitive languages over Σ. Then
L may be regarded as an indexed family of recursive languages (cf. Bucher and Maurer(1984)). In the sequel, we sometimes denote an indexed family and its range by the same
symbol L. What is meant will be clear from the context.
As in Gold (1967), we define an inductive inference machine (abbr. IIM) to be analgorithmic device which works as follows: The IIM takes as its input larger and larger
initial segments of a text t (an informant i) and it either requires the next input string,or it first outputs a hypothesis, i.e., a number encoding a certain computer program, andthen it requires the next input string (cf. e.g. Angluin (1980)).
At this point we have to clarify what space of hypotheses we should choose, thereby
also specifying the goal of the learning process. Gold (1967) and Wiehagen (1977) pointed
out that there is a difference in what can be inferred depending on whether we want tosynthesize in the limit grammars (i.e., procedures generating languages) or decision procedures, i.e., programs of characteristic functions. Case and Lynes (1982) investigated3this phenomenon in detail. As it turns out, IIMs synthesizing grammars can be more
powerful than those ones which are requested to output decision procedures. However,in the context of identification of indexed families, both concepts are of equal power.
Nevertheless, we decided to require the IIMs to output grammars. This decision has beencaused by the fact that there is a big difference between the possible monotonicity requirements. A straightforward adaptation of the approaches made in inductive inferenceof recursive functions directly yields analogous requirements with respect to the corresponding characteristic functions of the languages to be inferred. On the other hand, it
is only natural to interpret monotonicity with respect to the language to be learnt, i.e.,
to require containment of languages as described in the introduction. As it turned out,
the latter approach increases considerably the power of all types of monotonic and dual
monotonic language learning. Furthermore, since we exclusively deal with class preserving
learning of indexed families L = (Lj )j∈N of recursive languages we almost always take asspace of hypotheses an enumerable family of grammars G1 , G2 , G3 , ... over the terminalalphabet Σ satisfying L = {L(Gj ) | j ∈ N }. Moreover, we require that membership in
L(Gj ) is uniformly decidable for all j ∈ N and all strings s ∈ Σ∗ . As it turns out, it
is sometimes very important to choose the space of hypotheses appropriately in order toachieve the desired learning goal. Then, the IIM outputs numbers j which we interpretas Gj .
A sequence (jx )x∈N of numbers is said to be convergent in the limit if and only if there
is a number j such that jx = j for almost all numbers x.
Definition 1. (Gold, 1967) Let L be an indexed family of languages, L ∈ L, and let
G = (Gj )j∈N be a space of hypotheses. An IIM M LIM − T XT (LIM − IN F )–identifies
L on a text t (an informant i) with respect to G iff it almost always outputs a hypothesis
and the sequence (M (tx ))x∈N ((M (ix ))x∈N ) converges in the limit to a number j such that
L = L(Gj ).
Moreover, M LIM − T XT (LIM − IN F )–identifies L, iff M LIM − T XT (LIM −IN F )–identifies L on every text (informant) for L. We set:
LIM −T XT (M ) = {L ∈ L | M LIM −T XT −identif ies L} and define LIM −IN F (M )analogously.
Finally, let LIM −T XT (LIM −IN F ) denote the collection of all families L of indexedfamilies of recursive languages for which there is an IIM M such that L ⊆ LIM −T XT (M ) (L ⊆ LIM − IN F (M )).
Definition 1 could be easily generalized to arbitrary families of recursively enumerable
languages (cf. Osherson et al. (1986)). Nevertheless, we exclusively consider the restrictedcase defined above, since our motivating examples are all indexed families of recursive
languages. Moreover, it may be well conceivable that the weakening of L = {L(Gj ) | j ∈N } to L ⊆ {L(Gj ) | j ∈ N } may increase the collection of inferable indexed families.
However, it does not, as the following proposition shows.
Proposition 1. (Lange and Zeugmann, 1992C) Let L be an indexed family and let
G = (Gj )j∈N be any space of hypotheses such that L ⊆ {L(Gj ) | j ∈ N } and membershipin L(Gj ) is uniformly decidable. Then we have: If there is an IIM M inferring L on
4

text (informant) with respect to G, then there is also an IIM M̂ that learns L on text
(informant) with respect to L.
Note that, in general, it is not decidable whether or not M has already inferred L.
Within the next definition, we consider the special case that it has to be decidable whether
or not an IIM has successfully finished the learning task.
Definition 2. (Trakhtenbrot and Barzdin, 1970) Let L be an indexed family of
languages, L ∈ L, and let G = (Gj )j∈N be a space of hypotheses. An IIM M F IN −T XT (F IN − IN F )–identifies L on a text t (on an informant i) with respect to G iff it
outputs only a single and correct hypothesis j, i.e., L = L(Gj ), and stops thereafter.
Moreover, M F IN −T XT (F IN −IN F )–identifies L, iff M F IN −T XT (F IN −IN F )–identifies L on every text (informant) for L. We set: F IN − T XT (M ) = {L ∈L | M F IN − T XT − identifies L}, and define F IN − IN F (M ) analogously.
The resulting identification type is denoted by F IN − T XT(F IN − IN F ).

Next, we want to formally define strong–monotonic, monotonic and weak–monotonic
inference. But before doing this, we first define consistent identification. Consistently
working learning devices have been introduced by Barzdin (1974). Intuitively, consistency
means that the IIM has to reflect correctly the information it has already been fed with.
Definition 3. (Barzdin, 1974) An IIM M CON S − T XT
identifies L on a text t (an informant i) iff(1) M LIM − T XT(CON S − IN F )–(LIM − IN F )–identifies L on t (on i)+(2) Whenever M on tx (ix ) produces a hypothesis jx , then t+x ⊆ L(Gjx ) (ix ⊆ L(Gjx )and i−x ⊆ co − L(Gjx )).

M CON S − T XT (CON S − IN F )–identifies L iff M CON S − T XT (CON S − IN F )–identifies L on every text t (informant i).
By CON S − T XT (M ) (CON S − IN F (M )) we denote the set of all languages which
M CON S − T XT (CON S − IN F )–identifies. CON S − T XT and CON S − IN F are
analogously defined as above.
Now we are ready to formally define the three types of monotonic language learning
introduced in Section 1.
Definition 4. (Jantke, 1991A, Wiehagen, 1991) An IIM M is said to identify alanguage L from text (informant)(A) strong–monotonically(B) monotonically(C) weak–monotonicallyiff
5M LIM − T XT (LIM − IN F )–identifies L and for any text t (informant i) of L as
well as for any two consecutive hypotheses jx , jx+k which M has produced when fed tx andtx+k (ix and ix+k ), for some k ≥ 1, k ∈ N , the following conditions are satisfied:(A) L(Gjx ) ⊆ L(Gjx+k )(B) L(Gjx ) ∩ L ⊆ L(Gjx+k ) ∩ L−(C) if tx+k ⊆ L(Gjx ) then L(Gjx ) ⊆ L(Gjx+k ) (if i+
x+k ⊆ L(Gjx ) and ix+k ⊆ co − L(Gjx ),then L(Gjx ) ⊆ L(Gjx+k )).

Remark: (C) in particular means that M has to work strong–monotonically as long as its
guess jx is consistent with the data fed to M after M has output jx .

We denote by SM ON − T XT, SM ON − IN F, M ON − T XT, M ON − IN F ,W M ON − T XT , W M ON − IN F the family of all thoses sets L of indexed familiesof languages for which there is an IIM inferring it strong–monotonically, monotonically,
and weak–monotonically from text t or informant i, respectively.
Note that even SM ON − T XT contains interesting “natural” families of formal languages (cf. e.g. Lange and Zeugmann (1991, 1992A)).
Figure 1 summarizes the known results concerning monotonic language learning (cf.
Lange and Zeugmann (1991)). Incomparability of sets is denoted by #.
F IN − T XT ⊂ SM ON − T XT ⊂ M ON − T XT ⊂ W M ON − T XT ⊂ LIM − T XT
T









T









T









T

T

F IN − IN F ⊂ SM ON − IN F ⊂ M ON − IN F ⊂ W M ON − IN F = LIM − IN F
Figure 1
Next to, we define conservatively working IIMs.
Definition 5. (Angluin, 1980)
An IIM M CONSERVATIVE–TXT (CONSERVATIVE–INF)–identifies L on text t (oninformant i), iff for every text t (informant i) the following conditions are satisfied:(1) L ∈ LIM − T XT (M )(L ∈ LIM − IN F (M ))(2) If M on input tx makes the guess jx and then makes the guess jx+k 6= jx at somesubsequent step, then L(Gjx ) must fail to contain some string from tx+k (L(Gjx ) must−
fail either to contain some string s ∈ i+x+k or it generates some string s ∈ ix+k ).
CONSERVATIVE–TXT(M ) and CONSERVATIVE –INF(M) as well as the collectionsof sets CONSERVATIVE–TXT and CONSERVATIVE–INF are defined in a manner
analogous to that above.
6

Intuitively speaking, a conservatively working IIM performs exclusively justified mindchanges. Note that W M ON −T XT = CONSERVATIVE–TXT as well as W M ON −IN F= CONSERVATIVE–INF.
We continue in formally defining the three types of dual monotonic language learning
introduced in Section 1.
Definition 6. An IIM M is said to identify a language L from text (informant)(A) dual strong–monotonically(B) dual monotonically(C) dual weak–monotonicallyiff
M LIM − T XT (LIM − IN F )–identifies L and for any text t (informant i) of L as
well as for any two consecutive hypotheses jx , jx+k which M has produced when fed tx andtx+k (ix and ix+k ), for some k ≥ 1, k ∈ N , the following conditions are satisfied:(A) co − L(Gjx ) ⊆ co − L(Gjx+k )(B) co − L(Gjx ) ∩ co − L ⊆ co − L(Gjx+k ) ∩ co − L−(C) if tx+k ⊆ L(Gjx ), then co − L(Gjx ) ⊆ co − L(Gjx+k ) (if i+
x+k ⊆ L(Gjx ) and ix+k ⊆co − L(Gjx ), then co − L(Gjx ) ⊆ co − L(Gjx+k )).

By SM ON d − T XT , SM ON d − IN F , M ON d − T XT , M ON d − IN F , W M ON d −T XT , and W M ON d − IN F we denote the collections of all those indexed families Lof languages for which there is an IIM identifying it dual strong–monotonically, dual
monotonically and dual weak–monotonically from text and informant, respectively.
The next figure shows the relations between the defined modes of dual monotonic
inference (cf. Lange, Zeugmann and Kapur (1992)). Compared with Figure 1 it may help
to illustrate the similarities as well as the differences between the types of monotonic andof dual monotonic inference.
F IN − T XT = SM ON d − T XT ⊂ M ON d − T XT ⊂ W M ON d − T XT ⊆ LIM − T XT
T

T









T









T

T

F IN − IN F ⊂ SM ON d − IN F ⊂ M ON d − IN F ⊂ W M ON d − IN F = LIM − IN F
Figure 27Note that the notion of monotonicity and of dual monotonicity are truly duals of eachother.
Next, we combine the monotonicity constraints ¿from Definition 4 and Definition 6. As
we shall see, this might help to gain a better understanding of the relationships between
monotonic inference of languages and other well–known types of language learning.
Definition 7. Let SM ON & − T XT (SM ON & − IN F ) denote the class of indexedfamilies learnable by an IIM that works strong–monotonically as well as dual strong–monotonically. The identification types M ON & − T XT , M ON & − IN F , W M ON & −T XT and W M ON & − IN F are defined analogously.
Finally, we present two figures relating all types of monotonic language learning to alltypes of dual monotonic inference of recursive languages. For the sake of readability, we
separate the results for language learning on text from those ones dealing with language
learning ¿from positive and negative data.
The lines between the identification types indicate set inclusion, i.e., the lower typeis properly contained in the upper one. Missing lines indicate incomparability of thecollections of sets.
LIM − T XTS|W M ON d − T XT
HH

H

HH

CONSERVATIVE-TXT = W M ON − T XT

HH

H

HH

HH

H

HH
H

M ON d − T XT

M ON − T XT
b
b
b
b

&

M ON − T XT

((((
(

(((
((((

(((

(

SM ON − T XTF IN − T XT = SM ON d − T XT = SM ON & − T XT
Figure 3
The next figure relates monotonic and dual monotonic language learning on informant.

8

W M ON − IN F & = W M ON d − IN F = W M ON − IN F = LIM − IN F


Z



Z




Z
Z

M ON d − IN F

M ON − IN F

Z
Z



Z


Z



M ON & − IN F


Z



Z




Z
Z

SM ON d − IN F

SM ON − IN F

Z
Z



Z


Z



SM ON & − IN F = F IN − IN F
Figure 4
Additional results which give further insights into the relations between the defined
identification types can be found in Lange, Zeugmann and Kapur (1992).

3. Characterization Theorems
In this section, we present characterizations of all types of monotonic and of dual monotonic language learning from positive data. Characterizations play an important rolein that they lead to a deeper insight into the problem how algorithms performing theinference process may work (cf. e.g. Blum and Blum (1975), Wiehagen (1977, 1991),
Angluin (1980), Zeugmann (1983), Jain and Sharma (1989)). Starting with the pioneering paper of Blum and Blum (1975), several theoretical frameworks have been used forcharacterizing identification types. For example, characterizations in inductive inferenceof recursive functions have been formulated in terms of complexity theory (cf. Blum andBlum (1975), Wiehagen and Liepe (1976), Zeugmann (1983)) and in terms of computable
numberings (cf. e.g. Wiehagen (1977), (1991) and the references therein). Surprisingly,
some of the presented characterizations have been successfully applied for solving highly
nontrivial problems in complexity theory. Moreover, up to now it remains open how tosolve the same problems without using these characterizations. It seems that characterizations may help to get a deeper understanding of the theoretical framework where theconcepts for characterizing identification types are borrowed from. Furthermore, characterizations may help gain a better understanding of the properties objects should have in9order to be inferable in the desired sense. A very illustrative example is Angluin’s (1980)
characterization of those indexed families for which learning in the limit from positive
data is possible. In particular, this theorem provides insight into the problem how todeal with overgeneralizations. Theorem 5 below offers an alternative way to resolve thisquestion.
Proposition 2. (Angluin, 1980) Let L be an indexed family of recursive languages.
Then: L ∈ LIM − T XT if and only if there is an effective procedure which on any inputj ∈ N enumerates a tell–tale set Tj of strings such that
(1) Tj is finite.
(2) For all j ∈ N, Tj ⊆ Lj .
(3) For all j, z ∈ N , if Tj ⊆ Lz , then Lz 6⊂ Lj .
Originally, this theorem characterized all those indexed families L of recursive languages which are inferable with respect to L. However, a straightforward application of
Proposition 1 yields that Proposition 2 completely characterizes indexed families which
are inferable in the limit from positive data.
Though Angluin (1980) established some sufficient conditions that guarantee conservative learning from positive data, it remained open whether CONSERVATIVE–TXT may
be characterized in terms of finite non–empty sets. So let us start this section with asolution to this long standing open problem. The characterization of CONSERVATIVE–
TXT has been obtained by developing two new ideas. First, looking at Proposition 1
and 2, it might seem that the particular choice of the space of hypotheses is negligible.
However, when dealing with conservative learning, the situation is totally different (cf.
Lange, Zeugmann and Kapur (1992)). Therefore, in characterizing conservative learning
one has to construct an appropriate space of hypotheses. Second, this construction is
combined with an effective procedure generating recursive tell–tale sets rather than recursively enumerable ones as in Proposition 2. Finally, we state the announced theorem
as a characterization of weak–monotonic language learning from positive data.

3.1. The Characterization of Weak–Monotonic Inference
Our first theorem characterizes W M ON −T XT in terms of recursively generable finite
tell–tales. A family of finite sets (Tj )j∈N is said to be recursively generable iff there is a
total effective procedure g which, on input j, generates all elements of Tj and stops. If
the computation of g(j) stops and there is no output, then Tj is considered to be empty.
Finally, for notational convenience, we use L(G) to denote {L(Gj ) | j ∈ N } for any space
G = (Gj )j∈N of hypotheses.
Theorem 1. Let L be an indexed family of recursive languages. Then: L ∈ W M ON −T XT if and only if there are a space of hypotheses Ĝ = (Ĝj )j∈N and a recursively generable
family (T̂j )j∈N of finite and non–empty sets such that10

(1) range(L) = L(Ĝ).
(2) For all j ∈ N , T̂j ⊆ L(Ĝj ).
(3) For all j, z ∈ N , if T̂j ⊆ L(Ĝz ), then L(Ĝz ) 6⊂ L(Ĝj ).
Proof. Necessity: Let L ∈ W M ON −T XT = CONSERVATIVE–TXT. Then there are
an IIM M and a space of hypotheses (Gj )j∈N such that M infers any L ∈ L conservatively
with respect to (Gj )j∈N . We proceed in showing how to construct Ĝ = (Ĝj )j∈N . This isdone in two steps. First, we construct a space of hypotheses G̃ = (G̃j )j∈N as well as arecursively generable family (T̃j )j∈N of finite but possibly empty sets. Then, we describe
a procedure enumerating a certain subset of G̃ which we call Ĝ. Let c : N × N → N be
Cantor’s pairing function. We define the space of hypotheses (G̃j )j∈N as well as the wanted
family (T̃j )j∈N as follows: On input j compute k, x ∈ N such that j = c(k, x). Then set
G̃c(k,x) = Gk . Furthermore, for any language L(Gk ), we denote by tk the canonicallyordered text of L(Gk ) defined as follows: Let s1 , s2 , ... be the lexicographically ordered
text of Σ∗ . Test sequentially whether sz ∈ L(Gk ), for z = 1, 2, 3, ..., until the first z isfound such that sz ∈ L(Gk ). Since L(Gk ) 6= ∅, there must be at least one z fulfilling thetest. Set tk1 = sz . We proceed inductively:
 k
t s


 x z+x+1

if


otherwise, where sis the last string in tkx

tkx+1 =
tkx ssz+x+1 ∈ L(Gk )We define:T̃c(k,x) = range(tky )


∅

if

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

Obviously, T̃c(k,x) is uniformly recursively generable and finite. The desired space of
hypotheses Ĝ is obtained from G̃ by simply striking off all grammars G̃c(k,x) for whichT̃c(k,x) = ∅. Analogously, (T̂j )j∈N is obtained from (T̃j )j∈N . Obviously, (T̂j )j∈N is arecursively generable family of finite and non–empty sets. In order to save notational
convenience, we refer to T̂j as to T̂c(k,x) , i.e., we omit the corresponding bijective mappingyielding the enumeration of the sets T̂j from T̃z . It remains to show that Ĝ = (Ĝj )j∈N and(T̂j )j∈N do fulfil the announced properties. Due to our construction, (2) holds obviously.
In order to prove (1), let L ∈ L. We have to show that there is at least a j ∈ N suchthat for j = c(k, x) we have L = L(Ĝc(k,x) ). For this purpose, due to our construction, it
suffices to show that T̃c(k,x) 6= ∅. Let tL be L’s canonically ordered text. Since M has toinfer L on tL , there are k, y ∈ N such that for all z < y, M (tLz ) 6= k, M (tLy ) = k and
L = L(Gk ). Consequently, T̃c(k,y) = range(tLy ). Hence, by the convention made above,
we get that T̂c(k,y) = range(tLy ). Moreover, it immediately follows that L = L(Ĝc(k,x) )11

for any x ≥ y. This proves property (1). Finally, we have to show (3). It resultsfrom the requirement that any conservatively working IIM is never allowed to output anovergeneralized hypothesis, i.e., a guess that generates a proper superset of the language to
be inferred. To see this, suppose the converse, i.e., there are j, z ∈ N such that T̂j ⊆ L(Ĝz )and L(Ĝz ) ⊂ L(Ĝj ). By definition, there are uniquely determined k, x ∈ N such thatj = c(k, x). Let s1 , ..., sy be the strings of T̂j in canonical order with respect to L(Ĝc(k,x) ).
By construction we obtain M (s1 , ..., sy ) = k. Now we conclude that s1 , ..., sy is an initial
segment of the canonically ordered text for L(Ĝz ), since T̂j ⊆ L(Ĝz ) ⊂ L(Ĝj ) = L(Ĝc(k,x) ).
Finally, M has to infer L(Ĝz ) on its canonically ordered text. Thus, it has to perform amind change in some subsequent step which cannot be caused by an inconsistency. This
contradiction yields (3).
Sufficiency: It suffices to prove that there is an IIM M inferring any L ∈ L on any
text with respect to Ĝ. So let L ∈ L and let t be any text for L, and x ∈ N .
M (tx ) = “If x = 1 or M on tx−1 does not output a hypothesis, then goto (B). Otherwise,
goto (A).
(A) Let j be the hypothesis produced last by M when fed with tx−1 . Test whethert+x ⊆ L(Ĝj ). In case it is, output j and request the next input. Otherwise,
goto (B).
(B) For j = 1, ..., x, generate T̂j and test whether T̂j ⊆ t+x ⊆ L(Ĝj ). In case there
is at least a j fulfilling the test, output the minimal one. Otherwise, output
nothing and request the next input.”
Since all of the T̂j are uniformly recursively generable and finite, we see that M is an
IIM. Now it suffices to show that M infers L on t conservatively. Since the machine Mchanges its mind only in case it finds an inconsistency in (A), it works conservatively.
Claim 1. M converges on (tx )x∈N
Let z = µk[L = L(Ĝk )]. Consider T̂1 , ..., T̂z . Then there must be an x such thatT̂z ⊆ t+x ⊆ L(Ĝz ). That means, at least after having fed tx to M , the machine M
outputs a hypothesis. Furthermore, after having fed tx to M , the machine M always
outputs a hypothesis and it never outputs a guess j > x since z ∈ {k ≤ x | T̂k ⊆ t+x ⊆L(Ĝk )}. Moreover, since M changes its mind if and only if it receives some text stringthat misclassifies its current guess, we see that any rejected hypothesis is never repeated insome subsequent step. Finally, since at least z can never be rejected, M has to converge.
Claim 2. If M converges, say to j, then L = L(Ĝj ).
Suppose the converse, i.e., M converges to j and L 6= L(Ĝj ).
Case 1. L \ L(Ĝj ) 6= ∅Consequently, there is at least one string s ∈ L \ L(Ĝj ) that has to appear sometime int, say in tr for some r. Thus, t+
r 6⊆ L(Ĝj ). Hence, after having fed with tr , our IIM M
never outputs j, a contradiction.
12

Case 2. L(Ĝj ) \ L 6= ∅Then, we may restrict ourselves to the case L ⊂ L(Ĝj ), since otherwise we are again in
Case 1. On the other hand, due to the definition of M there should be an r ∈ N suchthat M in (B) verifies T̂j ⊆ t+r ⊆ L(Ĝj ), since otherwise it cannot output j at least once.
Moreover, since L = L(Ĝz ) and t+r ⊆ L(Ĝz ) for any r ∈ N , we conclude T̂j ⊆ L(Ĝz ).
Hence L = L(Ĝz ) 6⊂ L(Ĝj ) by property (3), a contradiction.
q.e.d.
Because W M ON & − T XT = W M ON − T XT , the theorem above yields a characterization of W M ON & − T XT too.
Kapur and Bilardi (1992) also established characterizations of conservative learning.
Their main characterization differs at least conceptually from the one presented above.
In order to see the difference, we need the following notion. Let A be a finite set andlet L be an indexed family of languages. A language L ∈ L is said to be a least upperbound of A iff A ⊆ L and any language L̂ ∈ L containing A is not a proper subset of L.
Kapur and Bilardi (1992) showed that conservative learning is equivalent to the existenceof a recursive enumeration of pairs of finite sets and grammars such that, in each pair,the language corresponding to the grammar is a least upper bound of the corresponding
finite set, and, for each L ∈ L, there is at least a corresponding pair. Consequently, thischaracterization is conceptually based on the judicious use of a function computing least
upper bounds. Our approach is in some sense converse in that we construct a suitableenumeration L̂ of L and for every language L̂ ∈ L̂ a recursive and finite set such that L̂
is a least upper bound of it.

3.2. The Characterization of Strong–Monotonic Inference
Next we characterize SM ON − T XT . As it turned out, the same proof techniquepresented above applies mutatis mutandis to obtain the following theorem.
Theorem 2. Let L be an indexed family of recursive languages. Then: L ∈ SM ON −T XT if and only if there are a space of hypotheses Ĝ = (Ĝj )j∈N and a recursively generable
family (T̂j )j∈N of finite and non–empty sets such that(1) range(L) = L(Ĝ).
(2) For all j ∈ N , T̂j ⊆ L(Ĝj ).
(3) For all j, z ∈ N , if T̂j ⊆ L(Ĝz ), then L(Ĝj ) ⊆ L(Ĝz ).
Proof. Necessity: Let L ∈ SM ON − T XT (M ). The recursively generable family(T̂j )j∈N of finite and non–empty sets is analogously defined as in in the proof of Theorem
1. Using the same arguments as above one, immediately obtains property (1) and (2). In
order to prove (3), let T̂j ⊆ L(Ĝz ). We have to show that L(Ĝj ) ⊆ L(Ĝz ). Let k, x be theuniquely determined numbers with j = c(k, x). Furthermore, let s1 , ..., sy be the strings
13

of T̂j in canonical order with respect to L(Ĝc(k,x) ) such that M (s1 , ..., sy ) = k for the firsttime. Since T̂j ⊆ L(Ĝz ), we see that s1 , ..., sy is also an initial segment of some text forL(Ĝz ). Consequently, s1 , ..., sy may be extended to a text for L(Ĝz ) . Finally, since M
has to infer L(Ĝz ) too, there should be an n ∈ N and a finite extension σ of strings ofL(Ĝz ) such that M (s1 , ..., sy , σ) = n and L(Ĝz ) = L(Gn ). M works strong–monotonicallyand hence, by the transitivity of ⊆, we obtain L(Ĝj ) ⊆ L(Ĝz ).
Sufficiency: It suffices to show that there is an IIM M that identifies L with respect
to Ĝ. Let L ∈ L, let t be any text for L, and let x ∈ N . The wanted IIM M is defined asfollows:
M (tx ) = “Generate T̂j and test whether T̂j ⊆ t+x ⊆ L(Ĝj ) for j = 1, ..., x. In case there is
at least a j fulfilling the test, output the minimal one and request the next input.
Otherwise output nothing and request the next input.”
We have to show that M infers L strong–monotonically. Since all of the T̂j are uniformly recursively generable and finite we see that M is an IIM. First we show that M
identifies L on t. Let k = µz[L = L(Ĝz )]. We claim that M converges to k. ConsiderT̂1 , ..., T̂k . Then there must be an x such that T̂k ⊆ t+x ⊆ L(Ĝk ). Thus, at least after
having fed tx to M the machine must output a guess. Moreover, since for all r ∈ N we
additionally have T̂k ⊆ t+x+r ⊆ L(Ĝk ), we may conclude that after having fed tx to M , itnever produces a hypothesis j > k. Suppose M converges to j < k. Due to the choice ofk we know L(Ĝj ) 6= L(Ĝk ) = L.
Case 1. L ⊂ L(Ĝj )By construction, if M outputs j at all, then there should be an n ∈ N such that+T̂j ⊆ t+n ⊆ L(Ĝj ). Moreover, since t is a text for L = L(Ĝk ), we know that tn ⊆ L(Ĝk )for all n ∈ N . Hence T̂j ⊆ L(Ĝk ). Now we can apply property (3) and obtain L(Ĝj ) ⊆L(Ĝk ) = L, a contradiction. Moreover, a closer look at the latter argument shows that
M can never output an overgeneralized hypothesis.
Case 2. L \ L(Ĝj ) 6= ∅Again, suppose that M converges to j < k. Let s ∈ L \ L(Ĝj ). Thus, there must be an+n ∈ N such that s ∈ t+
n . Consequently, after having seen at least tn , the machine M
cannot output j.
Summarizing, we obtain that M converges to k. It remains to show that M works
strong–monotonically. Suppose, M outputs y and changes its mind to z in some subsequent step. By construction we have: T̂y ⊆ t+n ⊆ L(Ĝy ), for some n ∈ N , and+T̂z ⊆ t+
⊆
T̂
,
for
some
r
>
0.
But
now,
T̂
⊆
t
z
y
n+r ⊆ L(Ĝz ), and again we conclude
n+r¿from property (3) that L(Ĝy ) ⊆ L(Ĝz ). Hence, M indeed works strong–monotonicallyon t.
q.e.d.
The characterization theorem of SM ON − T XT has the following interesting consequence. If L ∈ SM ON − T XT , then set inclusion in L is decidable (if one chooses an
14

appropriate description of L). On the other hand, Jantke (1991B) proved that, if set
inclusion of pattern languages is decidable, then the family of all pattern languages may
be inferred strong–monotonically from positive data. However, it remained open whether
the converse is also true. Using our result, we see it is, i.e., if one can design an algorithm
that learns the family of all pattern languages strong–monotonically from positive data,then set inclusion of pattern languages is decidable. This may show at least a promising way to solve the open problem whether or not set inclusion of pattern languages isdecidable.

3.3. The Characterization of Dual Strong–Monotonic Inference
In this subsection, we present the characterization of SM ON d − T XT and postponethat one for M ON − T XT for a moment, since it deserves special attention. Since
SM ON d − T XT = SM ON & − T XT = F IN − T XT , it suffices to characterize F IN −T XT in order to obtain the intended characterization of dual strong–monotonic inference
as well as of SM ON & − T XT . Note that a bit weaker theorem has been obtained
independently by Mukouchi (1991). The difference is caused by Mukouchi’s definition offinite identification from text, since there it is demanded that any indexed family L has
to be finitely inferred with respect to L itself. Consequently, one should ask whether or
not the latter requirement might lead to a decrease in the inferring power. It does not,as we shall see.
Our next characterization has some special features distinguishing it ¿from the characterizations already given. As pointed out above, dealing with characterizations has been
motivated by the aim to elaborate a unifying approach to monotonic inference. Concerning W M ON − T XT as well as SM ON − T XT this goal has been completely met byshowing that there is essentially one algorithm, i.e., that one described in the proof of
Theorem 1 and Theorem 2, respectively, which can perform the desired inference task,
if the space of hypotheses is appropriately chosen. The next theorem yields an evenstronger implication. Namely, it shows that, if there is a space of hypotheses at all suchthat L ∈ F IN −T XT with respect to this space, then one can always use L itself as spaceof hypotheses, thereby again applying essentially one and the same inference procedure.
Theorem 3. Let L be an indexed family of recursive languages. Then: L ∈ F IN −T XT if and only if there is a recursively generable family (Tj )j∈N of finite non–empty setssuch that(1) Tj ⊆ Lj for all j ∈ N .
(2) For all k, j ∈ N , if Tk ⊆ Lj , then Lj = Lk .
Proof. Necessity: Let L ∈ F IN − T XT . Then, there are a space G = (Gj )j∈N ofhypotheses and an IIM M such that M finitely infers L with respect to G. We proceed inshowing how to construct (Tj )j∈N . This is done in two steps. First, we construct (T̂j )j∈N
15

with respect to the space G of hypotheses. Then, we describe a procedure yielding thewanted family (Tj )j∈N with respect to L.
Let k ∈ N be arbitrarily fixed. Furthermore, let tk be the canonically ordered text ofL(Gk ). Since M infers L(Gk ) finitely on tk , there exists an x ∈ N such that M (tkx ) = m
with L(Gk ) = L(Gm ). We set T̂k = range(tkx ). The desired family (Tj )j∈N is obtained asfollows. Let z ∈ N . In order to get Tz search for the least j ∈ N such that T̂j ⊆ Lz . Set
Tz = T̂j . Note that at least one wanted j has to exist, since, for any set T̂k , there is a text
t of some language L ∈ L such that T̂k ⊆ t+ .
We have to show that (Tj )j∈N fulfils the announced properties. Due to our construction,
property (1) holds obviously. It remains to prove (2). Suppose z, y ∈ N such thatTz ⊆ Ly . In accordance with our construction, there is an index k such that Tz = T̂k .
Moreover, by construction, there is an initial segment of the canonically ordered text tk of
L(Gk ), say tkx , such that range(tkx ) = T̂k . Furthermore, M (tkx ) = m with L(Gk ) = L(Gm ).
Since T̂k ⊆ Ly , tkx forms an initial segment of some text for Ly . Taking into account that
M finitely infers Ly on any text and that M (ikx ) = m, we immediately obtain Ly = L(Gm ).
Finally, due to the definition of Tz , we additionally know that T̂k ⊆ Lz , hence the same
argument again applies and yields Lz = L(Gm ). Consequently, Lz = Ly . This proves (2).
Sufficiency: It suffices to prove that there is an IIM M inferring any L ∈ L finitely on
any text with respect to L. So let L ∈ L, let t be any text for L, and x ∈ N .
M (tx ) = “Generate Tj for j = 1, ..., x and test whether Tj ⊆ t+x ⊆ Lj .
In case there is at least a j fulfilling the test, output the minimal one and stop.
Otherwise, output nothing and request the next input.”
Since all of the Tj are uniformly recursively generable and finite we see that M is an
IIM. We have to show that it infers L. Let j = µn[L = Ln ]. Then, there must be anx ∈ N such that Tj ⊆ t+
x . That means, at least after having fed tx to M , the machine
M outputs a hypothesis and stops. Suppose M produces a hypothesis k with k 6= j andstops. Hence, there has to be a z with z < x such that Tk ⊆ t+
z . Since z < x, it follows
Tk ⊆ Lj . Thus, (2) implies Lk = Lj . Consequently, M outputs a correct hypothesis for L
and stops afterwards.
q.e.d.

3.4. The Characterization of Monotonic Inference
Next, we characterize M ON − T XT . As it turned out, characterizing M ON − T XT
is much more complicated. Intuitively this is caused by the following observations. One
has to construct a recursively generable family of finite tell–tales that should containboth information concerning the corresponding language as well as concerning possible
intersections of this language L with languages L0 which may be taken as candidate
16

hypotheses. However, these intersections may yield languages outside the indexed family.
Moreover, as long as the output of the IIM M performing the monotonic inference reallydepends on the range, the order and length of the segment of the text fed to M one has
to deal with a non–recursive component. The non–recursiveness directly results from therequirement that M has to infer each L ∈ L ¿from any text, i.e., one has to find suitableapproximations of the uncountable many non–recursive texts. Nevertheless, at first glance
there might be some hope. Osherson, Stob and Weinstein (1986) defined set–driven
as well as rearrangement–independent IIMs. An IIM M is set–driven (rearrangement–
independent) iff its output depends only on the range of its input (only on the range andlength of its input). However, set–driveness is a very restrictive requirement (cf. Osherson
et al. (1986), Fulk (1990)). On the other hand, Fulk (1990) proved that any IIM M may
be replaced by an IIM M 0 which is rearrangement–independent. Unfortunately, M 0 does
not preserve any of the types of monotonicity. Nevertheless, strong–monotonic inference
may always be performed by an IIM working rearrangement–independent as the proofof Theorem 2 shows. Surprisingly enough, the IIM described in the proof of Theorem 1
is not rearrangement–independent. But it possesses another favorable property, i.e., thehypothesis it converges to is the first correct one in the sequence of all created guesses.
IIMs fulfilling this property are said to work semantically finite. While the IIM describedin the demonstration of Theorem 2 does not necessarily work semantically finite, it may,
however, be replaced by an IIM M 0 that works strong–monotonically, rearrangement–
independent and semantically finite. In fact, M 0 works exactly as M does but it uses a
different space of hypotheses. A closer look at property (3) yields the following interesting
consequence. If L ∈ SM ON − T XT , then there is a recursive enumeration of L, i.e., that
one constructed in the proof, such that for any k, j ∈ N it is uniformly decidable whether
or not L(Ĝk ) ⊆ L(Ĝj ). Hence, equality of languages is uniformly decidable. Thus, one
may construct the wanted space of hypotheses containing each language of L exactly once.
On the other hand, it remained open whether the IIM presented in the proof of Theorem 1 may be replaced by an IIM that works semantically finite and rearrangement–
independent. We conjecture it cannot. So it seems that rearrangement–independence
gets lost somewhere in the hierarchy of monotonic inference. We conjecture that monotonic inference from positive data performed by rearrangement–independent IIMs is lesspowerful than ordinary monotonic learning from text. Summarizing the discussion above,in characterizing M ON − T XT we have to overcome the difficulties pointed out in adifferent way. Wiehagen (1992) proposed to construct for every language L and for every
text t of L a family of characteristic finite sets and obtained a characterization theorem
that is close to his characterization of monotonic inference of total recursive functions(cf. Wiehagen (1991)). However, conceptually it differs completely from the theorems
presented above.
What we now present is a characterization of M ON −T XT in terms of recursively generable finite sets as above. Additionally, we have been forced to define an easy computable
relation ≺ ⊆ N × N that can be used to distinguish appropriate chains of tell–tales withthe help of which an IIM M may compute its hypotheses. Now we are ready to present
17the wanted characterization.
Theorem 4. Let L be an indexed family of recursive languages. Then: L ∈ M ON −T XT if and only if there is a space of hypotheses Ĝ = (Ĝj )j∈N , a computable relation ≺over N , and a recursively generable family (T̂j )j∈N of finite and non–empty sets such that(1) range(L) = L(Ĝ).
(2) For all L ∈ L and all k ∈ N ,(i) T̂k ⊆ L(Ĝk ).
(ii) if T̂k ⊆ L, then L 6⊂ L(Ĝk ).
(3) For all L ∈ L and any k ∈ N , and all finite A ⊆ L, if T̂k ⊆ L, L(Ĝk ) 6= L, thenthere is a j such that k ≺ j, and A ⊂ T̂j ⊆ L(Ĝj ) = L.
(4) For all L ∈ L and all k, j ∈ N , if k ≺ j, T̂j ⊆ L, then L(Ĝk ) ∩ L ⊆ L(Ĝj ) ∩ L.
(5) For all L ∈ L, there is no infinite sequence (kj )j∈N such that for all j ∈ N , kj ≺ kj+1
S
and j T̂kj = L.
Proof. Necessity: We start by defining the relation ≺. For this purpose some additional
notation is needed. Let N ∗ be the set of all finite sequences over N , and for α ∈ N ∗ let|α| denote the length of α. Whenever appropriate, we interpret a number k as a bijective
encoding of a 4-tupel (n, α, β, γ), where n ∈ N, α, β, γ ∈ N ∗ . Let k, j ∈ N . Then k  jiff k = (n, α, β, γ), j = (m, αδ, βnτ, γκ), where |α| = |β| = |γ| as well as |δ| = |nτ | = |κ|.
Moreover, k ≈ j iff k = (n, α, β, γ), j = (m, αδ, βnτ, , γκ), where |α| = |β| = |γ| as wellas |δ| = |nτ | = |κ| and range(τ ) = {n}. Finally, k ≺ j iff k  j and not k ≈ j. Note that≺ is a transitive relation.
Let M be an IIM inferring L without loss of generality monotonically, conservatively
and consistently with respect to some space G = (Gj )j∈N of hypotheses (cf. Lange andZeugmann (1991)). Furthermore, for technical convenience, M initially always outputs 0,
where L0 = ∅. For all n ∈ N, α, β, γ ∈ N ∗ we define G̃(n,α,β,γ) = Gn , and set G0 = ∅.
Moreover, we define T̃(n,α,β,γ) as follows:(i) If not (|α| = |β| = |γ|), then T̃(n,α,β,γ) = ∅.
(ii) If (|α| = |β| = |γ|), β = β̂nρ, n 6∈ range(β̂), and range(ρ) 6= {n}, then T̃(n,α,β,γ) =∅.
(iii) Otherwise let α = y1 , ..., yr , β = 0, n1 , ..., nr−1 , γ = z1 , ..., zr and do the following:
Generate the canonical text σ̂n1 of L(Gn1 ) of length y1 and compute visible(σ̂n1 )= {τ | |τ | ≤ |σ̂n1 |, range(τ ) ⊆ range(σn1 )}. If |visible(σ̂n1 )| < z1 , thenT̃(n,α,β,γ) = ∅. Else test whether the z1 st element σn1 (with respect to the18lexicographical ordering) of visible(σ̂n1 ) when fed successively to M exactly
yields the sequence 0, n1 of hypotheses. If not, then T̃(n,α,β,γ) = ∅, and stop.
In case it does, generate the canonical text σ̂n2 of L(Gn2 ) of length y1 + y2 .
Compute visible(σ̂n2 ), and test whether |visible(σ̂n2 )| < z2 . In case it is, setT̃(n,α,β,γ) = ∅ and stop. For if not, test whether the z2 nd element of σn2 (withrespect to the lexicographical ordering) of visible(σ̂n2 ) does fulfil the following
properties:(a) σn1 is a prefix of σn2 , and(b) When fed successively with σn2 , the machine M exactly produces the sequence 0, n1 , n2 of guesses.
In case it does not, set T̃(n,α,β,γ) = ∅ and stop. Otherwise continue analogously.
Finally, if T̃(n,α,β,γ) has not been defined til now, generate the canonical text σ̂nof L(Gn ) of length y1 + ... + yr and compute visible(σ̂n ). If |visible(σ̂n )| < zr ,then set T̃(n,α,β,γ) = ∅. Else let σn be the zr th element of visible(σ̂n ) withrespect to the lexicographical ordering. Test whether(a) σnr−1 is a prefix of σn(b) When fed successively with σn , the machine M exactly produces the sequence 0, n1 , n2 , ..., nr−1 , n of guesses.
In case the test is not completely fulfilled set T̃(n,α,β,γ) = ∅. Otherwise, setT̃(n,α,β,γ) = range(σn ).
Obviously, T̃(n,α,β,γ) is uniformly recursively generable and finite. The families (T̂j )j∈N as
well as Ĝ = (Ĝj )j∈N are again obtained by simply striking off all T̃j that are empty as
well as the corresponding G̃j .
It remains to show that property (1) to (5) are satisfied. In order to prove (1), let
L ∈ L, and let n ∈ N be chosen such that M on L’s canonical text tL converges to n.
Furthermore, let y = µz[M (tLz ) = n]. We proceed in showing that there are α, β, γ ∈N ∗ such that T̃(n,α,β,γ) 6= ∅. The latter statement yields (1), since we may conclude
that L(Ĝ(n,α,β,γ) ) = L(Gn ) = L. We define β to be the sequence 0, n1 , n2 , ..., nr of M ’s
hypotheses when successively fed with tLy where the last element n is deleted.
Let σn1 < σn2 < ... < σnr < tLy be the corresponding initial segments of text on which
M produces its hypotheses (* < denotes prefix relation of finite sequences *). Since
M works consistently, we obtain σn+j ⊆ L(Gnj ) for j = 1, ..., r. Compute the canonicaltext tna11 , tna21 , ... of L(Gn1 ) of length ai = |σn1 | + i, i = 0, 1, ... until the least i with
σn1 ∈ visible(tnai1 ) has been found. Then let z1 be the lexicographical number of σn1 withrespect to visible(tnai1 ), and set y1 = ai . Next generate the canonical text tna12 , tna22 , ... ofL(Gn2 ) of length ai = |σn2 | + i until σn2 ∈ visible(tnai2 ) for the first time. Then define z2
to be the lexicographical number of σn2 with respect to visible(tnai2 ), and set y2 = ai − y1 ,a.s.o.
Finally, suppose y1 , ..., yr as well as z1 , ..., zr are already defined. Then we set yr+1 =max{y, y1 + ... + yr }. Define zr+1 to be lexicographical number of tLy with respect to19

visible(tLyr+1 ). Then, setting α = y1 , ..., yr+1 , β = 0, n1 , ..., nr and γ = z1 , ..., zr+1 directly
yields T̃(n,α,β,γ) 6= ∅. This proves part (1).
Assertion (i) of (2) follows directly from the construction described above. The second
part of property (2) is an immediate consequence of the conservativeness of M (cf. proofof Theorem 1).
The technique applied above to prove (1) applies mutatis mutandis to obtain (3).
Hence, we describe only the modification that has to be made. Let A ⊆ L and let
σ = s1 , ..., sm be the sequence of A’s strings written in lexicographical order. Moreover,let T̂k ⊆ L and L(Ĝk ) 6= L. Then there are n ∈ N, α, β, γ ∈ N ∗ with |α| = |β| = |γ| suchthat k = (n, α, β, γ). Furthermore, let α = y1 , ..., yr , β = 0, n1 , ..., nr−1 , γ = z1 , ..., zr , q =y1 + ... + yr , and let w1 , ..., wq be the uniquely determined sequence of all elements of T̂kon which, when fed successively to M , the machine M produces β as its sequence of
hypotheses. Since T̂k ⊆ L but L 6= L(Ĝk ) = L(Ĝ(n,α,β,γ) ), we conclude that M has not
yet converged on this particular initial segment w1 , ..., wq of some text for L. Next we
consider M ’s behavior when fed with w1 , ..., wq , σ. There are two cases to distinguish, i.e.,either the computation of M (w1 , ..., wq , σ) ends in M ’s request state, or it yields a guess.
However, in both cases we extend w1 , ..., wq , σ with a sufficiently long initial segment tLy
of L’s canonical text until M outputs a hypothesis that is correct for L. Finally, j is
obtained analogously as in the proof of property (1) where the construction is performed
with respect to w1 , ..., wq , σ, tLy instead of tLy . Obviously, k ≺ j, A ⊆ T̂j and L(Ĝj ) = L.
Hence (3) is proved.
We continue in proving property (4). Recall the definition of the relation ≺. Sincek ≺ j, in particular there are n, m ∈ N, α, β, γ, δ, τ, κ ∈ N ∗ such that k = (n, α, β, γ)and j = (m, αδ, βnτ, γκ). Due to the definition of T̂j , we obtain an initial segment
σ of text for L on which M , when successively fed with, sometime outputs n, and insome subsequent step m. Taking into account that M works monotonically we obtain
L(Gn ) ∩ L ⊆ L(Gm ) ∩ L. Finally, in accordance with our construction we know that
L(Ĝk ) = L(Ĝ(n,α,β,γ) ) = L(Gn ) and L(Ĝj ) = L(Ĝ(m,αδ,βnτ,γκ) ) = L(Gm ). Hence (4)follows. Furthermore, we directly see that T̂k ⊂ T̂j . The latter observation is used indemonstrating (5).
As above, if kj ≺ kj+1 , then there are n, m ∈ N, α, β, γ, δ, τ, κ ∈ N ∗ such that kj =(n, α, β, γ) and kj+1 = (m, αδ, βnτ, γκ). Moreover, since not kj ≈ kj+1 , we additionallyhave range(τ ) 6= {n}. Now suppose there is an infinite sequence (kj )j∈N such thatS
kj ≺ kj+1 and j T̂kj = L. Since T̂k ⊂ T̂j , we get in the limit a text t of L on which M
changes its mind infinitely often, a contradiction. Hence, (5) is proved.
Sufficiency: Again, it suffices to describe an IIM M that infers L with respect to Ĝ.
Let L ∈ L, let t be any text for L, and let x ∈ N . We define the desired IIM M as follows:
M (tx ) = “If x = 1 or M when fed successively with tx−1 does not produce any guess,then goto (A). Else goto (B).
(A) Search for the least j ≤ x for which T̂j ⊆ t+
x . In case it is found, output j and20request next input. Otherwise, output nothing and request next input.
(B) Let k be the hypothesis produced last by M on input tx−1 , and let yk be thecorresponding y used to find k , where yk = 0, if k is M ’s first guess.
(i) Test whether t+
x ⊆ L(Ĝk ).
In case it is, output k and request next input. Otherwise, goto (ii).
(ii) Search for the least j ≤ x satisfying k ≺ j, and there is a yj such that+yk < yj as well as t+yj ⊆ T̂j ⊆ tx . In case it is found, output j and request
next input. Otherwise, request next input and output nothing.”
Since all of the T̂j are uniformly recursively generable and finite and since ≺ is computable, we directly obtain that M is an IIM. We proceed in showing that M identifies
L monotonically on t.
Claim 1. If M converges, say to j, then L = L(Ĝj ).
First observe that T̂j ⊆ L, since otherwise j cannot be any of M ’s guesses. By (2),assertion (ii), we obtain that L 6⊂ L(Ĝj ). On the other hand, L \ L(Ĝj ) 6= ∅ would force
M to reject j (cf. (B), test (ii)). Hence, L = L(Ĝj ).
Claim 2. M works monotonically.
This is an immediate consequence of property (4) and the definition of M .
Claim 3. M converges on t.
In accordance with (2), assertion (i), one can show analogously as in the proof of
Theorem 2 that M outputs at least once a hypothesis. Moreover, as long as this guessis consistent with the data fed to M in subsequent steps, this guess is repeated. In caseM finds an inconsistency, property (3) ensures that M always outputs a new guess insome subsequent step. However, there might be competitive candidates that force M to
output a new guess before even touching the announced j. As long as this happens only
finitely often, M clearly converges, since a correct guess is never rejected. Now supposethat M changes its mind infinitely often. In accordance with M ’s definition then there
is an infinite sequence (kj )j∈N of all the guesses of M such that kj ≺ kj+1 for all j andS
j T̂kj = L. Hence property (5) is contradicted. This proves the theorem.
q.e.d3.5. The Characterization of Dual Monotonic Inference
In this section, we characterize dual monotonic language learning as well as M ON & −T XT . As it turned out, the proof technique developed above is powerful enough tocharacterize M ON d − T XT as well.
Theorem 5. Let L be an indexed family of recursive languages. Then: L ∈ M ON d −T XT if and only if there is a space of hyptheses Ĝ = (Ĝj )j∈N , a computable relation ≺over N , and a recursively generable family (T̂j )j∈N of finite and non–empty sets such that21

(1) range(L) = L(Ĝ).
(2) For all L ∈ L and all k ∈ N , T̂k ⊆ L(Ĝk ).
(3) For all L ∈ L , any k ∈ N , and all finite A ⊆ L, if T̂k ⊆ L, L(Ĝk ) 6= L, then there
is a j such that k ≺ j, and A ⊂ T̂j ⊆ L(Ĝj ) = L.
(4) For all L ∈ L and all k, j ∈ N , if k ≺ j, T̂j ⊆ L, then co − L(Ĝk ) ∩ co − L ⊆co − L(Ĝj ) ∩ co − L.
(5) For all L ∈ L, there is no infinite sequence (kj )j∈N such that for all j ∈ N , kj ≺ kj+1
S
and j T̂kj = L.
Proof. The necessity is mutatis mutandis proved analogously as in Theorem 4.
Sufficiency: The main problem we have to deal with is the detection and handling ofovergeneralized hypotheses. We proceed in defining an IIM M inferring L with respect
to Ĝ. Let L ∈ L, let t be any text for L, and let x ∈ N . The wanted IIM M is defined asfollows:
M (tx ) = “If x = 1 or M , when fed successively with tx−1 , does not produce any guess,then goto (A). Else goto (B).
(A) Search for the least j ≤ x for which T̂j ⊆ t+
x . In case it is found, output j andrequest next input. Otherwise, request next input.
(B) Let k be the hypothesis produced last by M on input tx−1 , and let yk be thecorresponding y used to find k , where yk = 0, if k is M ’s first guess.
(i) Execute the following tests:• Check whether t+
x ⊆ L(Ĝk ). In case it is not, goto (ii). Otherwise,
continue as follows.
• Check for all j ≤ x satisfying k ≺ j and there is a yj with yk < yj+
as well as t+yj ⊆ T̂j ⊆ tx whether or not there is a string s with|s| ≤ max{x, |s| | s ∈ t+x } fulfilling s ∈ L(Ĝk ) \ L(Ĝj ). In case at least
one j has been found, output the minimal one and request the next
input. Otherwise, output k and request next input.
(ii) Search for the least j ≤ x satisfying k ≺ j, and there is a yj such that+yk < yj as well as t+yj ⊆ T̂j ⊆ tx . In case it is found, output j and request
next input. Otherwise, request next input and output nothing.”
We have to show that M infers L dual strong–monotonically.
Claim 1. If M converges, say to z, then L = L(Ĝz ).
First observe that T̂z ⊆ L, since otherwise z cannot be any of M ’s guesses. Suppose,
L 6= L(Ĝz ). Then we have to distinguish the following two cases:
22

Case 1. L \ L(Ĝz ) 6= ∅.
Consequently, there is a string s ∈ L \ L(Ĝz ). Since t is a text for L, there has to be an x
such that s ∈ t+
x . Therefore M has to reject z in its consistency test in (i), a contradiction.
Case 2. L(Ĝz ) \ L 6= ∅.
Then we may assume L(Ĝz ) ⊃ L, since otherwise we are again in Case 1. Let yz be
the corresponding y used to find z. Since T̂z ⊆ L and L(Ĝz ) 6= L, we may set A := t+yz
and apply property (3). Hence, there has to be a j such that z ≺ j, A ⊂ T̂j ⊆ L andL(Ĝj ) = L. Therefore, there must be an x ≥ j such that the IIM M eventually finds a
string s satisfying s ∈ L(Ĝz ) \ L(Ĝj ) as well as |s| ≤ max{x, |s| | s ∈ t+x }. This event
would force M to change its mind from z to j, a contradiction. This proves Claim 1.
Claim 2. M works dual monotonically.
By construction, M changes its mind, say from k to j, only in case k ≺ j. Since it
additionally verifies T̂z ⊆ t+x ⊆ L, in accordance with property (4) we immediately obtainco − L(Ĝk ) ∩ co − L ⊆ co − L(Ĝj ) ∩ co − L. Hence, M works dual monotonically.
Claim 3. M converges on t.
In accordance with (2), one easily shows that M outputs a hypothesis at least once.
This guess is repeated as long as in (B) the tests in (i) are fulfilled. Moreover, if M ’s
last guess is rejected, it always outputs a new hypothesis in some subsequent step. Thisis obvious as long as M does not reject its last guess k by verifying t+
x 6⊆ L(Ĝk ). If M
detects an inconsistency, then property (3) ensures that M finds via (ii) a new hypothesis.
Consequently, the only remaining case we have to deal with is that M performs infinitely
many mind changes. Let (kj )j∈N be M ’s sequence of hypotheses produced when successively fed with t. However, by construction we obtain the following: kj ≺ kj+1 for allSj ∈ N and j T̂kj = L. The latter equality is true since t+
ykj ⊆ T̂kj and ykj < ykj+1 for all
kj . Hence, property (5) is contradicted. This proves the claim as well as the theorem.
q.e.d.
The proof of the sufficiency in Theorem 5 yields a new approach to handling overgeneralizations when learning from positive data. This technique may also be applied tocharacterize LIM − T XT .
Next we characterize M ON & − T XT . For that purpose, a new concept has to beelaborated which we now present. First, it is easy to argue that for any family in the class
M ON & − T XT there exists a learner that not only satisfies the required constraints but
also conservativeness and consistency (cf. Lange, Zeugmann and Kapur (1992)).
Theorem 6. Let L be an indexed family of recursive languages. Then: L ∈ M ON & −T XT if and only if there is a space of hypotheses Ĝ = (Ĝj )j∈N , a computable relation ≺over N , and a recursively generable family (T̂j )j∈N of finite and non–empty sets such that(1) range(L) = L(Ĝ).
(2) For all L ∈ L and all k ∈ N ,23

(i) T̂k ⊆ L(Ĝk ).
(ii) if T̂k ⊆ L, then L 6⊂ L(Ĝk ).
(3) For all k ∈ N , there is exactly one j (sometimes abbreviated as jk ) such that j ≺ k.
(4) For all L ∈ L and any k ∈ N , if T̂k ⊆ L, then there is a j 0 , jk ≺ j 0 , and L(Ĝj 0 ) = L.
(5) For all L ∈ L and any k, j ∈ N , if k ≺ j, T̂j ⊆ L, then(i) L(Ĝj ) \ L(Ĝk ) ⊆ L, and(ii) (L(Ĝk ) \ L(Ĝj )) ∩ L = ∅.
Proof. Necessity: Suppose first that an IIM M learns L while satisfying the monotonic
and the dual monotonic constraint as well as the consistency and conservativeness requirements with respect to some space G = (Gj )j∈N of hypotheses. We indicate how we candefine Ĝ = (Ĝj )j∈N , the relation ≺, and a recursively generable family (T̂j )j∈N of finite
and non–empty sets. The procedure works as follows: Let σ1 , σ2 , . . . be an enumerationof all finite sequences (possibly with repetition) of strings from Σ∗ . This enumeration isassumed to be in a canonical order so that all proper prefixes of a sequence appear before
the sequence itself. A function f that takes a sequence σ as its argument and returns anelement of N is used. We also need to keep track of sequences which have already been
dealt with. These are said to be marked. Initially, all sequences are unmarked. For any
r ≥ 1, in order to define T̂r , it first needs to define T̂j for all j < r. Suppose the procedure has already defined T̂j for all j < r. In order to define T̂r , a dovetailing technique
is invoked. By c : N × N → N , we denote Cantor’s pairing function. Also, first andsecond are the two inverse functions, so that first(c(x, y)) = x and second (c(x, y)) = y.
The procedure looks for the least number k such that σfirst(k) is an unmarked sequence
contained in the language Lsecond(k) ∈ L. It then marks this sequence and runs M on it. If+
M produces a hypothesis u when fed the entire sequence σfirst(k) , then it lets T̂r = σfirst(k)and Ĝr = Gu ; otherwise, it again looks for the first unmarked sequence as above. If M
has produced this guess for the first time on seeing the entire sequence σfirst(k) , it lets
f (σfirst(k) ) = r. If the sequence σi is the least prefix of σfirst(k) on which the machine
produced a guess, it lets f (σi ) ≺ r.
It is easy to see that the procedure outlined above is well-defined. Since the sequences
are assumed to be enumerated in a canonical order and proper dove-tailing is used, all
the prefixes of a sequence would be marked before the sequence itself is marked. Thus,
the function f would always be defined on a certain value prior to its use on that value.
Since the family is learned by M , there would be an infinite number of different sequences
which are contained in some language in the family and on which M makes a guess. Thus,
the procedure constructively defines T̂r and Ĝr for each r ≥ 1. We next argue that theproperties (1) through (5) are also satisfied.
Property (1) is trivial to establish since exactly whenever the machine M makes any
output u, there is some Ĝr defined equal to Gu . The second property is met since a24

conservative learner must always guess a least upper bound of the evidence. Furthermore,
property (3) is also satisfied because whenever a sequence σi leads to a definition of a T̂r ,by construction, there is a unique jr such that jr ≺ r.
Suppose there is some L ∈ L and a k ∈ N , such that T̂k ⊆ L. Then, by construction,
there must be a sequence σi such that σi+ = T̂k and Ĝk = GM (σi ) . Let t be a text for L
that has σi as a prefix. Clearly, at some point, the machine when run on t must guesssome j 0 so that L = L(Ĝj 0 ). Since jk = f (σk ), where σk is the least prefix of σi on which
M makes a guess, we immediately have jk ≺ j 0 . Thus, the fourth property is also satisfied.
Finally, we show that if, for any k, j ∈ N and L ∈ L, k ≺ j, T̂j ⊆ L, then(i) L(Ĝj ) \ L(Ĝk ) ⊆ L, and(ii) (L(Ĝk ) \ L(Ĝj )) ∩ L = ∅.
By construction, k ≺ j if and only if there is a sequence σi (σi+ = T̂j ) such that when M
is run on σi , the machine outputs a guess u as its first guess such that Gu = Ĝk . Further,on seeing the entire sequence σi , it outputs some v such that Gv = Ĝj . Let any language
L ∈ L be such that σi+ ⊆ L. Then, the sequence σi can be extended by any text t for L sothat the entire presentation is a text for L. Clearly, the machine M must converge to anindex for L on such a text. We claim that L(Ĝj ) \ L(Ĝk ) ⊆ L. Suppose the converse, i.e.,there is a string s such that s ∈ L(Ĝj ) \ L(Ĝk ) and s 6∈ L. Hence, s ∈ co − L ∩ co − L(Ĝk )but s 6∈ co − L ∩ co − L(Ĝj ). Therefore, co − L(Ĝk ) ∩ co − L 6⊆ co − L(Ĝj ) ∩ co − Land consequently, M does not work dual monotonically. Thus, (i) is proved. We proceed
in showing (ii). Suppose, there is a string s ∈ L(Ĝk ) \ L(Ĝj ) ∩ L. Then s ∈ L(Ĝk ) ∩ L
and s 6∈ L(Ĝj ). Therefore, s 6∈ L(Ĝj ) ∩ L. However, the latter statement contradicts themonotonicity requirement L(Ĝk ) ∩ L ⊆ L(Ĝj ) ∩ L. Hence, (ii) is proved.
Sufficiency: Suppose we are given a space of hypotheses Ĝ = (Ĝj )j∈N , a computable
relation ≺ and a recursively generable family (T̂j )j∈N . We construct an IIM M thatlearns L as follows: Let L ∈ L, let t be any text for L and let x ∈ N . M on input tx
behaves differently depending on whether or not it has made a guess prior to this stage.
• If M has not produced a guess up to this stage, then scan the enumeration of (T̂j )j∈N
for the least k ≤ x such that T̂k ⊆ t+x ⊆ L(Ĝk ). If such a k is found, then find jk(the only j such that j ≺ k) and let FIRST = jk , output k, and request the next
input. Otherwise, do not output a guess, and request the next input.
• If M has produced a guess previous to this stage, maintain the previous guess if it isconsistent with t+
x . Otherwise, scan the enumeration of (T̂j )j∈N for the least k ≤ nsuch that jk = FIRST and T̂k ⊆ t+x ⊆ L(Ĝk ). If such a k is found, then output it
as the guess, and request the next input. Otherwise, output nothing, and request
the next input.

25

We first argue that M learns L. Let L ∈ L and let t = t1 , t2 , . . . be a text for L. The
machine M , when run on t, must make a non-zero guess since, by property (1), there
must be a least k such that L = L(Ĝk ) and, at some stage x ≥ k, the text must include
the finite set T̂k . Since the machine is conservative and consistent (by property (ii) of(2) and by construction) it never produces an overgeneralization of the language to belearnt. Moreover, a correct guess is never rejected. Hence, the only way the machine
could fail to converge to an index for L is by guessing an infinite number of guesses
all different from L. By property (4), there must be a least j ∗ such that FIRST ≺j ∗ and L = L(Ĝj ∗ ). Consider a stage at which all of T̂j ∗ has been witnessed in theevidence. Suppose, at some subsequent stage, the machine changes its guess to j. We
claim that L(Ĝj ) = L(Ĝj ∗ ). Clearly, (T̂j ∪ T̂j ∗ ) ⊆ (L(Ĝj )∩L(Ĝj ∗ )). Since FIRST ≺ j ∗ , byproperty (5), we have L(Ĝj ∗ ) \ L(ĜFIRST ) ⊆ L(Ĝj ). Likewise, since FIRST ≺ j, we haveL(Ĝj )\L(ĜFIRST ) ⊆ L(Ĝj ∗ ). For the same reason, we have (L(ĜFIRST )\L(Ĝj ∗ ))∩L(Ĝj ) =∅ and (L(ĜFIRST )\L(Ĝj ))∩L(Ĝj ∗ )) = ∅. Thus, L(Ĝj ) = L(Ĝj ∗ ). Since M is conservative,
we conclude that M converges to an index for L on t.
Suppose on a text t for a language L, the machine makes the guesses
i, . . . , u, . . . , v, . . . , j, and it is the case that the machine exhibits a violation of monotonicity or dual monotonicity while proceeding from the guess u to v. Therefore,(c.1) L(Ĝv ) \ L(Ĝu ) 6⊆ L (violation of dual monotonicity), or(c.2) (L(Ĝu \ L(Ĝv )) ∩ L 6= ∅ (violation of monotonicity).
¿From the construction of M , we can infer that, for FIRST = ji , both FIRST ≺ u
and FIRST ≺ v, where T̂u ⊆ L(Ĝv ) and T̂u ∪ T̂v ⊆ L. Since FIRST ≺ u as well asT̂u ⊆ L(Ĝv ), and L(Ĝv ) ∈ L, due to property (5), we have(d.1) L(Ĝu ) \ L(ĜFIRST ) ⊆ L(Ĝv ) and(d.2) (L(ĜFIRST ) \ L(Ĝu )) ∩ L(Ĝv ) = ∅.
Similarly, since FIRST ≺ v, due to property (5), we have(e.1) L(Ĝv ) \ L(ĜFIRST ) ⊆ L and(e.2) (L(ĜFIRST ) \ L(Ĝv )) ∩ L = ∅.
Suppose (c.1) is true, i.e., there is some string x ∈ L(Ĝv ) which is neither in L(Ĝu )nor L. By (e.1), we can conclude that x ∈ L(ĜFIRST ). But this is inconsistent with (d.2).
Suppose, on the other hand, that (c.2) is true. Therefore, there is some string x in L(Ĝu )which is also in L but not in L(Ĝv ). By (e.2), we can conclude that x 6∈ L(ĜFIRST ).
But this is inconsistent with (d.1). This contradicts our assumption that M violatesmonotonicity or dual monotonicity.
q.e.d.
26

Note that the above characterizations could be generalized to all types of monotonic
learning and finite inference on informant. This is done in Lange and Zeugmann (1992B).

4. Conclusions and Open Problems
Different notions of monotonicity and of dual monotonicity have been defined andalmost all resulting modes of inference from positive data have been characterized in termsof finitely generable tell–tale sets. In particular, the characterization of W M ON − T XT
solved the long standing open problem of how to characterize inference algorithms thatavoid overgeneralization. Moreover, in characterizing dual monotonic inference ¿fromtext, we developed a new method to detect and to deal with overgeneralizations. This
technique can also be applied to obtain a new characterization of language learning in thelimit from positive data. However, the characterization of dual weak–monotonic inference
remains open.
All these characterization theorems lead to a deeper insight into the problem what
actually may be inferred monotonically. Moreover, we obtained a unifying approach tomonotonic language learning in describing general algorithms that perform any monotonic
inference task. Furthermore, the characterization theorems may eventually be applied tosolve problems that could not be solved using other approaches. In order to have an
example, let us recall what we have derived from Theorem 2, i.e., if L ∈ SM ON − T XT ,then set inclusion in L is decidable (if one chooses an appropriate description of L).
On the other hand, Jantke (1991B) proved that, if set inclusion of pattern languages isdecidable, then the family of all pattern languages may be inferred strong–monotonicallyfrom positive data. However, it remained open whether the converse is also true. Using
our result, we see it is, i.e., if one can design an algorithm that learns the family of all
pattern languages strong–monotonically from positive data, then set inclusion of patternlanguages is decidable. Nevertheless, while the decidability of set inclusion of languages
is necessary for SM ON − T XT identification, in general it is not sufficient. In Lange andZeugmann (1991) we have shown that there is an indexed family of recursive languages
such that set inclusion is uniformly decidable but which is not monotonically inferable,
even on informant.
However, several problems remained open. One of the most intriguing questions iswhether or not all types of monotonic and of dual monotonic inference from positive data
may be performed by IIMs that are rearrangement–independent, or even set–driven. For
strong–monotonic inference, this question has been partially answered via the characterization theorem. Unfortunately, for weak–monotonic, monotonic and dual monotonic
language learning, this approach did not succeed. Nevertheless, we were able to characterize rearrangement–independent monotonic inference from positive data (denoted by
M ON R − T XT ) as follows:
Theorem Let L be an indexed family of recursive languages. Then: L ∈ M ON R −T XT if and only if there are a space of hypotheses Ĝ = (Ĝj )j∈N and a recursively generable

27

family (T̂j )j∈N of finite sets such that(1) range(L) = L(Ĝ)(2) For all j ∈ N , T̂j ⊆ L(Ĝj ).
(3) For all j, z ∈ N , if T̂j ⊆ L(Ĝz ), then L(Ĝz ) 6⊂ L(Ĝj ).
(4) For all k, j ∈ N , and for all L ∈ L, if L(Ĝj ) 6= L 6= L(Ĝk ) and T̂k ⊆ L(Ĝj ) ∩ L as
well as T̂j ⊆ L, then L(Ĝk ) ∩ L ⊆ L(Ĝj ) ∩ L.
Obviously, we have M ON R − T XT ⊆ M ON − T XT . Therefore, clarifying whether
the inclusion is proper either yields a simplified characterization of M ON − T XT or it
adds some evidence that Theorem 4 cannot be considerably improved. Note that it is not
hard to show that SM ON − T XT ⊂ M ON R − T XT (cf. Lange and Zeugmann (1991)).
Next, we point out another interesting aspect of Angluin’s (1980) as well as of ourcharacterizations. Freivalds, Kinber and Wiehagen (1989) introduced inference from good
examples, i.e., instead of successively inputting the whole graph of a function now an IIM
obtains only a finite set of pairs (argument,value) containing at least the good examples.
Then, it finitely infers a function iff it outputs a single correct hypothesis. Surprisingly,
finite inference of recursive functions from good examples is exactly as powerful as identification in the limit. The same approach may be undertaken in language learning (cf.
Lange and Wiehagen (1991)). Now it is not hard to prove that any indexed family L canbe finitely inferred from good examples, where for each L ∈ L any superset of any of L’s
tell–tales may serve as good example.
Furthermore, as our results show, all types of monotonic language learning have special
features distinguishing them from monotonic inference of recursive functions. Therefore,
it would be very interesting to study monotonic language learning in the general case,i.e., not restricted to indexed families.
Acknowledgement
The first two authors gratefully acknowledge many enlightening discussions with Rolf
Wiehagen concerning the characterization of learning algorithms.

5. References
Angluin, D. (1980), Inductive Inference of Formal Languages from Positive Data,
Information and Control 45, 117 - 135.
Angluin, D., and Smith, C.H. (1983), Inductive Inference: Theory and Methods,
Computing Surveys 15, 237 - 269.
Angluin, D., and Smith, C.H. (1987), Formal Inductive Inference, in “Encyclopediaof Artificial Intelligence” (St.C. Shapiro, Ed.), Vol. 1, pp. 409 - 418, WileyInterscience Publication, New York.
28

Barzdin, Ya.M. (1974), Inductive Inference of Automata, Functions and Programs,in “Proceedings International Congress of Math.,” Vancouver, pp. 455 - 460.
Blum, L., and Blum, M. (1975), Toward a Mathematical Theory of Inductive
Inference, Information and Control 28, 122 - 155.
Bucher, W., and Maurer, H. (1984), “Theoretische Grundlagen der Programmiersprachen, Automaten und Sprachen,” Bibliographisches Institut AG, Wissenschaftsverlag, Zürich.
Case, J. (1988), The Power of Vacillation, in “Proceedings 1st Workshop on Computational Learning Theory,” (D. Haussler and L. Pitt, Eds.), pp. 196 -205, Morgan
Kaufmann Publishers Inc.
Case, J., and Lynes, C. (1982), Machine Inductive Inference and Language Identification, in “Proceedings Automata, Languages and Programming, Ninth Colloquim,
Aarhus, Denmark,” (M. Nielsen and E.M. Schmidt, Eds.), Lecture Notes in Computer Science Vol. 140, pp. 107 - 115, Springer-Verlag, Berlin.
Freivalds, R., Kinber, E.B., and Wiehagen, R. (1989), Inductive Inference
from Good Examples, in “Proceedings International Workshop on Analogical andInductive Inference, October 1989, Reinhardsbrunn Castle,” (K.P. Jantke ,Ed.),
Lecture Notes in Artificial Intelligence Vol. 397, pp.1 - 17, Springer-Verlag, Berlin.
Freivalds, R., Kinber, E.B., and Wiehagen, R. (1992), Convergently versus
Divergently Incorrect Hypotheses in Inductive Inference, GOSLER Report 02/92,
January 1992, Fachbereich Mathematik und Informatik, TH Leipzig.
Fulk, M.(1990), Prudence and other Restrictions in Formal Language Learning, Information and Computation 85, 1 - 11.
Gold, M.E. (1967), Language Identification in the Limit, Information and Control
10, 447 - 474.
Jain, S., and Sharma, A. (1989), Recursion Theoretic Characterizations of Language Learning, The University of Rochester, Dept. of Computer Science, TR 281.
Jantke, K.P. (1991A), Monotonic and Non–monotonic Inductive Inference, New Generation Computing 8, 349 - 360.
Jantke, K.P. (1991B), Monotonic and Non–monotonic Inductive Inference of Functions and Patterns, in “Proceedings First International Workshop on Nonmonotonic and Inductive Logics, December 1990, Karlsruhe,” (J. Dix , K.P. Jantke and
P.H. Schmitt, Eds.), Lecture Notes in Artificial Intelligence Vol. 543, pp. 161 177, Springer-Verlag, Berlin.

29

Kapur, S. (1992B), Monotonic Language Learning, in ”Proceedings of the Workshop
on Algorithmic Learning Theory,” JSAI.
Kapur, S., and Bilardi, G. (1992), Language Learning without Overgeneralzation, in “Proceedings 9th Annual Symposuim on Theoretical Aspects of Computer
Science, Cachan, France, February 13 - 15,” (A. Finkel and M. Jantzen, Eds.),
Lecture Notes in Computer Science Vol. 577, pp. 245 - 256, Springer-Verlag, Berlin.
Lange, S., and Wiehagen, R. (1991), Polynomial–Time Inference of Arbitrary
Pattern Languages, New Generation Computing 8, 361 - 370.
Lange, S., and Zeugmann, T. (1991), Monotonic versus Non-monotonic Language
Learning, in “Proceedings 2nd International Workshop on Nonmonotonic and Inductive Logic, December 1991, Reinhardsbrunn,” to appear in Lecture Notes in
Artificial Intelligence, Springer-Verlag, Berlin.
Lange, S., and Zeugmann, T. (1992A), On the Power of Monotonic Language
Learning, GOSLER–Report 05/92, February 1992, Fachbereich Mathematik undInformatik, TH Leipzig.
Lange, S., and Zeugmann, T. (1992B), Characterization of Language Learning on
Informant under Various Monotonicity Constraints, Journal of Experimental andTheoretical Artificial Intelligence, to appaer.
Lange, S., and Zeugmann, T. (1992C), Learning Recursive Languages with Bounded Mind Changes, GOSLER–Report 16/92, FB Mathematik und Informatik, TH
Leipzig.
Lange, S.,Zeugmann, T., and Kapur, S (1992), Class Preserving Monotonic
Language Learning, submitted to Theoretical Computer Science, and GOSLER–
Report 14/92, FB Mathematik und Informatik, TH Leipzig.
Mukouchi, Y. (1991), Definite Inductive Inference as a Successful Identification Criterion, Research Institute of Fundamental Information Science, Kyushu University
33, Fukuoka, December 24, ’91 RIFIS-TR-CS-52.
Osherson, D., Stob, M., and Weinstein, S. (1986), “Systems that Learn,
An Introduction to Learning Theory for Cognitive and Computer Scientists,” MITPress, Cambridge, Massachusetts.
Porat, S., and Feldman, J.A. (1988), Learning Automata from Ordered Examples,in “Proceedings First Workshop on Computational Learning Theory,” (D. Haussler
and L. Pitt, Eds.), pp. 386 - 396, Morgan Kaufmann Publishers Inc.
Solomonoff, R. (1964), A Formal Theory of Inductive Inference, Information andControl 7, 1 - 22, 234 - 254.

30

Trakhtenbrot, B.A., and Barzdin, Ya.M. (1970) “Konetschnyje Awtomaty (Powedenie i Sintez),” Nauka, Moskwa, (in Russian)english translation: “Finite Automata–Behavior and Synthesis, Fundamental Studies in Computer Science 1,” North–Holland, Amsterdam, 1973.
Wiehagen, R. (1976), Limes–Erkennung rekursiver Funktionen durch spezielle Strategien, Journal Information Processing and Cybernetics (EIK) 12, 93 - 99.
Wiehagen, R. (1977), Identification of Formal Languages, in “Proceedings Mathematical Foundations of Computer Science, Tatranska Lomnica,” (J. Gruska, Ed.),
Lecture Notes in Computer Science Vol. 53, pp. 571 - 579, Springer-Verlag, Berlin.
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 Artificial
Intelligence Vol. 543, pp. 184 - 207, Springer-Verlag, Berlin.
Wiehagen, R. (1992), Personal Communication
Wiehagen, R., and Liepe, W. (1976), Charakteristische Eigenschaften von erkennbaren Klassen rekursiver Funktionen, Journal of Information Processing and Cybernetics (EIK) 12, 421 - 438.
Zeugmann, T. (1983), A–posteriori Characterizations in Inductive Inference of Recursive Functions, Journal of Information Processing and Cybernetics (EIK) 19, 559 594.

31