Intrinsic Complexity of Partial Learning

Abstract

A partial learner in the limit [16], given a representation of the target language (a text), outputs a sequence of conjectures, where one correct conjecture appears infinitely many times and other conjectures each appear a finite number of times. Following [5, 14], we define intrinsic complexity of partial learning, based on reducibilities between learning problems. Although the whole class of recursively enumerable languages is partially learnable (see [16]) and, thus, belongs to the complete learnability degree, we discovered a rich structure of incomplete degrees, reflecting different types of learning strategies (based, to some extent, on topological structures of the target language classes). We also exhibit examples of complete classes that illuminate the character of the strategies for partial learning of the hardest classes.

S. Jain—Supported in part by NUS grant numbers C252-000-087-001 and R146-000-181-112.

E. Kinber—Supported by URCG grant from Sacred Heart University.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

In his seminal paper [8], E.M. Gold introduced the framework for algorithmic learning of languages in the limit from their representations (texts), which became the standard for exploring learnability of languages in the limit (see, for example [16]). In this model (we will refer to it as $\mathbf {TxtEx}$), a learner outputs an infinite sequence of conjectures stabilizing on a correct grammar for the target language. However, Gold himself was the first one to notice that the $\mathbf {TxtEx}$ model has a strong limitation: whereas the class of all finite languages is easily learnable within this framework, no class $\mathcal{L }$ containing just one infinite language and all its finite subsets is $\mathbf {TxtEx}$-learnable. In particular, the class of all regular languages cannot be learnt in the limit just from positive data. To capture the extent to which the aforementioned class $\mathcal{L }$ would still be learnable from positive data, Osherson, Stob and Weinstein [16] introduced the concept of partial learning in the limit: a learner outputs an infinite sequence of conjectures, where one correct grammar of the target language occurs infinitely many times, whereas all other conjectures occur at most a finite number of times. The aforementioned class $\mathcal{L }$ containing an infinite recursive language L and all its finite subsets is easily learnable in this model by a simple strategy that, every time when a new datum appears on the input, conjectures a grammar for L, and conjectures some standard code for the input seen so far, otherwise. Yet, as it was noted in [16], partial learning, without any other constraints, is very powerful: the whole class of all recursively enumerable languages turns out to be partially learnable — albeit by a much more complex strategy than the one trivially learning the aforementioned class $\mathcal{L }$.

Partial learning, under various natural constraints, has attracted a lot of attention recently (see, for example, [6, 7, 9, 10, 15]). Though partial learning can be done for the whole class of recursively enumerable sets, partial learning with constraints gives interesting results. Although partial learning does not seem to be as natural as Gold’s classical model of inductive inference, one can hope that partial learning strategies for important classes of languages (like the class of regular languages) not learnable within Gold’s framework can shed new light on the general problem of learnability of such classes (and, perhaps, their important subclasses) from positive data and, possibly, additional information. For example, if a relatively simple partial learning strategy for the class of regular languages from positive data is found, one can try to look at what kind of reasonable additional information could be sufficient for converting such partial strategy to a more realistic learning strategy for this class (perhaps, it could be different from Angluin’s classical strategy for learning regular languages from membership queries and counterexamples to conjectures [2]). We hope that our paper can be a start for this line of research.

One of the potential issues is to understand exactly how partial learning happens and what is involved in it, as, at no particular instant, one can say what is the current “planned” hypothesis of the learner. To understand more about partial learning, we consider reductions between different learning problems (classes of languages). Reductions gave an interesting structure in explanatory learning (see [4, 5, 12–14]), and we hope to be able to understand much more about partial learning using reductions between different classes, which would, in some sense, highlight the ease/difficulty of partial learning of various subsets of the full class of all recursively enumerable languages.

Thus, our main goal in the current research is to find natural, yet non-$\mathbf {TxtEx}$-learnable, classes (in particular, indexed classes [1], with decidable membership problem) and — whenever it would be possible — corresponding natural partial learning strategies that would be simpler than that for the class of all recursively enumerable languages. The concept of reducibility between partial learnability problems that we introduce in this paper is based on similar models defined first for learning in the limit of classes of recursive functions in [5] and then, for $\mathbf {TxtEx}$-learnability in [14] (see also [4] for a related but different concept of complexity of learning).

