On the Amount of Nonconstructivity in Learning
Formal Languages from Positive Data
Sanjay Jain1 , Frank Stephan2 , and Thomas Zeugmann3
1
Department of Computer Science
National University of Singapore, Singapore 117417
sanjay@comp.nus.edu.sg
2
Department of Computer Science and Department of Mathematics
National University of Singapore, Singapore 117543
fstephan@comp.nus.edu.sg
3
Division of Computer Science, Hokkaido University
N-14, W-9, Sapporo 060-0814, Japanthomas@ist.hokudai.ac.jp

Nonconstructive computations by various types of machines
and automata have been considered by e.g., Karp and Lipton [18] andFreivalds [9, 10]. They allow to regard more complicated algorithms fromthe viewpoint of more primitive 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
classes of formal languages from positive data. Dierent learning types
are compared with respect to the amount of nonconstructivity needed tolearn 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.
Abstract.

1

Introduction

The research subject studied in this paper derives its motivation from various
sources which we shortly present below. Nonconstructive methods of proof inmathematics have a rather long and dramatic history. The debate was especiallypassionate when mathematicians tried to overcome the crisis concerning thefoundations of mathematics.
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 used nonconstructive proofs masterly, beginning with the paper [8].
Another inuential paper was Barzdin² [4], who introduced the notion ofadvice in the setting of Kolmogorov complexity of recursively enumerable sets.
Karp and Lipton [18] introduced the notion of a Turing machine that takes
advice to understand under what circumstances nonuniform upper bounds canbe used to obtain uniform upper bounds. Damm and Holzer [7] adapted the424

S. Jain, F. Stephan, and T. Zeugmann

notion of advice for nite automata. Later Cook and Kraji£ek [6] initiated thestudy of proof systems that use advice for the verication of proofs. Even more
recently, Beyersdor et al. [5] continued along this line of research.
Quite often, we experience that nding a proof for a new deep theorem istriggered by a certain amount of inspiration. Being inspired does not mean that
we do not have to 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 we have found the one sought for. Also, as experience
shows, the more complicated the proof, the higher is the amount of inspirationneeded. These observations motivated Freivalds [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 for many types of automata andmachines and which essentially coincides with Karp and Lipton's [18] 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 to learn recursive functions.
The present paper generalizes the model of Freivalds and Zeugmann [11] tothe inductive inference of formal languages. We aim to characterize the di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 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 # suchthat the range of the text minus the pause symbol contains all strings of L andnothing else. 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-wordand 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 d bounding this length.
As in previous approaches, the help-word does not just provide an answer to thelearning 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 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, 23]). Second we investigate the amount of nonconstructivity
needed to infer recursively enumerable classes of recursively enumerable languages. Moreover, several variations of Gold's [13] model of learning in the limit
have been considered (cf., e.g., [15, 21, 23] and the references therein). Thus, itOn the Amount of Nonconstructivity in Learning Formal Languages425

is only natural to consider some of these variations, too. In particular, we shallstudy conservative learning and strong-monotonic inference.
We show upper and lower bounds for the amount of nonconstructivity inlearning classes of languages from positive data. The usefulness of this approachis 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 havean upper bound of log n and a lower bound of log n − 2 for conservative learningof indexable classes from positive data (cf. Theorems 2 and 3). Furthermore, wehave a 2 log n upper bound and a 2 log n − 4 lower bound for strong-monotonic
inference of indexable 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 growthof the function d is not sucient to learn all recursively enumerable classes ofrecursively enumerable languages from positive data (cf. Theorems 7, 8 and 9).
Due to the lack of space several proofs and details are omitted. A full version ofthis paper is available as technical report (cf. [16]).

2

Preliminaries

Any unspecied notations follow Rogers [22]. In addition to or in contrast with
Rogers [22] 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,
and subset, respectively. Let S1 , S2 be any sets; then we write S1 4 S2 to denotethe 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 of a 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.
Let n ∈ N+ ; then the set of all partial recursive functions and of all recursivefunctions of one and n variables over N is denoted by P, R, P n , Rn , respectively.
Let f ∈ P , then we use dom(f ) to denote the domain of the function f , i.e.,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 ofrecursively enumerable languages as follows. Any ψ ∈ P 2 is called a numbering.
Let ψ ∈ P 2 , then we write ψi instead of λx.ψ(i, x). We set Wiψ = dom(ψi )and refer to it as the ith enumerated language. Clearly, the sets Wiψ ⊆ N arerecursively enumerable.
A function f ∈ P is said to be strictly monotonic provided for all x, y ∈ Nwith x < y we have, if both f (x) and f (y) are dened then f (x) < f (y). By Rmon
we denote the set of all strictly monotonic recursive functions.

426

