TCS -TR-A-12-55

TCS Technical Report

On the Amount of Nonconstructivity in Learning
Formal Languages from Text
bySanjay Jain, Frank Stephan, and Thomas Zeugmann

Division of Computer Science
Report Series A
March 12, 2012

Hokkaido University
Graduate School ofInformation Science and Technology

Email: thomas@ist.hokudai.ac.jp

Phone: +81-011-706-7684
Fax:+81-011-706-7684

On the Amount of Nonconstructivity in Learning
Formal Languages from Text
Sanjay Jain

Frank Stephan

Department of Computer Science

Department of Computer Science andNational University of Singapore

Department of Mathematics

Singapore 117417

National University of Singapore

Republic of Singapore

Singapore 117417

sanjay@comp.nus.edu.sg

fstephan@comp.nus.edu.sg

Thomas Zeugmann
Division of Computer Science
Hokkaido University
N-14, W-9, Sapporo 060-0814, Japanthomas@ist.hokudai.ac.jp

Abstract
Nonconstructive computations by various types of machines and automata
have been considered by e.g., Karp and Lipton [17] and Freivalds [9, 10]. They
allow to regard more complicated algorithms from the viewpoint of much moreprimitive computational devices. The amount of nonconstructivity is a quantitative characterization of the distance between types of computational devices
with respect to solving a specic problem.
This paper studies the amount of nonconstructivity needed to learn classesof formal languages. Dierent learning types are compared with respect tothe amount of nonconstructivity needed to learn indexable classes and recursively enumerable classes, respectively, of formal languages from positive data.
Matching upper and lower bounds for the amount of nonconstructivity needed
are shown.

1. Introduction

The research subject studied in this paper derives its motivation from various
sources which we shortly present below. Nonconstructive methods of proof in mathematics have a rather long and dramatic history. The debate was especially passionate
when mathematicians tried to overcome the crisis concerning the foundations of mathematics.
1

2

Sanjay Jain, Frank Stephan, and Thomas Zeugmann

The situation changed slightly in the forties of the last century, when nonconstructive methods found their way to discrete mathematics. In particular, Paul Erd®s usednonconstructive proofs masterly, beginning with the paper [8].
Another inuential paper was Barzdin² [3], who introduced the notion of advice
in the setting of Kolmogorov complexity of recursively enumerable sets. Karp and
Lipton [17] introduced the notion of a Turing machine that takes advice to understandunder what circumstances nonuniform upper bounds can be used to obtain uniform
upper bounds. Damm and Holzer [7] adapted the notion of advice for nite automata.
Later Cook and Kraji£ek [6] initiated the study of proof systems that use advice forthe verication of proofs. Even more recently, Beyersdor et al. [4] continued along
this line of research.
Quite often, we experience that nding a proof for a new deep theorem is triggeredby a certain amount of inspiration. Being inspired does not mean that we do not haveto work hard in order to complete the proof and to elaborate all the technical details.
However, this work is quite dierent from enumerating all possible proofs until wehave found the one sought for. Also, as experience shows, the more complicated theproof, the higher is the amount of inspiration needed. These observations motivatedFreivalds [9, 10] to introduce a qualitative approach to measure the amount of nonconstructivity (or advice) in a proof. Analyzing three examples of nonconstructive
proofs led him to a notion of nonconstructive computation which can be used formany types of automata and machines and which essentially coincides with Karp and
Lipton's [17] notion when applied to Turing machines.
As outlined by Freivalds [9, 10], there are several results in the theory of inductive
inference of recursive functions which suggest that the notion of nonconstructivity
may be worth a deeper study in this setting, too. Subsequently, Freivalds and Zeugmann [11] introduced a model to study the amount of nonconstructivity needed tolearn recursive functions.
In the present paper we generalize the model of Freivalds and Zeugmann [11]to the inductive inference of formal languages. That is, we aim to characterize thediculty to learn classes of formal languages from positive data by using the amount of
nonconstructivity needed to learn these classes. We shortly describe this model. The
learner receives, as usual, growing initial segments of a text for the target language L,
where a text is any innite sequence of strings and a special pause symbol # such thatthe range of the text minus the pause symbol contains all elements of L and nothingelse. In addition, the learner receives as a second input a bitstring of nite length which
we call help-word. If the help-word is correct, the learner learns in the desired sense.
Since there are innitely many languages to learn, a parameterization is necessary, i.e.,
we allow for every n a possibly dierent help-word and we require the learner to learn
every language contained in {L0 , . . . , Ln } with respect to the hypothesis space (Li )i∈N
chosen (cf. Denition 6). The diculty of the learning problem is then measured by
the length of the help-words needed, i.e., in terms of the growth rate of the function dbounding this length. As in previous approaches, the help-word does not just provideOn the Amount of Nonconstructivity in Learning Formal Languages from Text

3

an answer to the learning problem. There is still much work to be done by the learner.
First, we consider the learnability of indexable classes in the limit from positive
data and ask for the amount of nonconstructivity needed to learn them. This is quite
a natural choice, since even simple indexable subclasses of the class of all regular languages are known not to be inferable in the limit from positive data (cf. [13, 15, 22]).
Second we investigate the amount of nonconstructivity needed to infer recursively
enumerable classes of recursively enumerable languages. Moreover, several variationsof Gold's [13] model of learning in the limit have been considered (cf., e.g., [15, 20]
and the references therein). Thus, it is only natural to consider some of these variations, too. In particular, we shall study conservative learning and strong-monotonic
inference.
We then prove upper and lower bounds for the amount of nonconstructivity inlearning classes of formal languages from positive data. The usefulness of this approach is nicely reected by our results which show that the function d may considerably vary. In particular, the function d may be arbitrarily slow growing for learningindexable classes in the limit from positive data (cf. Theorem 1), while we have an
upper bound of log n and a lower bound of log n − 2 for conservative learning of indexable classes from positive data (cf. Theorems 2 and 3). Furthermore, we have a
2 log n upper bound and a 2 log n − 4 lower bound for strong-monotonic inference ofindexable classes from positive data (cf. Theorems 4 and 5).
Moreover, the situation changes considerably when looking at recursively enumerable classes of recursively enumerable languages. For learning in the limit from positive
data we have an upper bound of log n and a lower bound of log n − 2, while for conservative learning even any limiting recursive bound on the growth of the function d
is not sucient to learn all recursively enumerable classes of recursively enumerable
languages from positive data (cf. Theorems 7, 8 and 9).
2. Preliminaries

Any unspecied notations follow Rogers [21]. In addition to or in contrast with
Rogers [21] we use the following. By N = {0, 1, 2, . . . } we denote the set of all natural
numbers, and we set N+ = N \ {0}.
The cardinality of a set S is denoted by |S|. We write ℘(S) for the power set
of set S . Let ∅, ∈, ⊂, ⊆, ⊃, and ⊇ denote the empty set, element of, proper
subset, subset, proper superset, and superset, respectively. Let S1 , S2 be any sets;then we write S1 4 S2 to denote the symmetric dierence of S1 and S2 , i.e., S1 4 S2 =(S1 \ S2 ) ∪ (S2 \ S1 ). By max S and min S we denote the maximum and minimum ofa set S , respectively, where, by convention, max ∅ = 0 and min ∅ = ∞.
We use T to denote the set of all total functions of one variable over N. Letn ∈ N+ ; then the set of all partial recursive functions and of all recursive functions of
one and n variables over N is denoted by P, R, P n , Rn , respectively. Furthermore,4