A partial learnability problem (a class of languages $\mathcal{L }$) is reducible to another partial learning problem (a class of languages $\mathcal{L }'$) if there exist two computable operators, $\varTheta$ and $\varPsi$, such that (a) $\varTheta$ translates every text for a language in $\mathcal{L }$ to a text for a language in $\mathcal{L }'$ and (b) $\varPsi$ translates every sequence of conjectures where a grammar for a language $L' \in \mathcal{L }'$ occurs infinitely many times and all other conjectures occur at most a finite number of times (we will call such sequences of conjectures admissible) back to an admissible sequence of conjectures for the language $L\in \mathcal{L }$ such that some text for L is translated by $\varTheta$ to a text for $L'$. We make a distinction between strong reducibility, where $\varTheta$ translates every text for the same language in $\mathcal{L }$ to a text for the same language in $\mathcal{L }'$ and weak reducibility, where $\varTheta$ may translate different texts of the same language $L\in \mathcal{L }$ to texts of different languages in $\mathcal{L }'$. Based on this concept of reducibility, one can naturally define degrees of learnability and the complete degree (which contains the class of all recursively enumerable languages).

Firstly, we found two relatively simple and transparent classes that are complete for weak and, respectively, strong reducibilities — these classes illuminate the character of the partial learning strategies for the hardest problems. We also show (Theorem 13) that the class of all recursive languages is not strongly complete. In particular, it means that all indexed classes, including the class of all regular languages, are not strongly complete.

A major accomplishment of our research is the discovery of a rich structure of incomplete classes under the degree of the class of all regular languages — based on a number of classes representing certain natural partial learning strategies. In particular, we define the class $\mathbf {iCOINIT}$, which contains an infinite chain $L_1,L_2,\ldots$ of infinite recursive subsets of a recursive infinite language, and all their finite subsets, where, for every i, $L_{i+1}\subset L_i$. The natural strategy to learn this class, when choosing an infinite language as its conjecture, immediately finds out an upper bound on the possible number of infinite languages that may be conjectured in the future. We also define the counterpart of $\mathbf {iCOINIT}$, the class $\mathbf {iINIT}$, which also contains an enumerable, but indefinitely growing chain of infinite recursive languages and all their finite subsets. The natural learning strategy for $\mathbf {iINIT}$, when choosing an infinite language as its conjecture, also faces a bound on the number of infinite languages that can be conjectured in the future, but unlike the case of $\mathbf {iCOINIT}$, this bound is not known to the learner. We show that $\mathbf {iCOINIT}$ is weakly reducible to $\mathbf {iINIT}$ (Theorem 15), yet it is not strongly reducible to $\mathbf {iINIT}$ (Theorem 16); also, $\mathbf {iINIT}$ is not even weakly reducible to $\mathbf {iCOINIT}$ (Theorem 17).

We also introduce the class $\mathbf {iRINIT}$, which contains an infinitely growing chain of recursive languages and all their finite subsets, yet, unlike the case of $\mathbf {iINIT}$, the enumeration of members of the chain is based on the set of all rational numbers between 0 and 1. In particular, for any two infinite languages $L,L'\in \mathbf {iRINIT}$, $L\subset L'$, there is another language in $\mathbf {iRINIT}$ between L and $L'$. We show that $\mathbf {iRINIT}$ is not weakly complete (Corollary 19), yet all variants and generalizations formed using $\mathbf {iINIT}$ and $\mathbf {iCOINIT}$ (as defined in this paper) are strongly reducible to $\mathbf {iRINIT}$ (Theorem 26), and $\mathbf {iRINIT}$ is strongly reducible to none of them (Theorem 26). On the other hand, $\mathbf {iRINIT}$ itself turns out to be weakly reducible to $\mathbf {iINIT}$ (Theorem 22). $\mathbf {iRINIT}$ is also strictly under the degree of all regular languages (Theorems 18 and 24).

We also define a variant $\mathbf {iCOINIT}_k$ of $\mathbf {iCOINIT}$, which, in addition to every infinite language L in the chain, contains also all languages extending L by at most k additional elements. A natural strategy learning an infinite target language $L\in \mathbf {iCOINIT}_k$, when a new datum appears on the input, first conjectures an infinite language $M\in \mathbf {iCOINIT}$, and when up to k new elements $x\notin M$ appear on the input, conjectures appropriate finite variants of M, before moving to the next $M'$ in the chain when the number of new data not in M exceeds k. Similarly the variant $\mathbf {iINIT}_k$ is defined for $\mathbf {iINIT}$. Interestingly, though, all classes $\mathbf {iCOINIT}_k, k\ge 1$ turn out to be strongly reducible to $\mathbf {iCOINIT}_1$ and, respectively, all classes $\mathbf {iINIT}_k, k\ge 1$ are strongly reducible to $\mathbf {iINIT}_1$. Yet, surprisingly, $\mathbf {iINIT}_1$ is not strongly reducible to $\mathbf {iINIT}$ and $\mathbf {iCOINIT}_1$ is not even weakly reducible to $\mathbf {iCOINIT}$ (see Theorem 25). All these classes, though, are weakly reducible to $\mathbf {iINIT}$ (as $\mathbf {iRINIT}$ is weakly reducible to $\mathbf {iINIT}$, see above).

Lastly, based on similar multidimensional classes of languages defined in [13], one can define classes of “multidimensional” languages, where partial learning of one “dimension” aids in learning next “dimension”. For example, one can, using cylindrification, define the class $(\mathbf {iINIT}, \mathbf {iCOINIT})$, where the conjecture that is output infinitely many times for the first “dimension” can be used to partially learn the second “dimension”. We have extended this idea to any arbitrary sequence Q of $\mathbf {iINIT}$ and $\mathbf {iCOINIT}$ and have shown that if a sequence Q is a proper subsequence of $Q'$, then the class corresponding to Q is strongly reducible to the one corresponding to $Q'$, but not vice versa. Due to space constraints, results on multi-dimensional languages are not described in this paper but will be given in the full paper.

Our result on the incompleteness of any indexed class suggests that there may exist natural, relatively simple, strategies that can partially learn an indexed class. This can shed a new light on the potential of learnability of many important classes of languages from positive data.

2 Preliminaries

Any unexplained recursion theoretic notation is from [17]. ${N}$ denotes the set of natural numbers $\{0,1,2,\ldots \}$. A language is any subset of ${N}$. We let $\emptyset , \subseteq , \subset , \supseteq , \supset$ denote empty set, subset, proper subset, superset and proper superset respectively. $A \mathbf{\Delta }B$ denotes the symmetric difference of sets A and B, that is $A \mathbf{\Delta }B=(A-B) \cup (B-A)$. $\overline{L}={N}-L$ denotes the complement of L. We let $\text {card}(S)$ denote the cardinality of a set S. For $S \subseteq {N}$, let $\text {max}(S), \text {min}(S)$ respectively denote maximum and minimum of a set S, where $\text {min}(\emptyset )=\infty$ and $\text {max}(\emptyset )=0$. We sometimes use sets of rational numbers. In this case, we use $\text {max}(S)$ to denote the least upper bound of the rational numbers in the set S.

A finite set $S \subseteq {N}$ can be coded as $\mathrm{code}(S)=\sum _{x \in S} 2^x$. $D_i$ denotes the finite set A with $\mathrm{code}(A)=i$.

$\varphi$ denotes a fixed standard acceptable numbering [17]. $\varphi _i$ denotes the i-th program in the acceptable numbering $\varphi$. Let $W_i=\text {domain}({\varphi _i})$. Thus, $W_i$ is the language/set enumerated by the i-th grammar in the acceptable programming system $W_0,W_1,\ldots$. Let $\varPhi$ be a Blum complexity measure [3] for the $\varphi$ programming system. Let

Let $W_{i,s}=\text {domain}({\varphi _{i,s}})$. Intuitively, $W_{i,s+1}-W_{i,s}$ can be thought of as the elements enumerated by $W_i$ in $(s+1)$-th step. For purposes of this paper, one can assume without loss of generality that $W_{i,s+1}-W_{i,s}$ contains at most one element.

$\mathcal{R}$ denotes the class of all recursive languages. $\mathcal{E}$ denotes the class of all recursively enumerable sets.

An indexed family is a family $(L_i)_{i \in {N}}$ of languages such that there exists a recursive function f uniformly deciding the membership question for $L_i$, that is, for all i, x, $f(i,x)=1$ iff $x \in L_i$.

Let $\langle \cdot ,\cdot \rangle$ denote a fixed recursive bijection from ${N}\times {N}$ to ${N}$. $\langle \cdot ,\cdot \rangle$ can be extended to pairing of n-ary tuples by taking $\langle x_1,x_2,\ldots ,x_n \rangle =\langle x_1,\langle x_2,\ldots ,x_n \rangle \rangle$. For notation convenience we let $\langle x \rangle =x$. Let $\pi _i^n(\langle x_1,x_2,\ldots ,x_n \rangle )=x_i$, where we drop the superscript in case $n=2$.

Let $pad(\cdot ,\cdot )$ be a 1–1 recursive function, increasing in both its arguments, such that for all i and j, $\varphi _{pad(i,j)}=\varphi _i$. Note that there exists such a padding function $pad$ (see [17]).

$RAT_{0,1}$ denotes the set of rational numbers between 0 and 1 (both inclusive). Let ${\text {ntor}}$ be a recursive bijection from ${N}$ to $RAT_{0,1}$. Let ${\text {rton}}$ be the inverse of ${\text {ntor}}$. Left r.e. real means a real number which is approximable from below using rational numbers enumerated by a recursive procedure. That is, a real number r is called a left r.e. real iff there exists a recursive function f mapping ${N}$ to the set of rational numbers such that: for all i, $f(i) \le f(i+1)$, and $\lim _{i \in {N}} f(i)=r$.

We now give some concepts from language learning theory. Let $\#$ be a special pause symbol. A finite sequence $\sigma$ is a mapping from an initial segment of ${N}$ to $({N}\cup \{\#\})$. Let ${\varLambda }$ denote the empty sequence. $SEQ$ denotes the set of all finite sequences. A text is a mapping from ${N}$ to $({N}\cup \{\#\})$. Let $|\sigma |$ denote the length of sequence $\sigma$. Let T[n] denote the initial segment of length n of the text T. For $n \le |\sigma |$, $\sigma [n]$ denotes the initial segment of length n of the sequence $\sigma$. The concatenation of sequences $\sigma$ and $\tau$ is denoted by $\sigma \diamond \tau$. The content of T, denoted $\text {content}(T)$, is the set of the numbers in the range of T, that is, $\{T(n) :n \in {N}\}-\{\#\}$. Let $\text {content}(\sigma )$ be defined similarly. We say that T is a text for a language L iff $\text {content}(T)=L$.

A language learning machine is a partial computable function which maps $SEQ$ to ${N}$. We let $\mathbf {M}$, with or without decorations, range over learning machines.

Definition 1

[16]

• (a) $\mathbf {M}$ $\mathbf {Part}$-learns L iff for all texts T for L,

  • (i) for all n, $\mathbf {M}$ is defined on T[n],

  • (ii) there exists a unique p such that $p=\mathbf {M}(T[n])$ for infinitely many n, and

  • (iii) for p as in (ii) above, $W_p=L$.

• (b) $\mathbf {M}$ $\mathbf {Part}$-learns a class $\mathcal{L }$ iff it $\mathbf {Part}$-learns each $L \in \mathcal{L }$.

• (c) $\mathbf {Part}=\{\mathcal{L }:(\exists \mathbf {M})[\mathbf {M}$ $\mathbf {Part}$-learns $\mathcal{L }\}$.

It can be shown that $\mathcal{E}$ is $\mathbf {Part}$-learnable [16]. If $\mathbf {M}$ $\mathbf {Part}$-learns a class $\mathcal{L }$ then we say that $\mathbf {M}$ witnesses $\mathbf {Part}$-learnability of $\mathcal{L }$. If an infinite sequence $p_0p_1\ldots$ satisfies the following two requirements:

• (i) there exists a unique p such that $p=p_n$ for infinitely many n, and

• (ii) for p as in (i) above, $W_p=L$,

then, we say that the sequence $p_0p_1\ldots$ witnesses $\mathbf {Part}$-learnability of L.

An enumeration operator (or just operator) $\varTheta$ is an algorithm mapping from $SEQ$ to $SEQ$ such that for all $\sigma , \tau \in SEQ$, if $\sigma \subseteq \tau$, then $\varTheta (\sigma ) \subseteq \varTheta (\tau )$. We let $\varTheta (T)=\bigcup _{n \in {N}} \varTheta (T[n])$.

We further assume that $\lim _{n \rightarrow \infty } |\varTheta (T[n])|=\infty$, that is texts are mapped to texts by the operator $\varTheta$. Note that any operator $\varTheta$ can be modified to satisfy the above property without violating the content of its output on infinite texts.

We will also use $\varTheta$ as an operator on languages (rather than individual texts representing them, as above). Note that, in general, for different texts $T,T'$ of a language L, $\varTheta$ may produce texts $\varTheta (T)$ and $\varTheta (T')$ of different languages. Thus, we define $\varTheta (L)$ as a collection of languages: $\varTheta (L)=\{\text {content}(\varTheta (T)) :T$ is a text for $L\}$, and, accordingly, the image $\varTheta (\mathcal{L })=\bigcup _{L \in \mathcal{L }} \varTheta (L)$. In the special case (important for our strong reductions, defined below), when $\varTheta (L)$ is a singleton $\{L'\}$, we abuse notation and say simply $\varTheta (L)=L'$. (Note that if $\varTheta (L)=\{L'\}$, then $L'= \bigcup _{\sigma : \text {content}(\sigma ) \subseteq L} \text {content}(\varTheta (\sigma ))$).

We let $\varTheta$ and $\varPsi$ range over operators, where for ease of notation, we assume that for $\varPsi$ the input and output sequences contain only elements of ${N}$ (and thus do not contain $\#$). We view $\varPsi$ as mapping sequences of grammars to sequences of grammars. Again, as in the definition of operator $\varTheta$, we assume that $\varPsi$ maps infinite sequences to infinite sequences. This can be easily done without changing the set of grammars which appear infinitely often in the sequence.

The following two definitions are based on the corresponding reductions for explanatory function learning [5] and explanatory language learning [14]. In these definitions, we view operators $\varTheta$ as mapping texts to texts, as well as mapping languages to collections of languages (as discussed above).

Definition 2

We say that $\mathcal{L }\le ^{\mathrm{W}{eak}}_{\mathbf {Part}} \mathcal{L }'$ iff there exist operators $\varTheta$ and $\varPsi$ such that

• (a) for all $L \in \mathcal{L }$, $\varTheta (L) \subseteq \mathcal{L }'$.

• (b) for all $L \in \mathcal{L }$, for all $L' \in \varTheta (L)$, if $p_0p_1\ldots$ is a sequence witnessing $\mathbf {Part}$-learnability of $L'$, then $\varPsi (p_0p_1\ldots )$ witnesses $\mathbf {Part}$-learnability of L.

Intuitively, $\varTheta$ reduces a text for a language $L \in \mathcal{L }$ to a text for a language $L' \in \mathcal{L }'$. $\varPsi$ then converts sequences witnessing $\mathbf {Part}$-learnability of $L'$ to sequences witnessing $\mathbf {Part}$-learnability of L.

However, as we noted above, different texts for L may be mapped by $\varTheta$ to texts for different languages in $\mathcal{L }'$. If we require that the mapping should be to the texts of the same language, then we get strong reduction.

Definition 3

We say that $\mathcal{L }\le ^{\mathrm{S}{trong}}_{\mathbf {Part}} \mathcal{L }'$, iff there exist operators $\varTheta$ and $\varPsi$ such that

• (a) $\varTheta$ and $\varPsi$ witness that $\mathcal{L }\le ^{\mathrm{W}{eak}}_{\mathbf {Part}} \mathcal{L }'$ and

• (b) for all $L \in \mathcal{L }$, $\text {card}(\varTheta (L))=1$.

For ease of notation, when considering strong reductions, as discussed above, we consider $\varTheta$ as directly mapping languages to languages, rather than considering it as a mapping from languages to a set containing just one language.

We say that $\mathcal{L }<^{\mathrm{W}{eak}}_{\mathbf {Part}} \mathcal{L }'$ if $\mathcal{L }\le ^{\mathrm{W}{eak}}_{\mathbf {Part}} \mathcal{L }'$ but $\mathcal{L }' \not \le ^{\mathrm{W}{eak}}_{\mathbf {Part}} \mathcal{L }$. Similarly, $\mathcal{L }\equiv ^{\mathrm{W}{eak}}_{\mathbf {Part}}$ if $\mathcal{L }\le ^{\mathrm{W}{eak}}_{\mathbf {Part}} \mathcal{L }'$ and $\mathcal{L }' \le ^{\mathrm{W}{eak}}_{\mathbf {Part}} \mathcal{L }$.

Similarly, we can define $\mathcal{L }<^{\mathrm{S}{trong}}_{\mathbf {Part}} \mathcal{L }'$ and $\mathcal{L }\equiv ^{\mathrm{S}{trong}}_{\mathbf {Part}} \mathcal{L }'$.

Definition 4

We say that $\mathcal{L }$ is $\le ^{\mathrm{W}{eak}}_{\mathbf {Part}}$-complete if

• (a) $\mathcal{L }\in \mathbf {Part}$ and

• (b) For all $\mathcal{L }' \in \mathbf {Part}$, $\mathcal{L }' \le ^{\mathrm{W}{eak}}_{\mathbf {Part}} \mathcal{L }$.

$\le ^{\mathrm{S}{trong}}_{\mathbf {Part}}$-completeness can be defined similarly.

We now define some languages and classes which are often used in the paper. We used the names $\mathbf {iINIT}$, $\mathbf {iCOINIT}$, $\mathbf {iRINIT}$ for the classes defined below as the infinite languages in these classes are obtained by cylindrification of the languages in ${INIT}$, ${COINIT}$ and ${RINIT}$ used in the literature (the class ${INIT}$ contains languages $\{1,2,\ldots ,i\}$ and ${COINIT}$ contains languages $\{i,i+1,i+2,\ldots \}$; ${RINIT}$ is similar to ${INIT}$ and contains, for each $r \in R_{0,1}$, the language having (the representatives of) rational numbers below r). Additionally the classes $\mathbf {iINIT}, \mathbf {iCOINIT}, \mathbf {iRINIT}$ contain all the finite languages. For $i \in {N}, r \in RAT_{0,1}$,

• (a) ${INIT}_i=\{\langle x,y \rangle :x,y \in {N}$ and $x \le i\}$,

• (b) ${COINIT}_i=\{\langle x,y \rangle :x,y \in {N}$ and $x \ge i\}$,

• (c) ${RINIT}_r=\{\langle x,y \rangle :x,y \in {N}$ and ${\text {ntor}}(x) \le r\}$,

• (d) ${INIT}_{i,s}=D_s \cup {INIT}_i$,

• (e) ${COINIT}_{i,s}=D_s \cup {COINIT}_i$,

• (f) $\mathcal{FIN}=\{L :L$ is finite$\}$,

• (g) $\mathbf {iINIT}=\{{INIT}_i :i \in {N}\} \cup \mathcal{FIN}$,

• (h) $\mathbf {iCOINIT}=\{{COINIT}_i :i \in {N}\} \cup \mathcal{FIN}$,

• (i) $\mathbf {iRINIT}=\{{RINIT}_r :r \in RAT_{0,1}\} \cup \mathcal{FIN}$,

• (j) $\mathbf {iINIT}_k=\mathbf {iINIT}\cup \{{INIT}_{i,s} :\text {card}(D_s) \le k, i \in {N}\}$,

• (k) $\mathbf {iCOINIT}_k=\mathbf {iCOINIT}\cup \{{COINIT}_{i,s} :\text {card}(D_s) \le k, i \in {N}\}$.

A natural partial learning strategy for the languages in $\mathbf {iINIT}$ is as follows: when a new datum $\langle j,x \rangle$, where j is larger than all m for all pairs $\langle m,y \rangle$ seen so far, appears on the input, the learner, for the first time, outputs the conjecture ${INIT}_j$. Now, as long as no new (not previously seen) datum appears on the input, the learner conjectures the finite set representing the input seen so far; if a new datum (not previously seen) from ${INIT}_j$ appears on the input, the learner repeats the conjecture ${INIT}_j$. This continues as long as no datum outside ${INIT}_j$ is seen. Clearly, the correct language ${INIT}_j$ or some finite input set is the only one that will be conjectured infinite number of times. A similar strategy works for $\mathbf {iRINIT}$.

For $\mathbf {iCOINIT}$ a similar strategy chooses a new infinite conjecture ${COINIT}_j$ when a new pair $\langle j,x \rangle$, where j is smaller than all m for all pairs $\langle m,y \rangle$ seen so far, appears on the input. Otherwise, the strategy is identical to the one for $\mathbf {iINIT}$.

For $\mathbf {iINIT}_k$ the above $\mathbf {iINIT}$-learning strategy can be adjusted as follows: the learner keeps track of the smallest j such that the set $E=\{\langle x,y \rangle :x >j$ and $\langle x,y \rangle$ is seen in the input so far$\}$ has at most k elements. Then, the strategy for learning $\mathbf {iINIT}_k$ is similar to that of $\mathbf {iINIT}$, except that whenever the strategy for $\mathbf {iINIT}$ outputs an infinite conjecture, strategy for $\mathbf {iINIT}_k$ outputs an infinite conjecture for ${INIT}_{j,s}$, where $D_s=E$, where j, E are as described above. Similar modification to the strategy for $\mathbf {iCOINIT}$ works for $\mathbf {iCOINIT}_k$.

3 Basic Properties of Reductions

In this section, we establish a number of technical facts used in many proofs of our results.

Lemma 5

Suppose $\varTheta$ witnesses part (a) of Definition 2 for $\mathcal{L }\le ^{\textit{weak}}_{\mathbf {Part}} \mathcal{L }'$. Suppose $F_1,F_2$ are computable functions such that, for any $L \in \mathcal{L }$ and $L' \in \varTheta (L)$, the following three properties hold:

• (i) if $L'$ is finite, then $F_1(L')$ is a grammar for L.

• (ii) if $L'$ is infinite and p is a grammar for $L'$, then $\lim _{t \rightarrow \infty } F_2(p,t)$ exists and is a grammar for L.

• (iii) if $L'$ is infinite, then for any sequence of finite sets $S_1,S_2, \ldots$ such that $S_0 \subset S_1 \subset S_2 \ldots$ and $\bigcup _{i\in {N}} S_i=L'$, for all t, for all but finitely many $t'$, $F_1(S_t) \ne F_1(S_{t'})$.

Then, there exists a $\varPsi$ such that, for all $L \in \mathcal{L }$, for any sequence of grammars $p_0p_1\ldots$ witnessing $\mathbf {Part}$-learnability of $L' \in \varTheta (L)$, $\varPsi (p_0p_1\ldots )=q_0q_1\ldots$ witnesses $\mathbf {Part}$-learnability of L.

The above lemma is useful in simplifying the construction of $\varPsi$ in many of the proofs: we can just give the relevant $F_1$ and $F_2$.

Proposition 6

There exists an operator $\varPsi$ such that for any sequence $q_0q_1\ldots$, $\varPsi (q_0q_1\ldots )=q_0'q_1',\ldots$ such that:

• (a) at most one grammar appears in $q_0'q_1'\ldots$ infinitely often,

• (b) if q is the least grammar which appears infinitely often in $q_0q_1\ldots$, then $q'$ appears infinitely often in $q_0'q_1'\ldots$, where $W_{q'}=W_q$.