S. Jain, F. Stephan, and T. ZeugmannLet Σ be any xed nite alphabet, and let Σ ∗ be the free monoid over Σ .
Any L ⊆ Σ ∗ is a language. Furthermore, we x a symbol # such that # ∈/ Σ . By
REG we denote the class of all regular languages (cf., e.g., [24]). 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 and any number of repetitions is allowed. For any n ∈ N we use t[n] todenote 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 thecontent of an initial segment and of a text, respectively.
An algorithmic learner M nds a rule (grammar) from growing initial segments of a text. On each initial segment the learner M has to output a hypothesis
which is a natural 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 suchthat M (t[n]) = j for all but nitely many n ∈ N.
So, we still have to specify the semantics of the numbers output by M . In
order to 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 call f a decision function.

Denition 3. A class C of non-empty recursive languages is said to be in-dexable if there is a family (Lj )j∈N of uniformly recursive languages such thatC = {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 , and also the class of all context-free languages and the classof all context-sensitive languages form an indexable class. Further information
concerning indexable classes and their learnability can be found in [21, 23].
So, when dealing with the learnability of indexable classes, it is only natural to interpret the hypotheses output by M with respect to a chosen indexingof a class containing the target class C (cf. Denition 4 below). On the other
hand, when considering recursively enumerable classes C of recursively enumerable languages, then we always take as hypothesis space the family (Wiψ )i∈N ,where ψ ∈ P 2 is the numbering dening the class C .

Denition 4. Let C be an indexable class. A family H = (Lj )j∈N is said to be

an indexed hypothesis space for C if (Lj )j∈N is uniformly recursive and C ⊆{Lj | j ∈ N}.
Following [20], if C = {Lj | j ∈ N} then we call H class preserving and if
C ⊆ {Lj | j ∈ N} then the hypothesis space H is said to be class comprising.

On the Amount of Nonconstructivity in Learning Formal Languages

427

Now we are ready to provide the formal denition of learning in the limit
from text. 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 todenote our hypothesis 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

a hypothesis space for C , and let L ∈ C . An IIM M is said to learn L in the limit
from text 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 denotedby LimTxt.
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 thecondition content (t[n]) ⊆ hM (t[n]) is satised (cf. Angluin [1], Barzdin [3]).
An IIM M is said to be conservative if for all relevant texts t and alln, 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 (cf. Angluin [2]).
We call an IIM M strong-monotonic if for all relevant texts t and all numbers
n, m ∈ N the following condition is satised. If j = M (t[n]) 6= M (t[n + m]) = k
then hj ⊆ hk must hold (cf. Jantke [17], Lange and Zeugmann [19]).
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 whyshould we study learning with nonconstructivity. The answer is given by the factthat many interesting language classes are not learnable from text. As shownin [23], even quite simple classes cannot be learned from text, e.g., the class[
C = {aj | j ∈ N+ }{a` | 1 ≤ ` ≤ k} .
(1)
k∈N+

We aim to characterize quantitatively the diculty of such learning problemsby measuring 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 helpwords 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 that for every text t for L the sequence (M (t[n], w))n∈N
converges to a number j such that hj = L (for LimTxt) and M is consistent(conservative, strong-monotonic) for ConsTxt (for ConsvTxt, and SmonTxt), respectively. More formally we have the following denition.

428

S. Jain, F. Stephan, and T. ZeugmannDenition 6. Let C be any class of languages, let H = (hj )j∈N be a hypothesis

space for C , and let d ∈ R. An IIM M infers C with nonconstructivity d(n) in
the limit with respect to H, if for each n ∈ N there is a help-word w of length
at most d(n) such that for 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 }.
To simplify notation, we make the following convention. Whenever we talkabout nonconstructivity log n, we assume that the logarithmic function to thebase 2 is replaced 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 beeninuenced by ideas developed in the quite a dierent context, i.e., the paradigmof learning by erasing (also called co-learning). We do not explain it here but
refer the reader to Jain et al. [14] as well as to Freivalds and Zeugmann [12].

3Results

Already Gold [13] showed that REG ∈/ LimTxt and as mentioned in (1), evenquite 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.
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
for all 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,and let H = (Lj )j∈N be any indexed hypothesis space for C . Then there is acomputable IIM M such that the class C can be identied with nonconstructivity
log dinv (n) in the limit 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 bitstringis 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.

On the Amount of Nonconstructivity in Learning Formal Languages

429

Now, the idea to complete the proof is as follows. In the limit, the IIM M
can determine 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 which is equal to L. We assume the lexicographical ordering ≤lo of
all strings from Σ ∗ , i.e., si ≤lo si+1 for all i ∈ N.
Using m, t[m], and the decision function f for H, the IIM M computes theleast 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}..
.
rLu∗ = {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 Lr0 , . . . , Lru∗ . From these languages Lrjz all those are deleted for which
content (t[m]) 6⊆ Lrjz (the inconsistent ones). From the remaining indices, theleast index 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 ofthe dierent languages enumerated in L0 , . . . , Lu∗ , and that the IIM M nds inthe limit the least indices j1 , . . . , j` for these pairwise dierent languages. Fromthese 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, andas soon as this string appears in the competition, the index j wins. Thus, thesequence (M (t[m], w))m∈N converges to j .
tuSo there is no smallest amount of nonconstructivity needed to learn REG andany 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 ∈ T such that t(n) ≥ d(n) for all d ∈ Rmon and all but nitely many n.
Hence, 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 obtainconservative learning from text for any indexable class. Now, the situation is
intuitively more complex, since ConsvTxt ⊂ LimTxt (cf. [2, 20]). Also, it iseasy to see that the IIM M given in the proof of Theorem 1 is in general notconservative. But the basic 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 can be conservatively identied with nonconstructivity log n from text withrespect 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430

S. Jain, F. Stephan, and T. Zeugmann

on n, we always assume n to be a power of 2. Intuitively, we then add one bit
and write the binary 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 not need the leading 1 in the help-word, since it can be addedby the IIM M . So if the help-word w has length k , then the added leading 1
with k − 1 zeros gives n and the bitstring w without the added leading 1 gives `.
Given `, the desired IIM M can nd the least indices of these ` pairwisedierent languages by using the decision function f from the proof of Theorem 1
above, where r is large enough to detect ` dierent languages.
The rest is done inductively. The IIM M checks whether or not t(0) ∈ 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. For m > 0, the IIM M then checks whether or notcontent (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, . . . , `, anddeletes all languages which fail. Then M orders the remaining sets Lrjz withrespect to set inclusion, and outputs the index of the minimal one with thesmallest index.
tu
We also have the following lower bound.

Theorem 3. There is a class C ∈ ID and an indexed hypothesis space H for itsuch that for every IIM that learns C conservatively with respect to H less thanlog n − 2 many bits of nonconstructivity are not enough.
Next, we look at strong-monotonic learning. Again the situation is more complex, since SmonTxt ⊂ ConsvTxt (cf. [20]). We 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 can be 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 encodingof 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
we have the following lower bound.

Theorem 5. There is a class C ∈ ID and an indexed hypothesis space H for
it such 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.

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

On the Amount of Nonconstructivity in Learning Formal Languages

431

Theorem 6. Let C ⊆ REG be arbitrarily xed, let d ∈ Rmon be any function,and let H = (Lj )j∈N be any indexed hypothesis space for C . Then there is acomputable IIM M such that the class C can be strong-monotonically identiedwith 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 nwith 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 number of 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 the help-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.
ψψ(2) For all pairs (i, j) with 0 < i, j ≤ n check whether or not Wi,m
\ Wj,m6= ∅.
ψψIf it is, let d(i, j) be the least element in Wi,m \ Wj,m . If there is no suchelement, we set d(i, j) = ∞.
(3) Using the numbers d(i, j) then M checks whether or not there are ` 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ψψ
4 Wk,m) for all j, k ∈ S̃ , where j < k and let s(S̃) be
xj,k =df min(Wj,mthe maximum 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 order them lexicographically and then choose the rst set S̃ in thisorder 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.
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 nited(j, i), j = i1 , . . . , i` . If there is no such i, then M (t[m]) = 0.
We have to show 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 thesymmetric di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 details.
t
u

432

S. Jain, F. Stephan, and T. Zeugmann

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.

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 withrespect to (Wiψ )i∈N+ .

The situation considerably changes if we require conservative learning. In
order to present 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, n).
n→∞Theorem 9. For every limiting recursive function h there is a recursively enu-