Sanjay Jain, Frank Stephan, and Thomas Zeugmann

let f ∈ P , then we use dom(f ) to denote the domain of the function f , that is,dom(f ) = {x | x ∈ N, f (x) is dened}. By range(f ) we denote the range of f , i.e.,
range(f ) = {f (x) | x ∈ dom(f )}.
It is technically most convenient to dene recursively enumerable families of recursively enumerable languages as follows. Any ψ ∈ P 2 is called a numbering. Letψ ∈ P 2 , then we write ψi instead of λx.ψ(i, x). Furthermore, we set Wiψ = dom(ψi )and refer to it as the ith enumerated language. Clearly, the sets Wiψ ⊆ N are recursively enumerable.
A numbering ϕ ∈ P 2 is called a Gödel numbering for P (cf. Rogers [21]) if Pϕ = P ,and for every numbering ψ ∈ P 2 , there is a compiler c ∈ R such that ψi = ϕc(i) for
all i ∈ N. If ϕ ∈ P 2 is any arbitrarily xed Gödel numbering then we also use Wi asa shorthand for Wiϕ .
A function f ∈ P is said to be strictly monotonic provided for all x, y ∈ N withx < y we have, if both f (x) and f (y) are dened then f (x) < f (y). By Rmon wedenote the set of all strictly monotonic recursive functions.
Let Σ be any xed nite alphabet, and let Σ∗ be the free monoid over Σ. Any
L ⊆ Σ∗ is a language. Furthermore, we x a symbol # such that # ∈/ Σ. We denotethe empty string by λ and use |w| to denote the length of any string w ∈ Σ∗ . By REG
we denote the class of all regular languages (cf., e.g., [23]). Furthermore, we use C or
L to denote any (innite) class and family of languages, respectively.