Proof

Let $q_i'=pad(q_i,j)$, where $j=\text {card}(\{i' :i' \le i$ and $q_{i'} < q_i \})$. It is easy to verify that the above sequence satisfies the requirements of the proposition.    $\blacksquare$

The above proposition is useful to simplify some of the constructions for $\varPsi$ in our proofs.

Proposition 7

Suppose $\mathcal{L }\le ^{weak}_{\mathbf {Part}} \mathcal{L }'$ as witnessed by $\varTheta$ and $\varPsi$. Then, for all distinct $L, L' \in \mathcal{L }$, $\varTheta (L) \cap \varTheta (L')=\emptyset$.

Proposition 8

For any operator $\varTheta$, if $L \subseteq L'$, $\varTheta (L)=\{X\}$ and $\varTheta (L')=\{X'\}$, then $X \subseteq X'$.

Proposition 9

Suppose L is infinite and $\mathcal{L }$ contains L and all finite subsets of L. Suppose further that $\mathcal{L }\le ^{weak}_{\mathbf {Part}} \mathcal{L }'$ as witnessed by $\varTheta$ and $\varPsi$. Then, for all finite sets S such that $S \subseteq L'$ for some $L' \in \varTheta (L)$, there exists an infinite superset of S in $\varTheta (L)$ (in particular, $\varTheta (L)$ contains an infinite language).

4 Complete Classes and the Class $\mathcal{R}$

As $\mathcal{E}\in \mathbf {Part}$, we trivially have that $\mathcal{E}$ is $\le ^{\mathrm{S}{trong}}_{\mathbf {Part}}$-complete. The following results give some simple classes which are complete.

Let $\mathbf {iCOINIT}_*=\{{COINIT}_i \cup A :i \in {N}$ and A is finite$\}$. We first show that every text for every recursively enumerable language can be appropriately “encoded” as a text for some language in $\mathbf {iCOINIT}_*$ — thus showing that $\mathbf {iCOINIT}_*$ is weakly complete.

Theorem 10

$\mathbf {iCOINIT}_*$ is $\le ^{weak}_{\mathbf {Part}}$-complete.

Proof. To show that $\mathcal{E}\le ^{weak}_{\mathbf {Part}} \mathbf {iCOINIT}_*$, define $\varTheta$ and $\varPsi$ as follows.

Suppose T is a given text. Let $C_{p,T}=\text {max}(\{t :W_{p,t} \subseteq \text {content}(T)$ and $\text {content}(T[t]) \subseteq W_p\})$. Note that $C_{p,T}$ can be approximated from below (that is, there exists a recursive function f such that $f(p,T[n]) \le f(p,T[n+1]) \le C_{p,T}$ and $\lim _{n \rightarrow \infty } f(p,T[n])=C_{p,T}$.

Define $\varTheta$ as follows. $\varTheta (T)=T'$ such that $\text {content}(T')=\{\langle q,x \rangle :(\exists q' \le q)[x \le C_{q',T}]\}$.