merable 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 .

4Conclusions

We have presented a model for the inductive inference of formal languages fromtext that incorporates a certain amount of nonconstructivity. In our model, theamount of 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 to learn any indexable class can be very small and there is no smallest
amount that can be described in a computable way (cf. Theorem 1).
Moreover, we showed upper and lower bounds for conservative learning ofindexable classes and for strong-monotonic inference roughly showing that theamount of nonconstructivity needed is log n for conservative learning and 2 log n
for strong-monotonic 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 the amount of nonconstructivity to learn all recursively enumerable
classes of recursively enumerable languages conservatively.
Acknowledgment. This research was performed partially while the third
author was visiting the Institute of 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.

On the Amount of Nonconstructivity in Learning Formal Languages

433

References[1] Angluin, D.: Finding patterns common to a set of strings. Journal of Computerand System Sciences 21(1), 4662 (1980)[2] Angluin, D.: Inductive inference of formal languages from positive data. Information and Control 45(2), 117135 (1980)[3] Barzdin, J.: Inductive inference of automata, functions and programs. In: Proc.
of the 20-th International Congress of Mathematicians, Vancouver, Canada. pp.
455460 (1974), (republished in Amer. Math. Soc. Transl. (2) 109, 1977, pages
107- 112)[4] Barzdin², J.M.: 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)[5] Beyersdor, O., Köbler, J., Müller, S.: Proof systems that take advice. Information
and Computation 209(3), 320332 (2011)[6] Cook, S., Kraji£ek, J.: Consequences of the provability of NP ⊆ P/poly . The
Journal of Symbolic Logic 72(4), 13531371 (2007)[7] Damm, C., Holzer, M.: Automata that take advice. In: Wiedermann, J., Hájek, P.
(eds.) Mathematical Foundations of Computer Science 1995, 20th International
Symposium, MFCS '95, Prague, Czech Republic, August 28 - September 1, 1995,
Proceedings. Lecture Notes in Computer Science, vol. 969, pp. 149158. Springer,
Berlin (1995)[8] Erd®s, P.: Some remarks on the theory of graphs. Bulletin of the American Mathematical Society 53(4), 292294 (1947)[9] Freivalds, R.: Amount of nonconstructivity in nite automata. In: Maneth, S.
(ed.) Implementation and Application of Automata, 14th International Conference, CIAA 2009, Sydney, Australia, July 14-17, 2009. Proceedings. Lecture Notes
in Computer Science, vol. 5642, pp. 227236. Springer, Berlin (2009)[10] Freivalds, R.: Amount of nonconstructivity in deterministic nite automata. Theoretical Computer Science 411(38-39), 34363443 (2010)[11] Freivalds, R., Zeugmann, T.: On the amount of nonconstructivity in learning
recursive functions. In: Ogihara, M., Tarui, J. (eds.) Theory and Applicationsof Models of Computation, 8th Annual Conference, TAMC 2011, Tokyo, Japan,
May 23-25, 2011, Proceedings. Lecture Notes in Computer Science, vol. 6648, pp.
332343. Springer (2011)[12] Freivalds, R., Zeugmann, T.: Colearning of recursive languages from positive
data. In: Bjørner, D., Broy, M., Potttosin, I.V. (eds.) Perspectives of System
Informatics, Second International Andrei Ershov Memorial Conference, Akademgorodok, Novosibirsk, Russia, June 1996, Proceedings. Lecture Notes in Computer
Science, vol. 1181, pp. 122133. Springer (1996)[13] Gold, E.M.: Language identication in the limit. Inform. Control 10(5), 447474(1967)[14] Jain, S., Kinber, E., Lange, S., Wiehagen, R., Zeugmann, T.: Learning languages
and functions by erasing. Theoretical Computer Science 241(1-2), 143189 (2000)[15] Jain, S., Osherson, D., Royer, J.S., Sharma, A.: Systems that Learn: An Introduction to Learning Theory, second edition. MIT Press, Cambridge, MA (1999)[16] Jain, S., Stephan, F., Zeugmann, T.: On the amount of nonconstructivity in learning formal languages from text. Tech. Rep. TCS-TR-A-12-55, Division of Computer Science, Hokkaido University (2012)