Denition 1 (Gold [13]). Let L be any language. Every total function t : N → Σ∗ ∪{#} with {t(j) | j ∈ N} \ {#} = L is called a text for L.
Note that the symbol # denotes pauses in the presentation of data. Furthermore,
there is no requirement concerning the computability of a text. So, any order andany number of repetitions is allowed. For any n ∈ N we use t[n] to denote the initial
segment (t(0), . . . , t(n)). Additionally we use content (t[n]) =df {t(0), . . . , t(n)} \ {#}and content (t) =df {t(j) | j ∈ N} \ {#} to denote the content of an initial segment
and of a text, respectively.
An algorithmic learner M nds a rule (grammar) from growing initial segments ofa text. On each initial segment the learner M has to output a hypothesis which is anatural number, i.e., M (t[n]) ∈ N. Then the sequence (M (t[n]))n∈N has to converge(to some representation of the input), i.e., there is a j ∈ N such that M (t[n]) = j forall but nitely many n ∈ N.
So, we still have to specify the semantics of the numbers output by M . In orderto do so, we need the following.

Denition 2 (Angluin [2]). A family (Lj )j∈N of languages is said to be uniformly
recursive if there exists a recursive function f : N × Σ∗ → {0, 1} such that Lj = {w |w ∈ Σ∗ , f (j, w) = 1} for all j ∈ N. We refer to f as a decision function.

On the Amount of Nonconstructivity in Learning Formal Languages from Text

5Denition 3. A class C of non-empty recursive languages is said to be indexable if
there is a family (Lj )j∈N of uniformly recursive languages such that C = {Lj | j ∈ N}.
Such a family is said to be an indexing of C .
By ID we denote the collection of all indexable classes.
Note that REG is an indexable class. Also, the class of all context-free languages
and the class of all context-sensitive languages form an indexable class. Further
information concerning indexable classes and their learnability can be found in [20, 22].
So, when dealing with the learnability of indexable classes, it is only natural tointerpret the hypotheses output by M with respect to a chosen indexing of a classcontaining the target class C (cf. Denition 4 below). On the other hand, when
considering recursively enumerable classes C of recursively enumerable languages thenwe always take as hypothesis space the family (Wiψ )i∈N , where ψ ∈ P 2 is the numberingdening the class C .

Denition 4. Let C be an indexable class. A family H = (Lj )j∈N is said to be anindexed hypothesis space for C if (Lj )j∈N is uniformly recursive and C ⊆ {Lj | j ∈ N}.
Following Lange and Zeugmann [19], if C = {Lj | j ∈ N} then we call H classpreserving and if C ⊆ {Lj | j ∈ N} then the hypothesis space H is said to be classcomprising.
Now we are ready to provide the formal denition of learning in the limit fromtext. Following Gold [13] we call our learners inductive inference machines (abbr.
IIM). To unify notations, in the denitions below we use H = (hj )j∈N to denote ourhypothesis spaces, where we assume the interpretation given above.

Denition 5 (Gold [13]). Let C be any class of languages, let H = (hj )j∈N be ahypothesis space for C , and let L ∈ C . An IIM M is said to learn L in the limit fromtext with respect to H if
(1) for every text t for L there is a j ∈ N such that the sequence (M (t[n]))n∈N
converges to j , and(2) L = hj .

An IIM M learns C in the limit from text with respect to H if M learns all L ∈ C in
the limit from text with respect to H.
The collection of all classes C for which there is an IIM M and a hypothesis space H
such that M learns C in the limit from text with respect to H is denoted by LimTxt.
Since, by the denition of convergence, only nitely many data of L were seenby the IIM upto the (unknown) point of convergence, whenever an IIM learns thepossibly innite language L, indeed some form of learning must have taken place. For
this reason, hereinafter the terms learn, infer, and identify are used interchangeably.

6

Sanjay Jain, Frank Stephan, and Thomas Zeugmann

In the following modications of Denition 5 additional requirements are made. An
IIM M is said to be consistent if for all relevant texts t and all n ∈ N the condition
content (t[n]) ⊆ hM (t[n]) is satised (cf. Angluin [1]).
Following Angluin [2], an IIM M is said to be conservative if for all relevant texts t
and all n, m ∈ N the following condition is satised. If j = M (t[n]) 6= M (t[n + m])then content (t[n + m]) 6⊆ hj .
We call an IIM M strong-monotonic if for all relevant texts t and all n, m ∈ N
the following condition is satised. If j = M (t[n]) 6= M (t[n + m]) = k then hj ⊆ hk
(cf. Jantke [16], Lange and Zeugmann [18]).
We denote the resulting learning types by ConsTxt, ConsvTxt, and SmonTxt, respectively.
After having dened several learning models, it is only natural to ask why should
we study learning with nonconstructivity. The answer is given by the fact that many
interesting language classes are not learnable from text. As shown in [22], even quite
simple classes cannot be learned from text, e.g., the classC = (Lj )j∈N , where L0 = {aj | j ∈ N+ } and Lj = {a` | 1 ≤ ` ≤ j} .

(1)

We aim to characterize quantitatively the diculty of such learning problems bymeasuring the amount of nonconstructivity needed to solve them.
The learners used for nonconstructive inductive inference take as input not only
growing initial segments t[n] of a text t but also a help-word w. The help-words
are assumed to be encoded in binary. So, for such learners we write M (t[n], w) to
denote the hypothesis output by M . Then, for all the learning types dened above,
we say that M nonconstructively identies L with the help-word w provided thatfor every text t for L the sequence (M (t[n], w))n∈N converges to a number j suchthat hj = L (for LimTxt) and M is consistent (conservative, strong-monotonic) for
ConsTxt (for ConsvTxt, and SmonTxt), respectively. More formally we have thefollowing denition.

Denition 6. Let C be any class of languages, let H = (hj )j∈N be a hypothesis spacefor C , and let d ∈ R. An IIM M infers C with nonconstructivity d(n) in the limit withrespect to H, if for each n ∈ N there is a help-word w of length at most d(n) such thatfor every L ∈ C ∩ {h0 , h1 , . . . , hn } and every text t for L the sequence (M (t[m], w))m∈N
converges to a hypothesis j satisfying hj = L.
Clearly, Denition 6 can be directly modied to obtain nonconstructive conservative and strong-monotonic learning.
Looking at Denition 6 it should be noted that the IIM may need to know either
an appropriate upper bound for n or even the precise value of n in order to exploit
the fact that the target language L is from C ∩ {h0 , h1 , . . . , hn }.

On the Amount of Nonconstructivity in Learning Formal Languages from Text

7

To simplify notation, we make the following convention. Whenever we talk about
nonconstructivity log n, we assume that the logarithmic function to the base 2 isreplaced by its integer valued counterpart blog nc + 1, where log 0 =df 1.
Now we are ready to present our results. Note that some proofs have been inuenced by ideas developed in the quite a dierent context, i.e., the paradigm of learning
by erasing (also called co-learning). We do not explain it here but refer the reader toJain et al. [14] as well as to Freivalds and Zeugmann [12].
3. Results

Already Gold [13] showed that REG ∈/ LimTxt and as mentioned in (1), even quite
simple subclasses of REG are not in LimTxt. So, we start our investigations by asking
for the amount of nonconstructivity needed to identify any indexable class in the limit
from text with respect to any indexed hypothesis space H.
3.1. Nonconstructive Learning of Indexable Classes
As we shall see, the needed amount of nonconstructivity is surprisingly small. In
order to show this result, for every function d ∈ Rmon we dene its inverse dinv asfollows dinv (n) = µy[d(y) ≥ n] for all n ∈ N. Recall that range(d) is recursive forall d ∈ Rmon . Thus, for all d ∈ Rmon we can conclude that dinv (n) ∈ R.

Theorem 1. Let C ∈ ID be arbitrarily xed, let d ∈ Rmon be any function, andlet H = (Lj )j∈N be any indexed hypothesis space for C . Then there is a computable
IIM M such that the class C can be identied with nonconstructivity log dinv (n) in thelimit from text with respect to H.
Proof. Assuming any help-word w of length precisely log dinv (n), the IIM M creates a

bitstring containing only 1s that has the same length as w. This bitstring is interpreted
as a natural number k .
So, k ≥ dinv (n), and thusu∗ =df d(k) ≥ d(dinv (n)) ≥ n .

(2)

We continue to dene the IIM M in a way such that it will learn every language
L ∈ C ∩ {L0 , . . . , Lu∗ } from every of its texts. So, x any such L, let t be any text
for L, and let m ∈ N.
Now, the idea to complete the proof is as follows. In the limit, the IIM M candetermine the number ` of dierent languages enumerated in L0 , . . . , Lu∗ as well as
the least indices j1 , . . . , j` of them and can then nd the language among them whichis equal to L. We assume the lexicographical ordering ≤lo of all strings from Σ∗ , i.e.,si ≤lo si+1 for all i ∈ N.

8

Sanjay Jain, Frank Stephan, and Thomas Zeugmann

Using m, t[m], and the decision function f for H, the IIM M computes the least
number r such that m ≤ r and s ≤lo sr for all s ∈ content (t[m]). Next, M computes

Lr0 = {w | w ≤lo sr , f (0, w) = 1}
Lr1 = {w | w ≤lo sr , f (1, w) = 1}···
Lru∗ = {w | w ≤lo sr , f (u∗ , w) = 1} ,and chooses the least indices j1 , . . . , j`m from 0, 1, . . . , u∗ of all the distinct languages
in the list Lr0 , . . . , Lru∗ . From these languages Lrjz all those are deleted for which
content (t[m]) 6⊆ Lrjz (the inconsistent ones). From the remaining indices, the leastindex j is output such that |Lrj \ content (t[m])| is minimal.
Now, it easy to see that the sequence (`m )m∈N converges to `, the number of thedierent languages enumerated in L0 , . . . , Lu∗ , and that the IIM M nds in the limit
the least indices j1 , . . . , j` for these pairwise dierent languages.
From these languages Lj1 , . . . , Lj` the ones satisfying L \ Ljz 6= ∅ are deleted.
That leaves all those Ljz with L ⊆ Ljz . Now, by assumption there is a leastj ∈ {0, . . . , u∗ } with Lj = L. If L ⊂ Ljz , then there is a string s ∈ Ljz \ L, and assoon as this string appears in the competition, the index j wins. Thus, the sequence(M (t[m], w))m∈N converges to j .
So there is no smallest amount of nonconstructivity needed to learn REG and any
subset thereof in the limit from text. But the amount of nonconstructivity cannot be
zero, since then we would have REG ∈ LimTxt. One can dene a total function t ∈ Tsuch that t(n) ≥ d(n) for all d ∈ Rmon and all but nitely many n. Consequently,
log tinv is then a lower bound for the amount of nonconstructivity needed to learn
REG in the limit from text for the technique used to show Theorem 1.
We continue by asking what amount of nonconstructivity is needed to obtain conservative learning from text for any indexable class. Now, the situation is intuitively
more complex, since ConsvTxt ⊂ LimTxt (cf. [2, 19]). Also, it is easy to see that
the IIM M given in the proof of Theorem 1 is in general not conservative. But thebasic idea still works mutatis mutandis provided we know the number ` of dierent
languages enumerated in L0 , . . . , Ln .

Theorem 2. Let C ∈ ID be arbitrarily xed, and let H = (Lj )j∈N be an indexed
hypothesis space for C . Then there is a computable IIM M such that the class C canbe conservatively identied with nonconstructivity log n from text with respect to H.
Proof. Let H = (Lj )j∈N be any indexed hypothesis space for C , and let n ∈ N. The

help-word w is dened as follows. Since the IIM also needs to know a bound on n, wealways assume n to be a power of 2. Intuitively, we then add one bit and write theOn the Amount of Nonconstructivity in Learning Formal Languages from Text

9binary representation of the exact number ` of pairwise dierent languages enumerated
in L0 , . . . , Ln behind the leading 1 including leading zeros. But of course we do notneed the leading 1 in the help-word, since it can be added by the IIM M . So if thehelp-word w has length k , then the added leading 1 with k − 1 zeros gives n and thebitstring w without the added leading 1 gives `.
Given `, the desired IIM M can nd the least indices of these ` pairwise dierent
languages by using the decision function f from the proof of Theorem 1 above, where
we additionally require r to be large enough to detect ` dierent languages.
The rest is done inductively. The IIM M checks whether or not t(0) ∈ Lrjz , wherez = 1, . . . , `, and deletes all languages which fail. Then M orders the remaining
sets Lrjz with respect to set inclusion, and outputs the index of the minimal one withthe smallest index. For m > 0, M checks whether or not content (t[m]) ⊆ LM (t[m−1]) .
If it is, it outputs M (t[m − 1]).
Otherwise, it checks whether or not content (t[m]) ⊆ Lrjz , z = 1, . . . , `, and deletes
all languages which fail. Then M orders the remaining sets Lrjz with respect to set
inclusion, and outputs the index of the minimal one with the smallest index.
We also have the following lower bound.

Theorem 3. There is a class C ∈ ID and an indexed hypothesis space H for it suchthat for every IIM that learns C conservatively with respect to H less than log n − 2many bits of nonconstructivity are not enough.
Proof. This proof is done by diagonalization. We have to dene a family (Lj )j∈Nof uniformly recursive languages and then to show that is satises the assertion of
the theorem. Let ϕ ∈ P 2 be any xed Gödel numbering of P . We interpret every
partial recursive function ϕi as an IIM, i.e., we set Mi = ϕi . Below we shall use
the alphabet Σ = {a, b} and assume any xed recursive encoding h·, ·i of all nitesequences from Σ∗ ×{0, 1}∗ onto the natural numbers. To simplify notation we shortly
write M (σ, β) instead of M (hσ, βi), where σ is any nite sequence of elements from Σ∗and β ∈ {0, 1}∗ . Also, we write M (σ, β) ↓ = ` provided the computation of M (σ, β)stops in a nite number of steps and outputs `.
Our construction is organized in blocks, where in Block i, i ∈ N, we shall denelanguages L2i +j for all 0 ≤ j ≤ 2i − 1, i.e., the languages L2i , . . . , L2i+1 −1 by diagonalizing against Mi−1 and all possible help-words β ∈ {0, 1}∗ with 0 ≤ |β| < i including
the empty one λ. Note that there are 2i − 1 many such β .
Part of the construction is based on an idea developed by Angluin [2]. For the sakeof completeness we set L0 = {b} and dene L1 = {bb}.
For i ≥ 1 we have to dene 2i many languages. In addition, we also dene a text ti
incrementally. This is done in Block i as follows.
For j = 0, . . . , 2i − 1 execute the following.

10

Sanjay Jain, Frank Stephan, and Thomas Zeugmann

Initialize L2i +j := {ai }, set Ci = {β | β ∈ {0, 1}∗ , 0 ≤ |β| < i}, Di = ∅, and initialize
the text ti by dening ti (0) = ai .
Execute Step 1.

Step k. Execute Instruction (A).
(A) Let ti (k) = ai bk . Execute Instruction (B).
(B) Let L2i +j := L2i +j ∪ {ai bk } for all j ∈ {0, . . . , 2i − 1} \ Di .
Execute Instruction (C).
(C) For all β ∈ Ci and all ` = 0, 1, . . . , k check whether or not

Mi−1 (ti [`], β) ↓ = 2i + j

for some j ∈ {0, . . . , 2i − 1} \ Di(3)

can be veried within at most k steps of computation until the rst such β , jand ` are found, if ever.
If β and j are found then let j∗ := min({0, . . . , 2i − 1} \ (Di ∪ {j}));Ci := Ci \ {β} and Di := Di ∪ {j∗ }.
Else do nothing.
Goto Step k + 1.
Now, it is easy to see that (L` )`∈N is a family of uniformly recursive languages.
Let i ≥ 1 be arbitrarily xed and suppose by way of contradiction that Mi−1
conservatively learns all the languages L2i +j , where 0 ≤ j ≤ 2i − 1, dened in Block i
by using help-words of size less than i. Note that i − 1 = blog(2i+1 − 1)c + 1 − 2 =log(2i+1 − 1) − 2 by the convention made at the very end of the Preliminaries.
Note that in Instruction (C), if β and j have been found, then exactly one element
is added to Di . Since there are only 2i − 1 possible help-words β , we conclude thatthe set {0, 1, 2, . . . , 2i − 1} \ Di is never empty. So, there is always a number j∗ andby construction j 6= j∗ .
Let β be any of the admissible help-words. We distinguish the following cases.

Case 1. The help-word β is not removed from Ci in any of the steps.
In this case Mi−1 fails to identify L2i +j for all j ∈ {0, 1, 2, . . . , 2i − 1} \ Di whenusing the help-word β . Note that the Di used here is the eventual value of Di . Since{0, 1, 2, . . . , 2i − 1} \ Di 6= ∅, at least one language is not learned, a contradiction.

Case 2. The help-word β is removed from Ci in some Step k.
Let j and j∗ be as described in Instruction (C) above when executing this Step k .
Then by construction we know that content (ti [k]) = L2i +j∗ , since j∗ is added to Di andso L2i +j∗ is not changed any further in Instruction (B). On the other hand, j is still not
in Di and thus L2i +j∗ ⊂ L2i +j after the execution of step k + 1. Consequently, the IIM
Mi−1 cannot learn L2i +j∗ conservatively when using the help-word β , a contradiction.

On the Amount of Nonconstructivity in Learning Formal Languages from Text

11

Therefore, for every help-word, at least one of the languages in Block i is notlearned by Mi−1 or on which Mi−1 is not conservative.
Finally, suppose that there is an IIM M that learns the indexable class (L` )`∈N
with nonconstructivity log n − 2 with respect to the hypothesis space (L` )`∈N . Then
there must be an i ∈ N such that M = Mi . Consequently, for n = 2i+2 − 1 there must
be a help-word w of length less than i + 1 such that Mi conservatively learns all the
languages L0 , . . . , L2i+2 −1 from any of its texts and w.
Now, we consider in particular Block i + 1, i.e., the languages L2i+1 , . . . , L2i+2 −1 .
Since |w| < i + 1 there must be a β such that w = β for some β ∈ Ci+1 . But as
our discussion above showed, this is impossible. So, we have a contradiction and our
supposition must be false. Hence, the theorem is shown.
Finally, we look at strong-monotonic learning. Again the situation is more complex,
since SmonTxt ⊂ ConsvTxt (cf. [19]). We also add L0 = ∅ to every hypothesis space
allowed, i.e., we always consider class comprising hypothesis spaces.

Theorem 4. Let C ∈ ID be arbitrarily xed, and let H = (Lj )j∈N be an indexed
hypothesis space for C . Then there is a computable IIM M such that the class C canbe strong-monotonically identied with nonconstructivity 2 log n from text with respect
to H.
Proof. The key observation is that it suces to know the following number
p = |{(i, j) | Li 6⊆ Lj , i, j = 0, . . . , n}| .
So, the help-word is just the binary encoding of p and n which is done mutatis mutandis
as in the proof of Theorem 2. The rest is not too dicult, and thus omitted.
Again, the bound given in Theorem 4 cannot be improved substantially, since wehave the following lower bound.

Theorem 5. There is a class C ∈ ID and an indexed hypothesis space H for itsuch that for every IIM that learns C strong-monotonically with respect to H less than
2 log n − 4 many bits of nonconstructivity are not enough.
Proof. Again we use diagonalization to show the desired result. We construct a family(Lj )j∈N of uniformly recursive languages. As in the proof of Theorem 3 we set Mi = ϕi ,where ϕ ∈ P 2 is any xed Gödel numbering of P , and we use the same notations as
there for IIMs. The construction is done in Blocks, where in Block i, i ∈ N, we shalldene languages L2i +j for all j ∈ {0, . . . , 2i − 1} by diagonalizing against Mi−1 andthe length-lexicographically rst 22(i−1) possible help-words β ∈ {0, 1}∗ . For the sakeof completeness we set L0 = ∅ and L1 = {b}.
For every i ≥ 1 we have to dene 2i many languages. We divide these languages
in two groups of size 2i−1 , where the rst group contains the languages L2i +j for12

Sanjay Jain, Frank Stephan, and Thomas Zeugmann

j = 0, . . . , 2i−1 − 1. In order to simplify notation, we refer to the languages in the rstgroup as Lpj , j = 0, . . . , 2i−1 − 1, i.e., Lpj = L2i +j . The second group contains theremaining languages L2i +j for j = 2i−1 , . . . 2i − 1. We refer to these languages as Lqk ,where k = 0, . . . , 2i − 1, i.e., Lqk = L2i +2i−1 +k . Since the construction is a bit more
complicated, for each Lpj we incrementally dene a text tji , where j = 0, . . . , 2i−1 − 1.
In Block i do the following.
Initialize the languages Lpj := {ai } for all j = 0, . . . , 2i−1 − 1 and Lqk := {ai } forall k = 0, . . . , 2i−1 − 1, set Ci = {β | 0 ≤ |β| < 2(i − 1)} ∪ {02(i−1) }, and let tji (0) := ai
for all j = 0, . . . , 2i−1 − 1. Furthermore, set x = 0 and set Dj = ∅.
Start Step 1.

Step s. Execute the following loop.
For j = 0 to 2i−1 − 1 do

x := x + 1;
Lpj := Lpj ∪ {ai bx };tji (x) := ai bx ;tzi (x) := tzi (x − 1) for all z ∈ {0, . . . , 2i−1 − 1} \ {j};Lqz := Lqz ∪ {ai bx } for all z = 0, . . . , 2i−1 − 1;
For k = 0 to 2i−1 − 1 do
If k ∈ Dj pass;
For all β ∈ Ci and ` = 0, . . . , x check whether or not

Mi−1 (tji [`], β) ↓ = pj
can be veried within at most s steps of computation.
If the test (4) is satised for a β ∈ Ci thenCi := Ci \ {β};x := x + 1;
Lpj := Lpj ∪ {ai bx };tji (x) := ai bx ;tzi (x) := tzi (x − 1) for all z ∈ {0, . . . , 2i−1 − 1} \ {j};Lqz := Lqz ∪ {ai bx } for all z ∈ {0, . . . , 2i − 1} \ {k};Dj = Dj ∪ {k};Else do nothing.

end
end
If Ci 6= ∅ start Step k + 1.

(4)

On the Amount of Nonconstructivity in Learning Formal Languages from Text

13

Note that the instruction pass in the second loop is used to indicate that in thecase that k ∈ Dj nothing has to be done. That is, the program continues the loopwith k + 1 if k + 1 ≤ 2i−1 − 1; otherwise it returns to the rst loop.
It should also be noted that we introduced the variable x above just to makesure that all texts have the same length and that any new element added to thecorresponding languages has not been inserted in an earlier execution of the nested
loops in the current step nor did we insert the new element in a previous step.
Now, it is easy to see that (L` )`∈N is a family of uniformly recursive languages.
Let i ≥ 1 be arbitrarily xed and suppose by way of contradiction that Mi−1
strong-monotonically learns all the languages L2i +j , where 0 ≤ j ≤ 2i − 1, dened in
Block i by using help-words of size less than 2(i − 1) or the help word 02(i−1) . Notethat 2(i − 1) = 2(blog(2i+1 − 1)c + 1) − 4 = 2 log(2i+1 − 1) − 4 by the convention madeat the very end of the Preliminaries.
Furthermore, note that by construction for every j the set Dj can be updated atmost 2i−1 many times. As soon as Dj = {0, . . . , 2i−1 −1} the second loop does nothing
for this j . Also note that for any change of some Dj a success in Test (4) is necessary.
Thus, when Dj = {0, . . . , 2i−1 − 1} for all j , we must have also deleted all help-words.
Let β be any of the admissible help-words. We distinguish the following cases.

Case 1. The help-word β is not removed from Ci in any of the steps.
In this case, there must be at least one j∗ such that Dj∗ ⊂ {0, . . . , 2i−1 − 1}. So,
if the Test (4) does never succeed for such a j∗ , when using the help-word β thenfor Lpj∗ we have a text tji ∗ on which the IIM Mi−1 fails to learn Lpj∗ when using β .
So, the IIM Mi−1 does not learn Lpj∗ when using β as help-word for at least one text,
a contradiction.

Case 2. The help-word β is removed from Ci in some step.
Let s be the step in which this happens. Then there must be a j∗ and a k∗ suchthat the variable j in the rst loop takes the value j∗ and the variable k in the second
loop takes the value k∗ and the Test (4) is satised for some `. This also implies
that k∗ ∈/ Dj∗ .
Now, by construction we know that tji ∗ [x] ⊆ Lqk∗ and tji ∗ [x] ⊆ Lpj∗ , where x is as at
the time when Test (4) is executed. However, now the language Lpj∗ obtains the newelement ai bx+1 while Lqk∗ does not. Consequently, we have Lpj∗ 6⊆ Lqk∗ . So, we havean initial segment of a text for Lqk∗ , i.e., tji ∗ [x], such that the IIM Mi−1 , using thehelp-word β , cannot strong-monotonically learn Lqk∗ from any text extending tji ∗ [x],since it has output pj∗ on tji ∗ [`] for some ` ≤ x. This is a contradiction.
Consequently, for each help-word β there is at least one language in Block i thatis not learned at all by Mi−1 or for which Mi−1 is not strong-monotonic.
The rest is done mutatis mutandis as in the proof of Theorem 3 and therefore
omitted.

14

Sanjay Jain, Frank Stephan, and Thomas Zeugmann

Having these general results, we can also ask what happens if we allow a suitablychosen hypothesis space for REG such as all DFAs. Then for all i, j ∈ N equality
Li = Lj and subset Li ⊆ Lj are decidable, and thus we are in the setting describedin the proof of Theorem 1. That is we have the following theorem.

Theorem 6. Let C ⊆ REG be arbitrarily xed, let d ∈ Rmon be any function, andlet H = (Lj )j∈N be any indexed hypothesis space for C such that H has a decidable
subset problem. Then there is a computable IIM M such that the class C can be strongmonotonically identied with nonconstructivity log dinv (n) from text with respect to H.
3.2. Nonconstructive Learning of Recursively Enumerable Classes
Next, we turn our attention to the amount of nonconstructivity needed to learn
recursively enumerable classes of recursively enumerable languages.

Theorem 7. Let ψ ∈ P 2 be any numbering. Then there is always an IIM M learning
the family (Wiψ )i∈N+ in the limit from text with nonconstructivity log n with respect
to (Wiψ )i∈N+ .
Proof. The help-word w is essentially the same as in the proof of Theorem 2, i.e., it

is a bitstring of b of length log n which is the binary representation of `, the numberof pairwise dierent languages enumerated in W1ψ , . . . , Wnψ plus n.
Let L ∈ C ∩ {W1ψ , . . . , Wnψ } and let t be any text for L. On input any t[m] and thehelp-word w the desired IIM M executes the following.
(1) For all 0 < i ≤ n enumerate Wiψ for m steps, that is M tries to computeψi (0), . . . , ψi (m) for at most m steps and enumerate those arguments x forψ
which ψi (x) turns out to be dened. Let Wi,mbe the resulting sets, 0 < i ≤ n.
ψψ
\ Wj,m6= ∅. If
(2) For all pairs (i, j) with 0 < i, j ≤ n check whether or not Wi,mψψ
it is, let d(i, j) be the least element in Wi,m \ Wj,m . If there is no such element,
we set d(i, j) = ∞.

(3) Having the numbers d(i, j) the IIM M checks whether or not there are at least `ψψpairwise dierent languages among W1,m
, . . . , Wn,m
. If not, then M (t[m]) = 0.
ψOtherwise, let S = {i | 0 < i ≤ n, Wj,m
6= ∅} and consider all sets S̃ ⊆ S
satisfying |S̃| = `. For each such set S̃ = {j1 , . . . , j` } compute the numbers
ψψ
xj,k =df min(Wj,m
4 Wk,m) for all j, k ∈ S̃ , where j < k and let s(S̃) be themaximum of all those xj,k . Furthermore, for each set S̃ we consider the `-tuple(j1 , . . . , j` ), where ji < ji+1 , i = 1, . . . , ` − 1. Using these tuples, we can orderthem lexicographically and then choose the rst set S̃ in this order for which s(S̃)
is minimized, i.e., s(S̃) ≤ s(Ŝ) for all Ŝ with Ŝ ⊆ S and |Ŝ| = `. Let i1 , . . . , i`be the elements of this set S̃ in their natural order.

On the Amount of Nonconstructivity in Learning Formal Languages from Text

15

Then M takes the languages Wiψ1 ,m , . . . , Wiψ` ,m into consideration. From thesecandidate hypotheses i1 , . . . , i` the least i is output for which t[m] contains allnite d(i, j), j = i1 , . . . , i` , and t[m] does not contain any of the nite d(j, i),
j = i1 , . . . , i` . If there is no such i, then M (t[m]) = 0.
It remains to argue that M learns L in the limit from t. Note that the ` pairwisedierent languages are found in the limit, since the minimal element in the symmetricdierence of the two languages tends to innity if the two languages are equal (if any
element is found at all).
So, the set of candidate hypotheses stabilizes in the limit, and by construction M
then outputs the correct i as soon as the initial segment is large enough. We omit
further details.
Note that the IIM dened in the proof of Theorem 7 even witnesses a much stronger
result, i.e., it always converges to the minimum index i of the target language.
The following lower bound shows that Theorem 7 cannot be improved substantially.
In order to show this result we need the following proposition.

Proposition 1. Given a set M = {M1 , M2 , M3 , . . . , Mm } of m IIMs, one can eectively nd grammars g0M , g1M , . . . , gmM such that none of M1 , M2 , . . . , Mm learns in thelimit all the languages Wg0M , Wg1M , . . . , WgmM .
Theorem 8. There is a numbering ψ ∈ P 2 such that no IIM M can learn thefamily (Wiψ )i∈N+ in the limit from text with nonconstructivity log n − 2 with respect
to (Wiψ )i∈N+ .
Proof. Using Proposition 1, the theorem can be shown as follows.
For any learner M , let M β be the learner which behaves just like M with theadvice β as additional input.
We dene the numbering ψ as follows. Let ϕ be any xed Gödel numbering of P .
We interpret every partial recursive function ϕi as an IIM M , i.e., Mi = ϕi forevery i ∈ N.
The set Wjψ , for 2i ≤ j < 2i+1 , is dened to be WgM i , where M = {Miβ | |β| < i}.
j−2Note that there are 2i − 1 many help-words β with 0 ≤ |β| < i, and we thus havethe needed number 2i of grammars (cf. Proposition 1). Thus, for any i, and any β oflength at most i − 1, the IIM Miβ does not learn at least one of the languages Wjψ ,where 2i ≤ j < 2i+1 .
Now, suppose by way of contradiction that there is an IIM M that learns the wholefamily (Wiψ )i∈N+ using nonconstructivity log n − 2. Then there must be an i ∈ N suchthat M = Mi .
So this IIM Mi learns the family (Wiψ )i∈N+ using nonconstructivity log n−2. Then,the IIM Miβ , for some β with length at most i − 1, learns all the languages Wjψ , for2i ≤ j < 2i+1 . A contradiction.

16

Sanjay Jain, Frank Stephan, and Thomas ZeugmannSo, it remains to show Proposition 1. We shall show a bit stronger result.

Proposition 2. Given a set M = {M1 , M2 , M3 , . . . , Mm } of m IIMs, and two disjoint nite sets S1 and S2 , S1 , S2 ⊆ N, one can eectively (in M) nd grammars
M,S1 ,S2
g0M,S1 ,S2 , g1M,S1 ,S2 , . . . , gm
such that for some i ≤ m, none of M1 , M2 , . . . , Mm
learns in the limit all the languages Wg0M,S1 ,S2 , Wg1M,S1 ,S2 , . . . , WgmM,S1 ,S2 , where we additionally have the properties that(a) S1 ⊆ WgM,S1 ,S2 , for i ≤ m, andi(b) S2 ∩ WgM,S1 ,S2 = ∅, for i ≤ m.
i

Proof. We show below how to dene gjM,S1 ,S2 , for every 0 ≤ j ≤ |M|. These grammars

are generated implicitly by using the operator recursion theorem [5]. If M = ∅ thenwe let WgM,S1 ,S2 = S1 .
0

Suppose M = {M1 , M2 , . . . , Mm }, with m > 0, and let disjoint nite sets S1 , S2
be given. The sets WgM,S1 ,S2 , for 1 ≤ j ≤ m, are dened via a staging construction asjfollows. Note that the construction is dierent for each dierent input M, S1 , S2 .
Let σ0 be a sequence with content S1 . Enumerate S1 in each of Whj , j ≤ m.
It will be the invariant that at the beginning of stage s, content (σs ) = Whj enumerated before Stage s, for 1 ≤ j ≤ m.
Go to Stage 0.

Stage s.
Dovetail Steps 1 and 2, until, if ever, Step 1 succeeds. If Step 1 succeeds, then stop
Step 2 and go to Step 3.

Step 1. Search for an extension σ of σs , where content (σ) ∩ S2 = ∅, such thatM(s mod m)+1 (σs ) 6= M(s mod m)+1 (σ).

Step 2. Let x be such that x 6∈ content (σs ) ∪ S2 .
Enumerate x in Whm .
Let S20 = S2 ∪ {x}. Let S10 = content (σs ).
Let M0 = M − {M(s mod m)+1 }.
Let Whj , for j < m, follow W M0 ,S10 ,S20 (until, if ever search in Step 1 succeeds).
gj
S
Step 3. If and when Step 1 succeeds, let X = j≤m Whj ∪ content (σ) enumerated
upto now.
Enumerate X in Whj , for j ≤ m.
Let σs+1 be an extension of σ such that content (σs+1 ) = X .
Go to Stage s + 1
End Stage s.

On the Amount of Nonconstructivity in Learning Formal Languages from Text

17

We now claim that gjM,S1 ,S2 as dened above satisfy the proposition. This is by
induction on size of M. Suppose the proposition properties hold for all M of size lessthan m. Then, we show that it holds for M of size m.
Fix M (of size m), and S1 , S2 and consider the following cases for the construction
given above.

Case 1. There are innitely many stages.
S
In this case, all Whj , j ≤ m, are the same language given by content ( s∈N σs ), andeach of the learners M1 , M2 , . . . , Mm , makes innitely many mind changes on the textSs∈N σs .

Case 2. Stage s starts but does not nish.
In this case, clearly, M(s mod m)+1 converges on all texts extending σs which do notcontain any element from S2 . Thus, either M(s mod m)+1 does not learn Whm , (whichcontains x as dened in Stage s), or does not learn any of Whj , j < m, which do
not contain x. Furthermore, by the induction hypothesis, none of the learners in M0
learns all the languages in Whj , where 0 ≤ j < m.
Thus, the proposition follows.
The situation considerably changes if we require conservative learning. In order topresent this result, we need the following. A function h : N → N is said to be limiting
recursive if there is a function h̃ ∈ R2 such that h(i) = lim h̃(i, t) for all i ∈ N.
t→∞

Theorem 9. For every limiting recursive function h there is a recursively enumerable
family (Wiψ )i∈N of recursively enumerable languages such that no IIM with nonconstructivity at most h can learn (Wiψ )i∈N conservatively with respect to (Wiψ )i∈N .
Proof. Let the limiting recursive function h : N → N be arbitrarily xed. Furthermore,
we assume any xed function h̃ ∈ R2 such that h(i) = lim h̃(i, n) for all i ∈ N.
n→∞

Again, we x any Gödel numbering ϕ of P and interpret each ϕi as an IIM, i.e.,
we have Mi = ϕi for all i ∈ N.
For every number i ∈ N we construct two recursively enumerable sets W2iψ andψ
W2i+1
such that for each help-word β ∈ {0, 1}∗ with 0 ≤ |β| ≤ h(2i + 1) there will beψ
a text such that Mi fails to learn at least one of the languages W2iψ and W2i+1
or Mi
is not conservative. This is done as follows.
For each number i ∈ N do the following. Set t := 0.
ψ
Initialize W2iψ = {hi, 2xi | x ∈ N} and W2i+1= {hi, 2x + 1i | x ∈ N}.

Goto (1).
(1) Compute mt := h̃(2i + 1, t) and let rt = 2mt +1 − 1.
Set Ct = {1, . . . , rt } and enumerate in lexicographic order all β ∈ {0, 1}∗ with0 ≤ |β| ≤ mt . We refer to these elements as βj , where j ∈ Ct .
Dovetail the execution of (α) and (2).

18

Sanjay Jain, Frank Stephan, and Thomas Zeugmann(α) do forevert := t + 1;

if h̃(2i + 1, t − 1) < h̃(2i + 1, t) thenlet mt := h̃(2i + 1, t) and rt = 2mt +1 − 1;Update Ct := {1, . . . , rt } and update (A) by including the newly
found j ∈ Ct .
end(2) Start (A).
(A) For each j ∈ Ct try to nd, by dovetailing the following search, a nitesequence σβj of elements from {hi, xi | x ∈ N} such that the condition
Mi (σβj , βj ) ↓ = 2i is veried.
Once such a sequence σβj is found, if ever, stop (A) for the j for which thesearch succeeded but continue for the remaining values of j , and update

W2iψ := W2iψ ∪ content (σβj ) ,
ψ
W2i+1

:=

ψ
W2i+1
∪

content (σβj ) .

(5)
(6)

Now start (B) for the j for which the search succeeded.
(B) Try to nd a nite sequence τβj of elements from {hi, xi | x ∈ N} such that
Mi (σβj  τβj , βj ) ↓ = 2i + 1, where σβj  τβj denotes the concatenation of thenite sequences σβj and τβj .
If such a τβj is found, if ever, stop (B) for the j for which the search
succeeded and update

W2iψ := W2iψ ∪ content (τβj ) ,
ψ
W2i+1

:=

ψ
W2i+1
∪

content (τβj ) .

(7)
(8)

Furthermore, set Ct := Ct \ {j}. If Ct 6= ∅ continue (A) or (B) for theremaining j ∈ Ct .
If Ct = ∅ then stop (A) and (B) until, if ever, in (α) the set Ct is updated.
Now, it is easy to see that (W`ψ )`∈N is a recursively enumerable family of recursively
enumerable languages. It remains to show that no IIM M can learn (W`ψ )`∈N conservatively with nonconstructivity h with respect to (W`ψ )`∈N .
Suppose the converse, i.e., there is an IIM M that learns (W`ψ )`∈N conservatively
with respect to (W`ψ )`∈N . In order to obtain a contradiction, it suces to show that
there is some n ∈ N such that for each help-word w with 0 ≤ |w| ≤ h(n) there isa language W from our family such that W ∈ {W0ψ , . . . , Wnψ } but W is not learned
conservatively by M .
Since M is an IIM, there must be an i ∈ N such that M = Mi . Furthermore, since h
is limiting recursive, there must be t0 ∈ N such that h(2i + 1) = h̃(2i + 1, t0 + k)

On the Amount of Nonconstructivity in Learning Formal Languages from Text

19

for all k ∈ N. That is, as soon as our t in (α) satises t ≥ t0 no further updateof Ct is occurring in (α). It should also be noted that we may have included more
help-words βj in our construction than actually necessary, since we only checked ifh̃(2i + 1, t) does increase. But this does not matter as we shall see below.
We claim that for n = 2i+1 the desired contradiction can be obtained. We consider
ψthe sets W2iψ and W2i+1.
As said above, as soon as t ≥ t0 the set Ct does not change any further in theloop (α). So, let m = h(2i + 1) and r = 2m+1 − 1. It suces to consider all help-words
β1 , . . . , βr , where 0 ≤ |βj | ≤ m for all j = 1, . . . , r.
Let any such βj be arbitrarily xed. Then we try in (A) in particular any nitesequence σ of elements of W2iψ . Thus, if for all sequences σ either Mi (σ, βj ) remains
undened or turns out to be dened but Mi (σ, βj ) 6= 2i then Mi fails to learn W2iψ whenusing the help-word βj , since there is no other index for this language in (W`ψ )`∈N .
ψ
Here it should be noted that W2iψ 6= W2i+1, since the at most nitely often occurring
updates in (5), (6), (7), and (8) do only add nitely often nitely many elementsψ, respectively.
to W2iψ and W2i+1
Otherwise, the search must eventually succeed, i.e., we nd a nite sequence σβjsuch that Mi (σ, βj ) ↓ = 2i.
ψ, too (see (6)). So, in (B)Now, by construction we know that content (σβj ) ⊆ W2i+1ψ
we try in particular any nite sequence τ of elements of W2i+1 , and by constructionψalso each sequence σβj  τ is an initial segment of a text for W2i+1. Consequently, ifψ
we never verify Mi (σβj  τ, βj ) ↓ = 2i + 1 in (B) then Mi fails to learn W2i+1
from every
text starting with σβj .

Otherwise, in (B) we nd a τβj such that Mi (σβj  τβj , βj ) ↓ = 2i + 1.
ψ
as well as
Now, by construction we know that content (σβj ) ∪ content (τβj ) ⊆ W2i+1ψ
content (σβj ) ∪ content (τβj ) ⊆ W2i (see (8) and (7)).
ψ. But sinceThus, σβj  τβj is an initial segment of a text for both W2iψ and W2i+1

Mi (σβj , βj ) ↓ = 2i 6= 2i + 1 = Mi (σβj  τβj , βj ) ↓ ,we see that Mi (σβj , βj ) 6= Mi (σβj  τβj , βj ) even though content (σβj  στj ) is containedin W2iψ . This is a contradiction to Mi (with help-word βj ) being conservative.
So, for every help-word βj , 0 ≤ |βj | ≤ m the IIM Mi either does not learn W2iψψor W2i+1
or it is not conservative. Thus, the theorem is shown.
Since SmonTxt ⊂ ConsvTxt, Theorem 9 directly allows for the following corollary.

Corollary 1. For every limiting recursive function h there is a recursively enumerable
family (Wiψ )i∈N of recursively enumerable languages such that no IIM with nonconstructivity at most h can learn (Wiψ )i∈N strong-monotonically with respect to (Wiψ )i∈N .

20

Sanjay Jain, Frank Stephan, and Thomas Zeugmann

4. Conclusions

We have presented a model for the inductive inference of formal languages from textthat incorporates a certain amount of nonconstructivity. In our model, the amountof nonconstructivity needed to solve the learning problems considered has been used
as a quantitative characterization of their diculty.
We studied the problem of learning indexable classes under three postulates, i.e.,learning in the limit, conservative identication, and strong-monotonic inference. As
far as learning in the limit is concerned, the amount of nonconstructivity needed tolearn any indexable class can be very small and there is no smallest amount that canbe described in a computable way (cf. Theorem 1).
Moreover, we showed upper and lower bounds for conservative learning of indexable classes and for strong-monotonic inference roughly showing that the amountof nonconstructivity needed is log n for conservative learning and 2 log n for strongmonotonic inference.
However, if we allow canonical indexed hypothesis spaces for REG such that equality of languages is decidable, then the amount of nonconstructivity needed to learn
REG even strong-monotonically can be made very small.
Finally, we studied the problem to learn recursively enumerable classes of recursively enumerable languages. In this setting, the amount of nonconstructivity needed
to learn in the limit is log n, while there is not even a limiting recursive bound for theamount of nonconstructivity to learn all recursively enumerable classes of recursively
enumerable languages conservatively or strong-monotonically.

Acknowledgment

This research was performed partially while the third author was visiting the Instituteof Mathematical Sciences at the National University of Singapore in September 2011.
His visit was supported by the Institute. Sanjay Jain was supported in part by
NUS grant numbers C252-000-087-001 and R252-000-420-112, and Frank Stephan
was supported in part by NUS grant number R252-000-420-112.

References[1] Dana Angluin. Finding patterns common to a set of strings. J. of Comput. Syst.
Sci., 21(1):4662, 1980.
[2] Dana Angluin. Inductive inference of formal languages from positive data. Inform. Control, 45(2):117135, 1980.

On the Amount of Nonconstructivity in Learning Formal Languages from Text

21[3] Janis M. Barzdin². Complexity of programs to determine whether natural numbers not greater than n belong to a recursively enumerable set. Soviet Mathematics Doklady, 9:12511254, 1968.
[4] Olaf Beyersdor, Johannes Köbler, and Sebastian Müller. Proof systems thattake advice. Information and Computation, 209(3):320332, 2011.
[5] John Case. Periodicity in generations of automata. Math. Syst. Theory, 8(1):15
32, 1974.
[6] Stephen Cook and Jan Kraji£ek. Consequences of the provability of NP ⊆P/poly . The Journal of Symbolic Logic, 72(4):13531371, 2007.
[7] Carsten Damm and Markus Holzer. Automata that take advice. In Mathematical

Foundations of Computer Science 1995, 20th International Symposium, MFCS
'95, Prague, Czech Republic, August 28 - September 1, 1995, Proceedings, volume
969 of Lecture Notes in Computer Science, pages 149158, Berlin, 1995. Springer.

[8] Paul Erd®s. Some remarks on the theory of graphs. Bulletin of the American
Mathematical Society, 53(4):292294, 1947.
[9] Rusin² Freivalds. Amount of nonconstructivity in nite automata. In Sebastian
Maneth, editor, Implementation and Application of Automata, 14th International
Conference, CIAA 2009, Sydney, Australia, July 14-17, 2009. Proceedings, volume 5642 of Lecture Notes in Computer Science, pages 227236, Berlin, 2009.
Springer.
[10] Rusin² Freivalds. Amount of nonconstructivity in deterministic nite automata.
Theoretical Computer Science, 411(38-39):34363443, 2010.
[11] Rusin² Freivalds and Thomas Zeugmann. On the amount of nonconstructivity inlearning recursive functions. In Mitsunori Ogihara and Jun Tarui, editors, The-ory and Applications of Models of Computation, 8th Annual Conference, TAMC
2011, Tokyo, Japan, May 23-25, 2011, Proceedings, volume 6648 of Lecture Notes
in Computer Science, pages 332343. Springer, 2011.

[12] Rusins Freivalds and Thomas Zeugmann. Colearning of recursive languages frompositive data. In Perspectives of System Informatics, Second International Andrei

Ershov Memorial Conference, Akademgorodok, Novosibirsk, Russia, June 1996,
Proceedings, volume 1181 of Lecture Notes in Computer Science, pages 122133.
Springer, 1996.

[13] E. Mark Gold. Language identication in the limit. Inform. Control, 10(5):447
474, 1967.
[14] Sanjay Jain, Em Kinber, Steen Lange, Rolf Wiehagen, and Thomas Zeugmann.
Learning languages and functions by erasing. Theoret. Comput. Sci., 241(12):143189, 2000. Special issue for ALT '96.

22

Sanjay Jain, Frank Stephan, and Thomas Zeugmann[15] Sanjay Jain, Daniel Osherson, James S. Royer, and Arun Sharma. Systems
that Learn: An Introduction to Learning Theory, second edition. MIT Press,
Cambridge, Massachusetts, 1999.
[16] Klaus P. Jantke. Monotonic and non-monotonic inductive inference. New Generation Computing, 8(4):349360, 1991.
[17] Richard M. Karp and Richard J. Lipton. Turing machines that take advice. L'
Enseignement Mathématique, 28:191209, 1982.
[18] Steen Lange and Thomas Zeugmann. Types of monotonic language learningand their characterization. In David Haussler, editor, Proc. 5th Annual ACM
Workshop on Comput. Learning Theory, pages 377390, New York, NY, 1992.
ACM Press.
[19] Steen Lange and Thomas Zeugmann. Language learning in dependence on thespace of hypotheses. In Lenny Pitt, editor, Proceedings of the Sixth Annual ACM
Conference on Computational Learning Theory, pages 127136, New York, NY,
1993. ACM Press.
[20] Steen Lange, Thomas Zeugmann, and Sandra Zilles. Learning indexed familiesof recursive languages from positive data: A survey. Theoret. Comput. Sci.,
397(1-3):194232, 2008.
[21] Hartley Rogers, Jr. Theory of Recursive Functions and Eective Computability.
McGraw-Hill, 1967. Reprinted, MIT Press 1987.
[22] Thomas Zeugmann and Steen Lange. A guided tour across the boundaries
of learning recursive languages. In Algorithmic Learning for Knowledge-Based
Systems, volume 961 of Lecture Notes in Articial Intelligence, pages 190258.
Springer, 1995.
[23] Thomas Zeugmann, Shin-ichi Minato, and Yoshiaki Okubo. Theory of Computation. Corona Publishing Co., LTD, 2009.