Now, suppose p is the least grammar for $W_p$, T is a text for $W_p$, and $T'=\varTheta (T)$. Then, it is easy to verify that $\text {content}(T')={COINIT}_{p,s}$, for some s, as $C_{p,T}=\infty$, but $C_{p',T}<\infty$ for $p'<p$.

We define $\varPsi '$ as follows.

$\varPsi '(p_0p_1\ldots )=q_0q_1\ldots$, where

$q_i= pad(j,p_i)$, where, for some x, $\langle j,x \rangle$ is the last new element enumerated in $W_{p_i,k}$ and k is the number of times $p_i$ appears in $p_0p_1\ldots p_i$.

Claim 11

Suppose $L \in \mathcal{E}$, and $L' \in \varTheta (L)$.

If $p_0p_1 \ldots$ witnesses $\mathbf {Part}$-learnability of $L'$, then $q_0q_1 \ldots$ is a sequence satisfying:

there exists a minimal q such that q appears infinitely often in $q_0q_1\ldots$ and this $q=pad(j,p)$, for minimal grammar j for L and some p.

To see the claim, suppose $L' \in \varTheta (L)$ and $p_0,p_1 \ldots$ is a sequence witnessing $\mathbf {Part}$-learnability of $L'$ and $\varPsi '(p_0p_1\ldots )=q_0q_1\ldots$. Suppose p is the only grammar which appears infinitely often in $p_0p_1\ldots$. Then only $q_i$ with $p_i=p$ can possibly appear infinitely often in the sequence $q_0q_1\ldots$ as $q_i$ used $p_i$ in its padding. Furthermore, $pad(j,p)$, with $j \ge \text {min}(\{e:W_e=L\})$ appear infinitely often in the sequence $q_0q_1\ldots$. The claim follows.

Now the theorem follows using Proposition 6.    $\blacksquare$

We now consider a $\le ^{\mathrm{S}{trong}}_{\mathbf {Part}}$-complete class.

Let $V(L)=\frac{1}{4}+\sum _{x \in L} 4^{-x-1}$.

Intuitively, V maps languages to real numbers where the mapping is monotonic in L. Furthermore, if $L \ne L'$ and $\text {min}(L \mathbf{\Delta }L') \in L$, then $V(L) > V(L')$.

The reason for choosing the additive part “$\frac{1}{4}$” is just to make sure that V(L) is non-zero.

Let $L_{r_0,r_1,\ldots ,r_k} =\{\langle i,x \rangle :i< k \text{ and } {\text {ntor}}(x) < r_i$ or $i \ge k \text{ and } {\text {ntor}}(x) < r_k\}$.

Let $\mathcal{STRCOMP}=\{L_{r_0,r_1,\ldots ,r_k} :k \in {N}, r_0 \le r_1 \le \ldots \le r_k$, and $r_0,r_1,\ldots ,r_k$ are left r.e. reals$\}$.

$\mathcal{STRCOMP}$ denotes “strong complete class”. The languages in $\mathcal{STRCOMP}$ can be thought of as follows: in the i-th cylinder we keep rational numbers $< r_i$. The $r_i$’s are monotonically non-decreasing left r.e. real numbers and the sequence $r_0,r_1,\ldots$ converges (that is, for some k, for all $i \ge k$, $r_i=r_k$). We suggest the reader to contrast this class with the previously defined class $\mathbf {iRINIT}$ (which, in the sequel, will be shown to be incomplete).

Theorem 12

$\mathcal{STRCOMP}$ is $\le ^{Strong}_{\mathbf {Part}}$-complete.

Proof

For any index i and any language L, let

$X_{i,L}= \{\frac{x}{y} :x,y \in {N}, y \ne 0, \frac{x}{y} < V(W_i \cap L)$ and $x,y \le \text {min}(\{t:W_{i,t}-L \ne \emptyset \})\}$.

Intuitively, $sup(X_{i,L})$ gives a value to how much $W_i$ and L are similar to each other:

• (P1) If $W_i=L$, then $sup(X_{i,L})$ is V(L) (as $\text {min}(\{t:W_{i,t}-L \ne \emptyset \})$ is infinite).

• (P2) If $W_i \ne L$, then $sup(X_{i,L}) < V(L)$. To see this note that if $L \not \subseteq W_i$, then clearly $V(W_i \cap L) < V(L)$ and thus $sup(X_{i,L}) \le V(W_i \cap L) < V(L)$. On the other hand, if $W_i \not \subseteq L$, then $sup(X_{i,L}) < V(W_i \cap L) \le V(L)$, as $X_{i,L}$ is a finite set and the supremum of a finite set of rational numbers $<r$ is $<r$ for any positive real number r.

Note that $X_{i,L}$ depends only on i and L and not on the particular presentation of L. This allows us to construct $\varTheta$ (and corresponding $\varPsi$) which give a strong reduction from $\mathcal{E}$ to $\mathcal{STRCOMP}$.

$\varTheta (L)= \bigcup _{i \in {N}} [\{ \langle i,y \rangle :(\exists i' \le i) (\exists s \in X_{i',L})[{\text {ntor}}(y) \le s]\}]$.