434

S. Jain, F. Stephan, and T. Zeugmann[17] Jantke, K.P.: Monotonic and non-monotonic inductive inference. New Generation
Computing 8(4), 349360 (1991)[18] Karp, R.M., Lipton, R.J.: Turing machines that take advice. L' Enseignement
Mathématique 28, 191209 (1982)[19] Lange, S., Zeugmann, T.: Types of monotonic language learning and their characterization. In: Haussler, D. (ed.) Proc. 5th Annual ACM Workshop on Computational Learning Theory. pp. 377390. ACM Press, New York, NY (1992)[20] Lange, S., Zeugmann, T.: Language learning in dependence on the space of hypotheses. In: Pitt, L. (ed.) Proceedings of the Sixth Annual ACM Conference on
Computational Learning Theory. pp. 127136. ACM Press, New York, NY (1993)[21] Lange, S., Zeugmann, T., Zilles, S.: Learning indexed families of recursive languages from positive data: A survey. Theoretical Computer Science 397(1-3), 194
232 (2008)[22] Rogers, Jr., H.: Theory of Recursive Functions and Eective Computability.
McGraw-Hill (1967), reprinted, MIT Press 1987.
[23] Zeugmann, T., Lange, S.: A guided tour across the boundaries of learning recursive
languages. In: Algorithmic Learning for Knowledge-Based Systems, Lecture Notes
in Articial Intelligence, vol. 961, pp. 190258. Springer (1995)[24] Zeugmann, T., Minato, S., Okubo, Y.: Theory of Computation. Corona PublishingCo., LTD (2009)