Intuitively, $\varTheta$ just collects all the members of $X_{i,L}$ in the i-th cylinder and then does an upward closure.

Note that $\varTheta (L)$ can be enumerated from a text T for L. Moreover, $\varTheta (L)$ depends only on L and not on the particular presentation T, and thus the reduction is a strong reduction.

We say that m improves at time step j in the enumeration of $W_p$, if, for some x, the following two conditions are satisfied:

• (i) $\langle m,x \rangle$ gets enumerated at time step j in $W_p$.

• (ii) Suppose $j'<j$ is the largest earlier time step when m improved, if any, in the enumeration of $W_p$ (take $j'=0$, if m did not improve earlier). Then, for any y such that $\langle m',y \rangle \in W_{p,j'}$, ${\text {ntor}}(x)>{\text {ntor}}(y)$.

Note that for any grammar p for $L' = L_{r_0,r_1,\ldots ,r_k}$, with $r_0 \le r_1 \le r_2 \ldots \le r_{k-1} < r_k$, k improves at infinitely many steps j in the enumeration of $W_p$, but $0,1,\ldots ,k-1$ improve only for finitely many steps j in the enumeration of $W_p$.

We define an operator $\varPsi '$ as follows. This can then be converted to the desired $\varPsi$ using Proposition 6. $\varPsi '(p_0p_1\ldots )=q_0q_1\ldots$, where $q_i$ is defined below. Note that if $L \in \mathcal{E}$, $\varTheta (L)=L'$ and $p_0,p_1,\ldots$ witnessed $\mathbf {Part}$-learning of $L'$, then we want $\varPsi (p_0p_1\ldots )$ to witness $\mathbf {Part}$-learning of L.

Without loss of generality assume that, for any k, $W_k$ enumerates at most one element at any step. For any fixed i, suppose $p_i$ appears j times in $p_0p_1\ldots p_i$, and $m_i$ improves at step j in the enumeration of $W_{p_i}$ (if no such $m_i$ exists, then take $m_i$ to be $i+1$). Then, let $q_i=pad(m_i,p_i)$.

Now suppose $L \in \mathcal{E}$ and $L'=\varTheta (L)$ and i is the minimal grammar for L. Then, by the properties (P1) and (P2), for all $j <i$, $sup(X_{i,L}) > sup(X_{j,L})$, and for all $j \ge i$, $sup(X_{i,L}) \ge sup(X_{j,L})$. Thus, $L'$ is of the form $L_{r_0,r_1,\ldots ,r_i}$, where $r_0 \le r_1 \le r_{i-1}<r_i$.

Now, suppose p appears infinitely often in $p_0p_1\ldots$, which witnesses $\mathbf {Part}$-learnability of $L'$. Then for $\varPsi '(p_0p_1\ldots )=q_0q_1\ldots$ only $q_j$ with $p_j=p$ could possibly appear infinitely often in the sequence $q_0q_1\ldots$ as $q_j$ used $p_j$ in its padding. Furthermore, i is the minimal number which improves at infinitely many steps in the enumeration of $W_p$. It follows that $pad(i,p)$ is the minimal element which appears infinitely often in the sequence $q_0 q_1\ldots$.

Now $\varPsi '$ can be converted to the required $\varPsi$ using Proposition 6. The theorem follows.    $\blacksquare$

Our next result states that the class $\mathcal{R}$ of all recursive languages is not strongly complete. In particular, this means that all indexed classes of languages, including the class of all regular languages, are incomplete. This opens a possibility of creating partial learning strategies for these classes that would be simpler than the general strategy for partial learning of all recursively enumerable languages.

Theorem 13

$\mathcal{R}$ is not $\le ^{Strong}_{\mathbf {Part}}$-complete.

Proof

Suppose $\varTheta$ (and $\varPsi$) witness that $\mathcal{E}\le _{\mathbf {Part}}^{\mathrm{S}{trong}} \mathcal{R}$. Let K denote the halting set $\{i :i \in {N}$ and $\varphi _i(i)\downarrow \}$. Now, by Propositions 7 and 8, for all x, $\varTheta (K) \subset \varTheta (K \cup \{x\})$. Let $S=\varTheta (K)$. Note that, by assumption, S is recursive. Now, $x \in K$ iff $\varTheta (\{x\} \cup K) \subseteq S$. As S is recursive, this would imply that $\overline{K}$ is recursively enumerable, which is in contradiction to a known fact that K is not recursively enumerable [17].    $\blacksquare$

5 Relationship Between $\mathbf {iINIT}$, $\mathbf {iCOINIT}$ and $\mathbf {iRINIT}$ Classes

In this section, we explore the relationships between the classes $\mathbf {iINIT}$, $\mathbf {iCOINIT}$ (and some of their variants), and $\mathbf {iRINIT}$. We also establish that their degrees are strictly under the degree of all regular languages.

Proposition 14

Fix $n \in {N}$. Suppose $\mathcal{L }\subseteq \mathcal{E}$ contains only n infinite languages. Then,

• (a) $\mathcal{L }\le ^{Strong}_{\mathbf {Part}} \mathbf {iINIT}$.

• (b) $\mathcal{L }\le ^{Strong}_{\mathbf {Part}} \mathbf {iCOINIT}$.

First, we explore the relationship between $\mathbf {iINIT}$ and $\mathbf {iCOINIT}$. We begin with establishing that $\mathbf {iCOINIT}$ is reducible to $\mathbf {iINIT}$, but only weakly. Perhaps, this fact and the fact that $\mathbf {iINIT}$ is not reducible to $\mathbf {iCOINIT}$ (see below) are not surprising, as the chain of infinite languages in $\mathbf {iINIT}$ is growing indefinitely, whereas every growing chain of infinite languages in $\mathbf {iCOINIT}$ is finite.

Theorem 15

$\mathbf {iCOINIT}\le ^{\textit{weak}}_{\mathbf {Part}}\mathbf {iINIT}$.

Theorem 16

$\mathbf {iCOINIT}\not \le ^{Strong}_{\mathbf {Part}} \mathbf {iINIT}$.

On the other hand, $\mathbf {iINIT}$ is not reducible to $\mathbf {iCOINIT}$ even weakly.

Theorem 17

$\mathbf {iINIT}\not \le ^{\textit{weak}}_{\mathbf {Part}} \mathbf {iCOINIT}$.

The class $\mathbf {iRINIT}$ is similar to $\mathbf {iINIT}$ in that it features an infinitely growing chain of infinite languages. However, unlike $\mathbf {iINIT}$, between any two infinite languages in $\mathbf {iRINIT}$, there is always another language. We show that the $\le _{\mathbf {Part}}^{\mathrm{S}{trong}}$-degree of $\mathbf {iRINIT}$ is strictly above the degrees of the classes $\mathbf {iINIT}$ and $\mathbf {iCOINIT}$. However, first we show that $\mathbf {iRINIT}$ is not even weakly complete. Let $\mathcal{REG}$ denote the class of all regular sets [11] (we assume some standard recursive bijection between strings and ${N}$, so that regular sets can be considered as subsets of natural numbers). Topologically, $\mathcal{REG}$ is much more complex than containing just one growing chain of infinite languages $\mathbf {iRINIT}$ (plus finite sets), and this translates into greater complexity of partial learning of $\mathcal{REG}$, as the following theorem indicates.

Theorem 18

$\mathcal{REG}\not \le ^{\textit{weak}}_{\mathbf {Part}} \mathbf {iRINIT}$.

Proof

Suppose by way of contradiction that $\varTheta$ and $\varPsi$ witness that $\mathcal{REG}\le ^{\mathrm{W}{eak}}_{\mathbf {Part}} \mathbf {iRINIT}$.

Inductively define $\sigma _i$ as follows.

$\sigma _0={\varLambda }$.

$\sigma _{i+1}$ is an extension of $\sigma _i \diamond i$ such that $\text {max}(\{{\text {ntor}}(x):\langle x,y \rangle \in \varTheta (\sigma _{i+1})\}) > \text {max}(\{{\text {ntor}}(x) :\langle x,y \rangle \in \varTheta (\sigma _i)\})$.

If all $\sigma _{i+1}$ get defined, then for $T=\bigcup _{i \in {N}} \sigma _i$, T is a text for ${N}$ (which is regular), but $sup(\{{\text {ntor}}(x):\langle x,y \rangle \in \text {content}(\varTheta (T))\})$ does not belong to $\{{\text {ntor}}(x) :\langle x,y \rangle \in \text {content}(\varTheta (T))\}$ (as if it belonged, then it would belong to $\{{\text {ntor}}(x) :\langle x,y \rangle \in \text {content}(\varTheta (\sigma _j))\}$, for some j, and that would violate the definitions of $\sigma _i$’s).

If some $\sigma _{i+1}$ does not get defined, then let $r=\text {max}(\{{\text {ntor}}(x) :\langle x,y \rangle \in \text {content}(\varTheta (\sigma _i))\})$. Now, for all infinite regular languages L containing $\text {content}(\sigma _i)$, ${RINIT}_r \in \varTheta (L)$ (as $\varTheta (L)$ contains an infinite language containing $\langle {\text {rton}}(r),y \rangle$, for some y, and $\sigma _{i+1}$ did not get defined). A contradiction to Proposition 7, as there are infinitely many (in particular at least two) infinite regular languages which contain $\text {content}(\sigma _i)$.    $\blacksquare$

Corollary 19

$\mathbf {iRINIT}$ is not $\le ^{weak}_{\mathbf {Part}}$-complete.

Our next result shows that both $\mathbf {iINIT}$ and $\mathbf {iCOINIT}$ are strongly reducible to $\mathbf {iRINIT}$. Let $0<r_0,r_1,\ldots$ in $RAT_{0,1}$ be a strictly increasing sequence of rational numbers. $\{{INIT}_i :i \in {N}\}$ can be naturally embedded into $\mathbf {iRINIT}$, by mapping ${INIT}_i$ to ${RINIT}_{r_i}$. Note that, by our convention on coding of finite sets, $D_s \subset D_{s'}$ implies $s < s'$. For any s, let $k_s=\text {max}(\{x :\langle x,y \rangle \in D_s\})$. Now, mapping finite sets $D_s$ to ${RINIT}_{r_{k_s}+(r_{{k_s}+1}-r_{k_s})*r_s}$ ensures that $\mathbf {iINIT}\le ^{\mathrm{S}{trong}}_{\mathbf {Part}} \mathbf {iRINIT}$. A similar method works to show that $\mathbf {iCOINIT}\le _{\mathbf {Part}}^{\mathrm{S}{trong}} \mathbf {iRINIT}$.

Theorem 20

 

• (a) $\mathbf {iINIT}\le ^{Strong}_{\mathbf {Part}} \mathbf {iRINIT}$.

• (b) $\mathbf {iCOINIT}\le ^{Strong}_{\mathbf {Part}} \mathbf {iRINIT}$.

Next we show that $\mathbf {iRINIT}$ is neither strongly reducible to $\mathbf {iINIT}$, nor even weakly reducible to $\mathbf {iCOINIT}$. Yet, it is weakly reducible to $\mathbf {iINIT}$. The latter fact is quite interesting: every text for a language in $\mathbf {iRINIT}$ can be encoded as a text for a language in $\mathbf {iINIT}$, yet the corresponding languages in $\mathbf {iINIT}$ for such texts may be different for different texts of the same language in $\mathbf {iRINIT}$.

Theorem 21

$\mathbf {iRINIT}\not \le ^{Strong}_{\mathbf {Part}} \mathbf {iINIT}$.

Proof

Suppose by way of contradiction otherwise, as witnessed by $\varTheta$ and $\varPsi$. Note that, by Proposition 9, $\varTheta ({RINIT}_{0.2})$ cannot be a finite set. Suppose $\varTheta ({RINIT}_{0.2})={INIT}_k$.

Then for two different values of $r<0.2$, $\varTheta ({RINIT}_r)={INIT}_i$, for same i, as for all $r<0.2$, $\varTheta ({RINIT}_r) \subseteq {INIT}_k$. A contradiction.    $\blacksquare$

Theorem 22

$\mathbf {iRINIT}\le ^{weak}_{\mathbf {Part}} \mathbf {iINIT}$.

Proof

Let $r_S=\text {max}(\{{\text {ntor}}(x) :\langle x,y \rangle \in S\})$. Define $m_{T[n]}$ as follows.

• (i) $m_{{\varLambda }}=\langle rton(0),0 \rangle$.

• (ii) $m_{T[n+1]}=m_{T[n]}$, if $r_{\text {content}(T[n+1])}=r_{\text {content}(T[n])}$; otherwise $m_{T[n+1]}=\langle rton(r_{\text {content}(T[n+1])}),m_{T[n]}+1 \rangle$.

Now, let $\varTheta (T[n])=\{\langle x,y \rangle :x \le m_{T[n]}, y \le \mathrm{code}(\text {content}(T[n]))\}$.

It is easy to verify that,

• (1) For a finite set L, $\varTheta (L) \subseteq \{ \{\langle x,y \rangle :x \le i, y \le \mathrm{code}(L)\} :i \in {N}\}$.

• (2) $\varTheta ({RINIT}_{r}) \subseteq \{{INIT}_{\langle {\text {rton}}(r),w \rangle } :w \in {N}\}$.

We can define the operator $\varPsi$ for the reduction using Lemma 5, where $F_1$ and $F_2$ are defined as follows.

$F_1(S)=$ canonical grammar for $D_w$, where $w=\text {max}(\{y :\langle 0,y \rangle \in S\})$.

$F_2(p,t)=$ canonical grammar for ${RINIT}_{{\text {ntor}}(j)}$, where, for some w, $\langle j,w \rangle =\text {max}(\{x :\langle x,y \rangle \in W_{p,t}\})$.

It is now easy to verify using Lemma 5 that $\varTheta$ and $\varPsi$ (as given by Lemma 5) witness that $\mathbf {iRINIT}\le ^{\mathrm{W}{eak}}_{\mathbf {Part}} \mathbf {iINIT}$.    $\blacksquare$

Theorem 23

$\mathbf {iRINIT}\not \le ^{weak}_{\mathbf {Part}} \mathbf {iCOINIT}$.

The next result shows that $\mathbf {iRINIT}$ is strongly reducible to $\mathcal{REG}$, the class of all regular languages. As we noted above, $\mathcal{REG}$ is not reducible to $\mathbf {iRINIT}$ (even weakly), thus, the degree of $\mathbf {iRINIT}$ is strictly below the degree of $\mathcal{REG}$.

Theorem 24

$\mathbf {iRINIT}\le ^{Strong}_{\mathbf {Part}} \mathcal{REG}$.

Now we turn our attention to the classes $\mathbf {iINIT}_k$ and $\mathbf {iCOINIT}_k$. The infinite languages in these classes do not form simple strict chains, as, for every infinite language L in the chain, both classes contain its variants having up to k extra elements. Interestingly, though, it turns out that, whereas adding one such extra element to infinite languages in the chain makes the partial learning problem harder, the difficulty of the partial learning problem does not increase when more elements are added.

Theorem 25

For all $k>0$,

• (a) $\mathbf {iINIT}_k \le ^{Strong}_{\mathbf {Part}} \mathbf {iINIT}_1$.

• (b) $\mathbf {iCOINIT}_k \le ^{Strong}_{\mathbf {Part}} \mathbf {iCOINIT}_1$.

• (c) $\mathbf {iINIT}_1 \not \le _{\mathbf {Part}}^{Strong} \mathbf {iINIT}$.

• (d) $\mathbf {iCOINIT}_1 \not \le ^{weak}_{\mathbf {Part}} \mathbf {iCOINIT}$.

• (e) $\mathbf {iINIT}_1 \le ^{weak}_{\mathbf {Part}} \mathbf {iINIT}$.

Theorem 26

For all $k>0$,

• (a) $\mathbf {iINIT}_k \le _{\mathbf {Part}}^{Strong} \mathbf {iRINIT}$.

• (b) $\mathbf {iCOINIT}_k \le _{\mathbf {Part}}^{Strong} \mathbf {iRINIT}$.

• (c) $\mathbf {iRINIT}\not \le _{\mathbf {Part}}^{Strong} \mathbf {iINIT}_k$.

• (d) $\mathbf {iRINIT}\not \le _{\mathbf {Part}}^{weak} \mathbf {iCOINIT}_k$.