We study learning of indexed families from positive data where a learner can freely choose a hypothesis space (with uniformly decidable membership) comprising at least the languages to be learned. This abstracts a very universal learning task which can be found in many areas, for example learning of (subsets of) regular languages or learning of natural languages. We are interested in various restrictions on learning, such as consistency, conservativeness or set-drivenness, exemplifying various natural learning restrictions.
The contribution of this work is twofold. First, we present a general result on how the hypothesis spaces may be constructed during learning, rather than beforehand. Using this result, we build on previous results from the literature and provide several maps (depictions of all pairwise relations) of various groups of learning criteria, including a map for monotonicity restrictions and similar criteria and a map for restrictions on data presentation. Furthermore, we consider, for various learning criteria, whether learners can be assumed consistent.
We investigate the problem of algorithmically learning a description for a formal language (a computably enumerable subset of the set of all natural numbers) when presented successively all and only the elements of that language. This is called inductive inference, a branch of (algorithmic) learning theory. For example, a learner h (a computable device) might be presented more and more numbers. After each new number, h outputs a description for a language as its conjecture. The learner h might decide to output a program for the set of all odd numbers, as long as all numbers presented are odd and prime. Later, when h sees a 2, it might change this guess to a program for the set of all prime numbers.
In the literature, many criteria for determining whether a learner h is successful on a (target) language L have been proposed. Gold [15] gave a first, simple learning criterion, -learning,1
stands for learning from a text of positive examples; G stands for Gold-style learning and indicates that the learner has full information on the data given; stands for explanatory.
where a learner is successful if and only if, on every text for L (listing of all and only the elements of L) it eventually stops changing its conjectures, and its final conjecture is a correct description for the input language. Trivially, each single, describable language L has a suitable constant function as a -learner (this learner constantly outputs a description for L). Thus, we are interested in analyzing for which classes of languages there is a single learner h learning each member of . This framework is also known as language learning in the limit and has been studied extensively, using a wide range of learning criteria similar to -learning (see, for example, the textbook [16]).
A major branch of this analysis focuses on learning indexed families, that is, classes of languages such that there is an enumeration of all and only the elements of for which the decision problem “” is decidable. Already for such classes of languages we get a rich structure, see the survey of previous work [29]. Here, the learners learn with respect to some indexed family, the so-called hypothesis space. The conjectures of the learners are then interpreted according to the hypothesis space and the learners learn a class of languages successfully if they do so with respect to some hypothesis space. We are specifically interested in class comprising learning, where our learners are free to choose any hypothesis space containing hypotheses at least for the target languages. This is in contrast, for example, to learning with an explicitly given hypothesis space.
Since the appearance of the mentioned survey, only little work on indexable classes was conducted, while learning of arbitrary families of languages sprouted a new mode of analysis, map charting. This approach tries to further the understanding of learning settings by looking at all relations between similar learning criteria and displaying them as a map [21,22]. This approach builds on the pairwise relations which are already known in the literature and completes them in interesting settings to understand one aspect more closely, for example regarding certain natural restrictions on what kind of mind changes are allowed (which we will consider in Section 5) or the importance of data presentation (which we will consider in Section 6).
We develop a very useful characterization of learning indexable families given in Theorem 1. Here we show that learnability of an indexed family with an arbitrary hypothesis space is equivalent to the learnability by a learner which only outputs programs for characteristic functions [4] and is considered successful when converging to such a program which decides the target language. This result allows us to simplify many of our proofs, since now the hypothesis space does not need to be chosen in advance.
With this characterization, we start our analysis by considering the restriction of consistent learning [1]. A learner is consistent if and only if each of its hypotheses correctly reflects the data which the hypothesis is based on. Note that, for arbitrary learning in the Gold-style model, learners cannot be assumed consistent in general [3], a result termed the inconsistency phenomenon. The reason behind this result is essentially the same as for the halting problem: a general hypothesis cannot be checked for consistency in a computable way. Since, for indexed families, consistency of hypotheses is decidable, it comes at no surprise that here learners can, in general, be assumed consistent [37]. However, to prove this result, crucial changes to the hypotheses are made (so as to make them consistent), which might spoil other nice properties the learner might exhibit (such as never overgeneralizing the true target language). In Section 4 we show several different ways in which total learners can be made consistent, each maintaining other restrictions (such as, for example, conservative learning [1], where learners must not change their mind while their hypothesis is consistent).
In Section 5 we consider one of the best-studied maps from other learning settings, the map of delayable learning restrictions. We build on previously known results, such as that conservative learning is restrictive [24], and complete the map both for the case of full information (where the learner has access to the full history of data shown) and for set-driven learners (which only have access to the set of data presented so far, but not to the order of presentation [34]). This builds on earlier analyses of monotone learning which has been studied in various settings [27]. We depict our results in Fig. 1(a). In particular, we show that the criteria cluster into merely five different learning powers, i.e., many learning criteria allow for learning the same classes of languages. Among other things, we show that (strong) non-U-shaped learning [2,11], where abandoning a correct hypothesis is forbidden, is not restrictive in either setting (set-driven and full-information).
Depiction of relations between G- and -learners under various additional restrictions (see Fig. 1(a)) and syntactic and semantic convergence criteria under various memory restrictions β for total learners (see Fig. 1(b)) when learning indexable classes. For a full list of the considered restrictions, please see Section 2. Black solid lines imply inclusions (bottom-to-top, left-to-right). In Fig. 1(b), these inclusions are trivial and the dashed line depicts the non-trivial proper inclusion . Greyly edged areas illustrate a collapse of the enclosed learning criteria. There are no further collapses.
In Section 6 we consider in more detail what impact the access to information has on the learning power of total learners. Additionally to full information and set-driven learning, we also consider iterative learning (where the learner has access to its previous hypothesis, but only the current datum [34]). We give the complete map for -learning at the same time as -learning (behaviorally correct learning, where the learner need not to stop syntactically changing the conjecture, as long as it remains semantically correct [9,31]). We depict our findings in Fig. 1(b).
These directions taken together (consistency, delayable restrictions, information access, syntactic vs. semantic convergence) give a well-rounded picture, offering a glimpse on learning indexable classes from all commonly studied angles.
Preliminaries
In this section we introduce the mathematical notations and notions used throughout the paper. For non-introduced notation we refer to [32]. Regarding the learning criteria, we follow the system of [19].
Language learning in the limit
We denote the set of natural numbers by . With ⊆ and ⊊ we denote the subset and proper subset relation between sets, respectively. With we denote the set intersection, union, and difference, respectively. We let ∅ and ε denote the empty set and empty sequence, respectively. We use () as the set of all (total) computable functions. If a function f is defined on an argument x we denote this by ; otherwise, we write . We fix an effective numbering of , where e may be viewed as a program or index for the function .
We fix the symbol # called pause. For any set , we denote . The set of all sequences of length at most over is denoted by and the set of all finite sequences over by . For two sequences σ, τ, we let denote their concatenation and we write () if and only if σ is a (proper) prefix of τ. For a (possibly infinite) sequence σ, we let . For , we denote the sequence with the last element removed as . Furthermore, we may interpret finite sequences as natural numbers and fix a total order ⩽ on these such that, in particular, for all with we have that .
We call a computably enumerable set a language. We learn indexed families of languages, that is, families of languages where there exists a total computable function f such that, for all ,
We learn these families with respect to hypothesis spaces, which are indexed families of languages themselves. In general, a learner is a function . We examine learning from text. A text is a total function . We denote the set of all texts as . Similar to sequences, we define the content of a text as . Furthermore, we call T a text for a language L if ; the set of all texts for L is denoted by . The canonical text of a language L is the enumeration of all elements in L in strictly ascending order (if L is finite, the text returns # after all elements have been presented). Analogously, the canonical sequence of a (finite) language L is the (finite) sequence of all elements in L in strictly ascending order. Additionally, we define and, for all with , .
What kind of information a learner is given, is specified by an interaction operator. Formally, an interaction operator is a function that takes a learner and a text as input arguments and outputs a (possibly partial) function that is called learning sequence or sequence of hypotheses. We consider Gold-style or full-information learning [15], denoted by G, iterative learning (, [13,35]), partially set-driven or rearrangement-independent learning (, [5,33]), set-driven learning (, [34]) and transductive learning (, [7,19]). Note that transductive learners may output a special symbol “?” if the information given is not sufficient to make a guess. Formally, for all learners , texts and ,
Intuitively, Gold-style learners have full information on the elements given. Set-driven learners base their hypotheses solely on the content of the information given, while partially set-driven learners additionally have a counter for the iteration step. Iterative learners base their conjectures on their previous hypothesis and the current datum. Lastly, transductive learners solely base their guesses on the current datum and may output “?” if the information is not sufficient.
For two interaction operators β, we write if and only if every β-learner h can be compiled into an equivalent -learner such that, for any text T, we have . We note that and . As an example, every -learner can be compiled into an -learner by simply ignoring the counter. Furthermore, note that any -learner may be simulated by a -learner, however, the order of the hypotheses may be changed. For any β-learner h with , we let , the starred learner, denote the G-learner simulating h. For example, the starred learner of a -learner h is defined, for all sequences σ, as .
For a learner to successfully identify a language it has to satisfy certain restrictions. A famous example was given by Gold, who required the learner to converge to a correct hypothesis for the target language [15]. This is called explanatory learning and denoted by . When we speak of correct hypotheses, it is with regard to an indexed hypothesis space. Formally, a learning restriction is a predicate on a sequence of hypotheses p and a text . In the case of explanatory learning, we get, for a given indexed hypothesis space ,
We now give the intuition for the considered restrictions and define them formally afterwards. As an alternative to , for behaviorally-correct () learning one only requires semantic convergence, that is, after some point all hypotheses must be correct hypotheses for the target language, but they do not need to be syntactically equal [9,31].
In addition to these convergence criteria there are various other properties to require from a learner that are inspired from nature or other sciences. In non-U-shaped learning (, [2]), once the learner outputs a correct hypothesis, it may not unlearn the language, i.e., it may only make syntactic mind changes. In strongly non-U-shaped learning (, [11]) not even these syntactic mind changes are allowed. In consistent learning (, [1]), each hypothesis must include the given information. There exist various monotonicity restrictions ([17,25,36]). When learning strongly monotone (), the learner may not discard elements present in previous hypotheses, and in monotone learning () the learner is not allowed to remove correct data from its hypotheses. Furthermore, in weakly monotone learning () the learner must remain strongly monotone while consistent with the input. Similarly, in cautious learning (, [30]), no hypothesis may be a proper subset of a prior hypothesis. As a relaxation, in target-cautious learning (, [21]), no hypothesis may be a proper superset of the target language. A specialization of cautious and weakly monotone learning is witness-based learning (, [22]), where each mind change must be justified by a witness. Witness-based learning is also a specialization of conservative learning (, [1]) where the learner may only make a mind change when an inconsistency is detected. If we only require this for semantic mind changes, we call the learner semantically conservative (, [23]). Finally, in decisive learning (, [30]), the learner may not return to semantically abandoned hypotheses; in strongly decisive learning (, [20]), the learner may not return to syntactically abandoned hypotheses. Now, we give formal definitions for theses restrictions. Let be an indexed hypothesis space. For any sequence of hypotheses p and text , define
We combine any two learning restrictions δ and by intersecting them, which is denoted by their juxtaposition. With T we define the learning restriction which is always true and interpret it as absence of a learning restriction.
Finally, a learning criterion is a tuple , where α and δ are learning restrictions, is the set of admissible learners, usually or , and β is an interaction operator. We write to denote the learning criterion and omit if it equals , and a learning restriction if it equals T. Let be an admissible learner. We say that h-learns a language L with respect to some hypothesis space if and only if, for all texts , we have and, for all , . Note that α has to hold on all texts, while δ only has to be true on texts of the learnable language L. The set of languages -learned by h with respect to some hypothesis space is denoted by . The class of such sets over all admissible learners is denoted by , the so-called learning power of -learners.
Normal forms
To prove certain statements on a learner, there are properties that come in handy. For example, except for , all considered learning restrictions are delayable. Intuitively, a learning restriction is delayable if it allows for arbitrary, but finite postponing of hypotheses [21]. Formally, a learning restriction is delayable if and only if for all sequences of hypotheses p, texts with and non-decreasing, unbounded functions , if we have and, for all , , then also holds.
A common property of the considered learning restrictions is that they solely depend on the semantic of the hypotheses and on the position of mind changes. This property is formalized in the notion of pseudo-semantic learning restrictions [23]. A learning restriction δ is pseudo-semantic if and only if for all learning sequences p and texts , if and for a learning sequence , with, for all , and are defined and semantically equivalent and implies , then . All considered learning restrictions are pseudo-semantic.
We regularly make use of locking sequences. These are sequences that contain enough information such that a given learner, after seeing this sequence, suggests a correct hypothesis for the target language and does not change its mind whatever data from the target language it is given. Formally, let h be a G-learner and a hypothesis space. Then a sequence is a locking sequence for h on a language L, if, for all sequences , we have and [5]. For -learners, we drop the first requirement and call σ a -locking sequence [16]. This definition can directly be expanded to learners with other interaction operators. Let h be such a learner and consider its starred learner . Then, a sequence σ is called a locking sequence for h on L if and only if σ is a locking sequence for on L. We remark that, in the case of partially set-driven and set-driven learners, we refer to locking sequences as locking information and locking set, respectively. Note that, if a learner learns a language there always exists a (-) locking sequence [5], but there exist texts where no initial sequence thereof is a (-) locking sequence. Given a learner h and a language L it learns, if on any text there exists an initial sequence thereof which is a (-) locking sequence for h on L, we call h strongly (-) locking on L. If h is strongly (-) locking on every language it learns, we call h strongly (-) locking [21].
Learning indexed families without hypothesis spaces
In this section, we present a useful result on which we build our remaining results. When learning indexed families with respect to (arbitrary) hypothesis spaces, the choice of the latter is crucial for successful learning. However, it is often a non-trivial task to construct the fitting hypothesis space. With Theorem 1, we show that one can forgo this necessity and, so to speak, obtain the hypothesis space on the run.
We make use of so-called C-indices or characteristic indices [4]. Intuitively, a C-index of a language L is a program for its characteristic function. Formally, an index e is a C-index of the language L if and only if . We also denote . Note that if e is a C-index of L then . Now, we can request a learner to converge to a C-index instead of an index with respect to some hypothesis space. Exemplary, when requiring syntactic convergence to a C-index we write, for all sequences of hypotheses p and all texts T,
Adjusting the other considered restrictions to cover C-indices is immediate and, thus, omitted. For clarity, we write in case of learning C-indices. Analogously, we denote with the set of all classes -learnable by some learner h.
In particular, we show that learners which output characteristic indices on any input may be translated into total learners which learn with respect to a hypothesis space. To that end, we define the restriction [4], where the learner must output C-indices. Formally, for any hypothesis sequence p and any text T, we have
We show the equality of the two learning approaches. Firstly, the output when learning with respect to a hypothesis space can easily be interpreted as a characteristic index. For the other direction, we consider all hypotheses output by the -learner, that is, the learner which outputs C-indices on any input, as hypothesis space and choose the right (minimal) index of this hypothesis space to maintain successful learning.
Let α, δ be pseudo-semantic restrictions, letbe an interaction operator and letbe an indexed family. Then,is-learnable by some learner h if and only if there exist a total learnerand a hypothesis spacesuch that-learnswith respect to.
For the first direction, let be an indexed family learned by a -learner h. Let be the starred form of h, that is, the G-learner simulating h. As h is , so is and we can define the indexed hypothesis space . As h learns , we have . Fix an order ⩽ on the set of all finite sequences. Then, we define the learner , for notational convenience in its starred form, for any finite sequence σ as
Note that the min-search terminates as σ is a candidate thereof. Intuitively, returns the ⩽-least sequence such that does not change, that is, . This sequence is then an index for the hypothesis space . Now, for two sequences σ and τ, we have if and only if . Also, and are semantically equivalent. Thus, -learns with respect to .
Conversely, let be such that there exist a total learner and an indexed hypothesis space such that -learns with respect to . We provide a learner h which -learns . Let and denote their starred forms. As is an indexed hypothesis space, there exists a total computable function f such that for all
Due to the S-m-n Theorem, there exists a strictly monotonically increasing function such that, for all , we have . Now, we define, for all finite sequences ,
We conclude the proof by showing that h-learns . We first show that h is . This follows immediately as, for any finite sequence σ, there exists such that
As only makes mind changes when h does and as, for any , , we have that h-learns . □
We will see that in many cases requiring the learner to be total is not restrictive. It is already known that, when learning arbitrary classes of recursively enumerable languages, Gold-style learners, obeying delayable learning restrictions, may be assumed total [21]. This result directly transfers to learning indexed families with respect to some hypothesis space.
([21]).
For delayable restrictions δ we get.
This proof follows [21] and is included for completeness. Immediately, we get the inclusion . For the other, let h-learn with respect to a hypothesis space . Let such that . To define the equivalent learner, let Φ be a Blum complexity measure [6], that is for example, for , could be the number of steps the program e needs to halt on input x. We define a learner such that, for all sequences ,
As we only allow total learning sequences of h for languages in , we have and, thus, is indeed total and computable. We show that h-learns with respect to . To that end, we use that δ is delayable. Let and . Now, for all , let . Note that, for all , we have . As δ is delayable, it suffices to show that r is non-decreasing and unbounded to prove that -learns with respect to . By definition of r, we have that r is non-decreasing and, for all , we have and that r is unbounded, as there exists with such that and, thus . This concludes the proof. □
Consistent learning
Certain learners exhibit various properties which ease mathematical proofs and provide insight in the necessary learning behavior. One such is being consistent with the information given while maintaining learning power. For example, various behaviorally correct learners have been investigated for consistency [23]. We study whether this can also be assumed when learning indexed families and also with explanatory learners. Initial results can be found within the literature [1,27–29]. We complete these using condense results (see Lemmas 4 to 6) and obtain Theorem 3, the main result of this section. For the remainder this section, we fix and .
For all, alland all, we have
Unrestricted -learners can be made consistent by simply patching the missing elements into the hypothesis. As one can check for consistency, one can decide whether changing the hypothesis is necessary or not. It is immediate to see that this strategy works out as, firstly, the padding needs only to be done while the learner did not converge yet and, secondly, as the learner needs not to serve any additional requirements. Note that this also preserves -convergence. Interestingly, the same idea also works out for strongly monotone and monotone learners. Especially here, Theorem 1 comes in handy as we create the hypothesis space containing the padded hypotheses on the way.
For,and, we have
The inclusion is immediate. For the other, we use a construction which patches in the seen data while maintaining the given learning restriction, as seen when learning of arbitrary classes [23]. By Theorem 1, it suffices to show
Let h be a learner and let . We define a -learner using some auxiliary functions. For ease of notation, we use h and as their starred learners. Due to the S-m-n Theorem, there exists such that, for all and all finite sequences σ,
We now define the learner such that for any finite sequence σ
Note that and are total because h is a -learner. Intuitively, has the same hypothesis as h, if this hypothesis is consistent. Otherwise, it patches the input set into the hypothesis of h. Thus, by construction, only outputs consistent C-indices, i.e., it is a -learner. In particular, note that for any sequence σ we have that
It remains to be shown that -learns every language in and that it obeys the restriction δ while doing so. We first show -convergence. Let and . As h learns L, there exists such that, for all , we have and, in the case of , also . For , as is consistent, will output , proving that -learns L from text T.
Lastly, we prove that learns without violating the restriction δ. For this follows immediately. We consider the remaining restrictions separately. Let and let .
. Let such that . Since h is , we have that
Now, by Equation (1), we get that is as
. Let such that . Since h is , we have that
Now, by Equation (1), we get that is as
This concludes the proof.
□
The former strategy does not work for target-cautious learners. The reason is that by simply adding missing elements, one can suddenly overgeneralize the target language. “Resetting” the conjecture to solely the information given when determining non-consistency preserves target-cautiousness, as we show in the next result. Interestingly, this strategy of “resetting” also works for weakly monotone learners as they, when inconsistent, may propose new suggestions.
For,and, we have
The inclusion is immediate. For the other, it suffices to show , due to Theorem 1. We use a similar construction as used for the case of W-indices [23]. The idea is to output solely the content of the given data if the original learner is not consistent. Let h be a learner and let . We define a learner which -learns . For ease of notation, we use h and as their starred learners. We now define the learner , such that for any finite sequence
Note that is total and computable because h only outputs C-indices. By construction, only outputs consistent C-indices, i.e., it is a -learner.
It remains to be shown that -learns every language in while obeying the restriction δ. We first show -convergence. Let and . As h learns L, there exists such that, for all , we have and, in the case of , also . For , as is consistent, will output , proving that -learns L on text T.
Lastly, we prove that satisfies the restriction δ. We consider the restrictions separately. Let and let .
. Let such that and . We show that . If is not consistent, that is, , then . Thus, we have that
Otherwise, is consistent and, thus, . Since, by assumption, and since h is weakly monotone, we have that and also that is consistent. Thus, in this case we get
. Let , then outputs either , in which case the hypothesis is target-cautious due by assumption, or it outputs the conjecture . As , this hypothesis is also target-cautious. □
Although (semantically) conservative learners may change their mind when being inconsistent with the data given, the above strategy does not work. The problem is that one may make them consistent too early and, thus, prevent later mind changes from happening. An interesting strategy solves the problem. One mimics the (possibly) inconsistent learner on information without repetition. Learning is preserved this way, as when inferring infinite target languages there will always be new information to correct an incorrect conjecture. On the other hand, learning finite target languages is also successful since, given all information without repetition, either the learner was correct anyway or making it consistent is a correct guess.
For,and, we have
The inclusion is immediate. For the other, we use a similar construction as when learning W-indices [23]. By Theorem 1, it suffices to show . Let h be a learner and let . We define a learner which -learns . For ease of notation, we use h and as their starred learners. Given a sequence σ, we write for the sequence without repetitions or pause symbols. Analogously, -learners given consider instead. Notably, -learners receive the same information since we have . Now, we define such that, for all finite sequences ,
Note that, by construction, is a -learner. The intuition for the learner is then to mimic h on information without repetition. This is important to ensure (semantic) conservativeness. Given σ, it either outputs the same hypothesis as , if this is consistent, or it outputs solely a C-index for the content of the input.
Next, we show that -learns . Let and . We distinguish whether L is finite or not.
L is finite. Then, there exists a minimal such that . Then, by definition, for all , we have that as no new element will be witnessed. Now, if is consistent, then, because h is (semantically) conservative and thus target-cautious, we have . Otherwise, outputs . In both cases, is a correct hypothesis.
L is infinite. Note that the transition to text T from the corresponding text which does not contain any duplicates or pause-symbols can be done using an unbounded, non-decreasing function , that is, . As is delayable, it suffices to show the convergence on text . As h also converges on , there exists some such that, for all , we have and, if , also . In particular, for all , is consistent and, thus, . Thus, -learns L from text since h does and, as is delayable, also learns L from text T.
It remains to be shown that obeys δ. The basic idea is that may only make a mind change if it sees a new element which is not consistent with the current hypothesis. Formally, let and . Furthermore, let , with , be such that . We distinguish between the two cases for δ.
. We show that . In the case of , this follows by definition. Otherwise, there exists an element in which is not in . Thus, in order for to enumerate , that is, , it must hold that . Then, since h is semantically conservative, we have . In particular, is consistent, meaning that . Altogether, we get
. This case follows an analogous proof-idea, the main difference being that semantic equalities need to be replaced with syntactic ones. We show that . In the case of , this follows by definition. Otherwise, there exists an element in which is not in . Thus, in order for to enumerate , that is, , it must hold that . Then, since h is (syntactically) conservative, we have . In particular, is consistent, meaning that . Altogether, we get
which concludes the proof.
□
We note that none of the above strategies work for learners which may not return to previous guesses, say, non-U-shaped learners, as one may, by patching missing elements into the hypotheses or “resetting” the hypotheses, accidentally produce a hypothesis for the target language and later discard it temporarily. However, another widely used strategy, called poisoning [8], works in this case. The main idea is to “poison” wrong hypotheses, that is, create obviously incorrect hypotheses. Since inconsistent hypotheses cannot be correct, we can poison those and obtain a consistent learner.
For,and, we have
We would like to express our gratitude to the anonymous reviewer who provided helpful feedback in developing the following proof. Observe that the inclusion is immediate. For the other direction, by Theorem 1, it suffices to show
Let h be a learner and let . We consider h in its starred form to prove the statement for all at once. Consider the class of hypotheses made by h, that is, . Intuitively, we construct an indexed family containing poisoned hypotheses as follows. We start with a computable set F which is co-infinite, that is, is infinite, and which differs from all possible hypotheses made by h, that is, differs from all sets in , at infinitely many positions. We then extend this set with some finite information which grows as the data input grows. In particular, we will make it consistent. We then use these sets in case the original hypothesis was inconsistent (and therefore wrong).
For the formal proof, we use the following auxiliary notation. Given the interaction operator β and two finite sequences , we write if and only if,
in the case of , we have ;
in the case of , there exists a text and , with , such that and ;
in the case of , we have .
Intuitively, means that σ contains less information than τ according to β.
We construct formally. Using a diagonalisation argument, we obtain a computable set F which is co-infinite, that is, is infinite, and which differs from, for all , at infinitely many positions. Let m be a bijective computable function such that, for all , and, if then . Respecting the notation of starred learners, we write . Intuitively, m creates a numbering which ensures that later information obtains a larger number.
For each , let be such that is the set containing the first many elements which are not present in F. As F is co-infinite, we will always find such elements. Furthermore note that by the choice of we have . Now, let be such that
Note that . In the end, define .
Now, given a finite sequence as input, consider the new learner g defined as
The learner g is a β-learner and consistent by definition. Furthermore, the learner g maintains -learning as whenever h outputs a correct (and therefore consistent) hypothesis, g outputs the (syntactically) same hypothesis. We show that it obeys the restriction δ as well. Let be such that and , which equals L in case δ equals and . We show that for each with , we have (in case δ equals and ) and (in case δ equals and ).
If , we get the result immediately. Otherwise, assume . Thus, and, by definition of g, the only possibility where may happen is that and . As h is a δ-learner, we have . This, in particular implies
Thus, and, therefore, (in case δ equals and ) and (in case δ equals and ). This means that g maintains δ. □
Altogether, the lemmas above give the proof of Theorem 3.
Delayable map for learning indexed families
In this section we compare the power of (possibly partial) learners underlying various delayable learning restrictions to each other. First, we gather known results from literature. It is a well-known fact that learners need time in order to obtain full learning power [27], that is, set-driven learners lack learning power. Furthermore, in the literature monotonic learners have been investigated thoroughly [27].
We remark that weak monotonicity as well as conservativeness is no restriction to set-driven learners [27]. We expand this result by showing that set-driven learners may be even assumed to be witness-based. This way, we also capture the remaining restrictions, such as (target-) cautiousness and (strong) decisiveness. To obtain the desired result, we first show that target-cautious and witness-based Gold-style learners possess the same learning power. The idea is that, as target-cautious learners never overgeneralize the target language, there always remain elements as witnesses to justify a mind change if the current hypothesis is wrong.
We have.
The inclusion is straightforward. For the other, by assuming that G-learners are total, see Theorem 2, and by Theorem 1, it suffices to show
Let h be a learner with . Using Theorem 3, we can assume h to be consistent, i.e., . We now prove that the following learner is a -learner for . Let and, for all finite and , let
Intuitively, only updates its hypothesis if the latest datum may be used as a witness for a mind change. As h is also consistent, we immediately have that is witness-based. Furthermore, note that outputs a C-index on every input and thus is a -learner.
It remains to be shown that learns . To that end, let and . Since h correctly learns L there exists such that, for all , we have and . We distinguish the following cases.
is a C-index for L. In this case, , and thus cannot change its mind again. Thus, it converges correctly.
is no C-index for L. As h is target-cautious and mimics h, it cannot hold . Thus, there exists with . By definition of and by consistency of h, we have . Let be such that . Then, by construction, for all , we have that , which is a C-index for L. □
This equality also includes weakly monotone learners. Thus, we already have that these are as powerful as set-driven learners. However, we go one step further and show that these learners may even be assumed total. We make use of Theorems 1 and 2. The idea is to mimic the Gold-style learner on the minimal, consistent hypothesis. This way, target-cautiousness is preserved as well as the learning power, since no guess overgeneralizes the target language and, thus, checking for consistency is a valid strategy.
We have.
The inclusion is immediate. For the other one, as G-learner may be assumed total, see Theorem 2, and by Theorem 1, it suffices to show
Let h be a learner and let . By Theorem 3, we may assume h to be consistent. For a finite set D, for , let be the canonical sequence of D of length k, that is, the sequence of the first k elements in D in strictly ascending order, and define the -learner as
Mimicking learner h, the newly defined learner is target-cautious whenever h is and it always outputs C-indices. It remains to be shown that -learns . Let, to that end, . We distinguish the following cases.
L is finite. Let be the minimal such that . By consistency of h, such exists. Then, we have by h being target-cautious that . Altogether, we have
L is infinite. Then, consider the canonical text T of L. As h learns L, there exists a minimal such that . By target-cautiousness of h and minimal choice of , there exists such that for all we have
Then, for all D with , we have as desired.
□
Again with Theorem 1, we obtain that set-driven learners may be assumed total and witness-based. The idea resembles the approach for partially set-driven learners of arbitrary classes of languages [22]. To obtain this, we assume the information coming in a certain order and then mimic the learner on the least input where no mind change is witnessed. Then, while enumerating, we check whether any later datum causes a mind change. If so, we stop the enumeration. Especially here, Theorem 1 comes in handy as we do not need to fix the hypothesis space beforehand, but rather build it up on the fly.
We have.
The direction follows immediately. For the other, by Theorem 1, it suffices to show that
Let h-learn . We define the desired witness-based learner . Given a finite set D and , let be the set of the first k elements (in ascending order) in D, and define
That is, contains the minimal amount of elements of D in ascending order where no mind change is witnessed. In what follows, we use to denote all elements in up until x, that is, . Then, for any finite set D, define
Note that for any locking set D of some language L, we have . Then, for any finite set D, we define the learner
Intuitively, the learner first searches the minimal amount of elements where no mind change is witnessed. Then, given , if the learner on input witnesses an element to be (possibly) out of order, it outputs . This way, we keep this element as a witness for a possible, later mind change. Otherwise, the learner outputs which conducts a forward search and enumerates all elements where no mind change is witnessed.
Formally, we first show that learns correctly. Let therefore . We distinguish the following cases.
L is finite. Here, is a correct conjecture and, thus, as well. Note that, in particular, is a locking set for L. As there exists no with , we have that . Since is a locking set, is a correct conjecture.
L is infinite. Let be the canonical text for L and let be minimal such that is a locking set for h on L. As, for all , is no locking set, there exists some where this is witnessed. Let and let such that, for , we have . Then, for any D with , we have that . As is a locking set, we have that is a correct hypothesis.
Lastly, we show that is witness-based. Let, to that end, such that . We show that . For , let and let . Then, as , it suffices to show
We distinguish the following cases.
. In particular, . Then, , a contradiction to the initial assumption.
. Let x be a maximal such element. Either, and it will not be considered when enumerating . Otherwise, as it either is less than or it will not be enumerated by as it witnesses a mind change.
. If , then, as , the minimality of is violated. Thus, it also holds that , and we proceed just as in the previous case. □
This completes the study of set-driven learners following delayable learning restrictions. It remains to be shown that Gold-style learners may be assumed strongly decisive. We do so in two steps. First, we show that unrestricted learners may be assumed strongly non-U-shaped in general. The idea is to search for locking sequences. If we witness that the current sequence is not locking, we poison the produced hypothesis [8]. We can do so, as indexed families provide a decision procedure to check whether or not. When poisoning, we simply output a hypothesis contradicting all of the given languages. Note that, by Theorem 1, we may construct poisoned hypotheses on the fly.
We have.
The inclusion is immediate. For the other direction, note that G-learners may be assumed total by Theorem 2. Thus, by Theorem 1, it suffices to show that
Let h be a -learner and let . We provide a -learner for . The idea is the following. Since is indexed, there exists a procedure to decide whether or not. Given any input, we check whether it serves as a locking sequence. Note that -learners may be assumed strongly locking [14]. While it does so, we mimic the learner on this input. Once we figure it not being a locking sequence, we start poisoning this guess such that it does not refer to any of the possible languages . Thus, the resulting learner will output the correct language once it finds a locking sequence thereof.
Formally, we first define the auxiliary predicate which, given a sequence σ and an element , tells us whether σ is a candidate for a locking sequence up until the element x, that is,
Again, we use to denote all elements in up until x, that is, . Next, the S-m-n Theorem provides us with an auxiliary function which poisons conjectures on non-locking sequences. There exists such that for all and
Note that in the second case is non-empty (as the first case does not hold) and that its elements are bounded by x. Lastly, we need the following auxiliary function which finds the minimal sequence on which h agrees with the current hypothesis up until some point. For any sequence σ, define
Finally, we define the learner as, for any sequence σ,
Now, let and let . We show that converges to a correct hypothesis and, afterwards, show the learner to be strongly non-U-shaped. As h is strongly locking, there exists a minimal such that is a locking sequence for h on L. In particular, there exists such that, for all , , that is, all sequences prior to are not locking. Then, for all , we have that and, thus, . Furthermore, for any , we have that as all the sequences output the same hypothesis. Thus, , meaning that is a C-index for L.
We now show that successful learning is also strongly non-U-shaped. First, we show, for all , that is no C-index for L. By minimality of , is no locking sequence for h on L. Now, if is no C-index of L, neither will be, as it either outputs the same as or eventually contradicts all languages in . If, otherwise, is a C-index of L, there exists some point witnessing not to be a locking sequence. Then, starts contradicting all languages in . Thus, and also is no C-index for L. □
Building on this result, we go one step further and show the learners to be even strongly decisive. The strategy the newly found learner employs is to wait before changing its hypothesis until it witnesses a mind change. And, when doing so, it first checks whether this mind change produces a new hypothesis which is different from all previous ones.
We have.
The inclusion follows immediately. For the other, it suffices, by the observation that G-learners may be assumed total (Theorem 2) and by Theorem 1, to show that
To that end, let h be a learner and let . We define an equivalently powerful -learner as follows. Let and, for any finite sequence , let be the minimal sequence on which , that is, the sequence on which based its previous output. Then, define
As mimics h, always outputs C-indices and, hence, is . The intuition is to only update the hypothesis if the current hypothesis cannot be based on a locking sequence and if all previous ones are witnessed to be semantically different. As h is , may never abandon a correct guess and all hypotheses before that are incorrect. Thus, preserves the learning power.
Formally, we first show that is, indeed, . We do so by showing that whenever makes a mind change, this new hypothesis is certainly semantically different from all previous ones and, thus, also syntactically different. Let and let such that , that is, h made a mind change. Note that . Furthermore, let base its prior hypothesis on , that is, is the minimal sequence on which, for all with , we have . The only case where makes a mind change is, if for all there exists such that
As and, therefore, , we have, for all ,
As there are no further mind changes until , this holds for all . Thus, is .
To show that h converges correctly, let and let . Then there exists a (minimal) such that, for all , and is a C-index for L. We distinguish the following cases.
. In this case, is a correct C-index and, as h never changes its mind again, neither does .
. Let be such that . In particular, . Thus, the first case of the definition of cannot hold. By h being and by the minimal choice of , there exists some minimal such that witnesses all hypotheses prior to (and including) to differ from . Then, by the second case of the definition, it will output never to change its mind again. □
Altogether, we obtain the full map as depicted in Fig. 1(a). It remains open to include partially set-driven learners into this picture. Due to known results from literature and the results we obtain, it remains to be shown whether Gold-style learners may be assumed strongly decisive and partially set-driven at the same time. We pose the following open question.
May Gold-style strongly decisive learners be assumed partially set-driven so?
Comparing convergence criteria
In this section we compare total learners under various memory constraints which converge syntactically to such that converge semantically. The gathered results we depict in Fig. 1(b). Usually, semantically converging learners are more powerful than their syntactic counterpart. This can be observed, for example, when learning arbitrary classes of languages [14]. However, when learning indexed families class-comprisingly different results are obtained.
We first gather known results which can be easily obtained from learning with (possibly) partial learners, by either applying Theorem 2 or slightly adapting the known proof. In the latter case, we provide the proofs for completeness reasons. It is known that explanatory G-learners and behaviorally correct ones are equally powerful [29]. By Theorem 2, this also holds true for total learners (compare Equation (2)). Furthermore, it is known that Gold-style learners do not rely on the order of the presented elements but rather on the time given [1,14,33] (see Equation (3)). By patching in the information given [7,10,23], even iterative -learners are as powerful as Gold-style -learners (see Equation (4)). As patching changes the hypothesis with every new datum, this approach does not work for explanatory iterative learners. It is known that this problem cannot be solved as there exists a well-known class separating set-driven explanatory learners from iterative ones [16,26] (compare Equation (5)). On the other hand, each iterative learner can be made set-driven by simply, given all data, mimicking the iterative learner on input with pause-symbols between each two elements [18,26] (compare Equation (6)).
We have
Most of these results are either known or immediately obtainable. We include the proofs for completeness reasons.
It is known that [29]. With Theorem 2, we get the desired.
The inclusion is straightforward. For the other, we follow the proof of the analogous result when learning classes of recursively enumerable languages [14]. Let h-learn with respect to a hypothesis space . Without losing generality, see Theorem 2, let h be total. We define a -learner using an auxiliary function as, for all finite sets and ,
Intuitively, mimics h on minimal potential locking sequences. Note that is total as h is so. To show that h learns , let and . Let be the minimal locking sequence of h on L. We show that eventually converges to . To that end, let be large enough such that, with , we have
,
and
for all there exists such that , i.e., witnesses .
Then, for all , we have and thus converges to . As this is a correct hypothesis for L, learns .
Immediately, we have . We apply a padding argument [23] for the other direction. By Theorem 1, it suffices to show that
Let h be a -learner and let . Recall that is an injective padding function such that for all and all finite sequences σ we have . We define the iterative learner for all previous hypotheses p, all finite sequences σ and all ,
It is immediate to see that, for all sequences σ, we have . Thus, -learns .
This is a standard proof and we include it for completeness [16]. By Theorem 1, it suffices to provide a class of languages which is -learnable but not so. We define . Then, the following learner learns . Fix as a code for the language and define, for any finite sequence σ,
It is immediate that h learns . Now, assume there exists an iterative learner which -learns . Let , let T be a text of L and let such that for all we have . Let , then on the following two texts of distinct languages in
the learner generates the same hypotheses. Thus, it is unable to distinguish between these two. Therefore, cannot be learned by .
This is a standard proof and we include it for completeness [18]. Let h-learn the indexed family with respect to . We provide a -learner learning . To that end, we expand the hypothesis space by adding all finite sets. This new hypothesis space we denote by . For ease of notation, we refer to these new indices as, for all D, . Now, for any set D, let be the sequence of the elements in D sorted in ascending order, with a # between each two elements. Furthermore, let be the starred form of h. Now, we define as, for all finite sets D,
To show that learns with respect to , let . If L is finite, then either , in which case h converges to on text . Otherwise, we have . In both cases, learns L as is a correct hypothesis for L.
On the other hand, if L is infinite, then h converges to a correct hypothesis for L on the text . Let be the initial sequence of on which h has converged and let . Then, for all , we have as h is iterative. Therefore, for all with , we have and , which is a correct hypothesis for L. As , we have the convergence of to a correct hypothesis for L and, thus, learns L. □
Interestingly, only iterative learners benefit from loosening the convergence criterion. We have already investigated the situation for Gold-style and partially set-driven learners. Now, we conclude this section by showing that, first, total set-driven learners and then also transductive ones do not benefit from this relaxation.
Considering set-driven learners, we first show that behaviorally correct such learners may be assumed target-cautious in general. We do so by conducting a forward search, checking the learners output on each possible future hypothesis. Should we detect inconsistencies, we know that the current information is not locking and, thus, we can stop the enumeration. This way, no overgeneralization will happen as, otherwise, locking sets must be included in the search.
We have.
The inclusion is straightforward. By Theorem 1, for the other direction it suffices to show
We apply a similar construction of forward searches as when learning arbitrary classes of languages [12]. Let h be a total learner with . According to Theorem 3, we may assume h to be consistent on any input. Now, define a -learner as follows. Let, for all and finite sets ,
Intuitively, the conjecture of contains D itself and certain additional elements of the hypothesis of h on D. For these additional elements, checks whether all possible future hypotheses of h contain these elements as well. If so, adds them in its hypothesis, otherwise it does not. This way, we prevent overgeneralizing target languages. Note that by construction is . Furthermore, note that, for any finite set D, we have
We first show that -learns any language . We distinguish the following cases.
L is finite. Since h learns L, we have . Consider . Now, for any element , we have , by definition. For any element , we have and, therefore, as well. Thus, and learns L.
L is infinite. Let be a -locking set for h on L. We show that, for any D with , is a correct hypothesis for L. We need to show that . Note that, by Condition (7), . Thus, it remains to be shown that . To that end, let . If , then by consistency. Otherwise, we have and, thus, are in the third case of the definition of . We show that x gets enumerated this way. By Condition (7), we get
As , and therefore also D, is a -locking set, we have for all with that
So the third condition is met and, therefore, . Hence, -learns L.
Finally, it remains to be shown that is target-cautious. To that end, assume that is not target-cautious. Thus, there exists a language and a set such that . Let and let be a -locking set for L on h. Let . As but not in D, it must be enumerated by the third condition of the definition of . Note that (as must be enumerated until ). Now, for all with , it must hold that
However, this is a contradiction for as but . This concludes the proof. □
In a second step, we construct an explanatory learner from the target-cautious behaviorally correct learner. The idea is to always mimic the -learner on the ⩽-minimal set on which it is consistent. This way, we obtain syntactic convergence. On the other hand, the final hypothesis cannot be incorrect as, eventually, the learner has enough information to figure out incorrect guesses and, as it is target-cautious, these consistent conjectures are no overgeneralizations.
We have.
The inclusion is immediate. For the other, by Theorem 1, it suffices to show that
Let h be a learner and let . By Theorem 15, we may assume h to be target-cautious. We provide a learner which -learns . The main idea is to search for the first set on which the learner h is consistent. By its target-cautiousness, this way we will, eventually, conjecture the right language. For the formal details, fix a total order ⩽ on finite sets. For any finite set D, we define the following auxiliary functions as
Finally, for any finite set D, define . To show correctness, let . We distinguish the following cases.
L is finite. Let such that . Since , we have . Since h is target-cautious, the equality holds, that is, . Thus, is a correct hypothesis.
L is infinite. Let be the ⩽-minimal set such that . Let such that and . Such a set exists as h, due to the minimal choice of , conjectures incorrect guesses on with which do not overgeneralize the target language. Then, for any D, with , we have , a correct conjecture. □
Finally, behaviorally correct transductive learners, being unable to save any information about previous guesses, can be made explanatory immediately. One simply awaits a non-? guess and then checks for the first element in this guess which also produces a non-?.
We have.
The inclusion follows immediately. For the other, it suffices, by Theorem 1, to show that
Let h be a -learner and let . We define and such that for all , ,
By construction, is only outputs C-indices (or ?). Intuitively, outputs the hypothesis of h on the smallest element in the hypothesis h on the current datum (if it is not “?”). We claim that learns . Let . First, note that for any , we have that either or is a C-index of L. If that were not the case, h would not identify L on any text which has infinitely many occurrences of x. Furthermore, for at least one , must not be “?”. Thus, there exists a minimal , such that is a characteristic index of L. The idea of this construction is to search for such minimal . Note that, if , as .
Let and let be minimal such that and such that . Then, , a correct guess. Furthermore, for either and with it or, otherwise, . Thus, we have -convergence. □
We remark that all these results, except for Lemma 15 and Theorem 16, also hold for (possibly) partial learners. These are obtained either directly, for example by applying Theorem 2, or by slightly changing the provided proofs. However, one cannot directly translate Lemma 15, and therefore Theorem 16, as, in the forward search, totality of the learner is key. Otherwise, this search can be indefinite, breaking the indexability. We conclude this work by posing the following open question.
Does hold?
Footnotes
Acknowledgements
This work was supported by DFG Grant Number KO 4635/1-1. We would also like to thank the anonymous reviewers for their helpful feedback which helped improving this work.
References
1.
D.Angluin, Inductive inference of formal languages from positive data, Information and Control45 (1980), 117–135. doi:10.1016/S0019-9958(80)90285-5.
2.
G.Baliga, J.Case, W.Merkle, F.Stephan and R.Wiehagen, When unlearning helps, Information and Computation206 (2008), 694–709. doi:10.1016/j.ic.2007.10.005.
3.
J.M.Bārzdiņš, Inductive inference of automata, functions and programs, in: American Mathematical Society Translations, 1977, pp. 107–122.
4.
J.Berger, M.Böther, V.Doskoč, J.Gadea Harder, N.Klodt, T.Kötzing, W.Lötzsch, J.Peters, L.Schiller, L.Seifert, A.Wells and S.Wietheger, Learning languages with decidable hypotheses, in: Computability in Europe (CiE), 2021, pp. 12813:25–12813:37.
5.
L.Blum and M.Blum, Toward a mathematical theory of inductive inference, Information and Control28 (1975), 125–155. doi:10.1016/S0019-9958(75)90261-2.
6.
M.Blum, A machine-independent theory of the complexity of recursive functions, Journal of the ACM14 (1967), 322–336. doi:10.1145/321386.321395.
7.
L.Carlucci, J.Case, S.Jain and F.Stephan, Results on memory-limited U-shaped learning, Information and Computation205 (2007), 1551–1573. doi:10.1016/j.ic.2007.04.001.
8.
J.Case and T.Kötzing, Strongly non-U-shaped language learning results by general techniques, Information and Computation251 (2016), 1–15. doi:10.1016/j.ic.2016.06.015.
9.
J.Case and C.Lynes, Machine inductive inference and language identification, in: International Colloquium on Automata, Languages and Programming (ICALP), 1982, pp. 107–115. doi:10.1007/BFb0012761.
10.
J.Case and S.E.Moelius, U-shaped, iterative, and iterative-with-counter learning, Machine Learning72(1–2) (2008), 63–88.
11.
J.Case and S.E.Moelius, Optimal language learning from positive data, Information and Computation209 (2011), 1293–1311. doi:10.1016/j.ic.2011.07.003.
12.
V.Doskoč and T.Kötzing, Cautious limit learning, in: Algorithmic Learning Theory (ALT), 2020, pp. 117:251–117:276.
13.
M.Fulk, A Study of Inductive Inference Machines, PhD thesis, 1985.
14.
M.A.Fulk, Prudence and other conditions on formal language learning, Information and Computation85 (1990), 1–11. doi:10.1016/0890-5401(90)90042-G.
15.
E.M.Gold, Language identification in the limit, Information and Control10 (1967), 447–474. doi:10.1016/S0019-9958(67)91165-5.
16.
S.Jain, D.Osherson, J.S.Royer and A.Sharma, Systems That Learn: An Introduction to Learning Theory, 2nd edn, MIT Press, Cambridge (MA), 1999.
17.
K.Jantke, Monotonic and non-monotonic inductive inference, New Generation Computing8 (1991), 349–360. doi:10.1007/BF03037092.
18.
E.B.Kinber and F.Stephan, Language learning from texts: Mindchanges, limited memory, and monotonicity, Information and Computation123 (1995), 224–241. doi:10.1006/inco.1995.1170.
19.
T.Kötzing, Abstraction and Complexity in Computational Learning in the Limit, PhD thesis, University of Delaware, 2009.
20.
T.Kötzing, A solution to Wiehagen’s thesis, Theory of Computing Systems60 (2017), 498–520. doi:10.1007/s00224-016-9678-0.
21.
T.Kötzing and R.Palenta, A map of update constraints in inductive inference, Theoretical Computer Science650 (2016), 4–24. doi:10.1016/j.tcs.2016.07.028.
22.
T.Kötzing and M.Schirneck, Towards an atlas of computational learning theory, in: Symposium on Theoretical Aspects of Computer Science (STACS), 2016, pp. 47:1–47:13.
23.
T.Kötzing, M.Schirneck and K.Seidel, Normal forms in semantic language identification, in: Algorithmic Learning Theory (ALT), 2017, pp. 76:493–76:516.
24.
S.Lange and T.Zeugmann, Language learning in dependence on the space of hypotheses, in: Conference on Computational Learning Theory (COLT), 1993, pp. 127–136.
25.
S.Lange and T.Zeugmann, Monotonic versus non-monotonic language learning, in: Nonmonotonic and Inductive Logic, 1993, pp. 254–269. doi:10.1007/BFb0030397.
26.
S.Lange and T.Zeugmann, Incremental learning from positive data, Journal of Computer and System Sciences53 (1996), 88–103. doi:10.1006/jcss.1996.0051.
27.
S.Lange and T.Zeugmann, Set-driven and rearrangement-independent learning of recursive languages, Mathematical Systems Theory29 (1996), 599–634. doi:10.1007/BF01301967.
28.
S.Lange, T.Zeugmann and S.Kapur, Monotonic and dual monotonic language learning, Theoretical Computer Science155 (1996), 365–410. doi:10.1016/0304-3975(95)00284-7.
29.
S.Lange, T.Zeugmann and S.Zilles, Learning indexed families of recursive languages from positive data: A survey, Theoretical Computer Science397 (2008), 194–232. doi:10.1016/j.tcs.2008.02.030.
30.
D.N.Osherson, M.Stob and S.Weinstein, Learning strategies, Information and Control53 (1982), 32–51. doi:10.1016/S0019-9958(82)91097-X.
31.
D.N.Osherson and S.Weinstein, Criteria of language learning, Information and Control52 (1982), 123–138. doi:10.1016/S0019-9958(82)80025-9.
32.
H.RogersJr., Theory of Recursive Functions and Effective Computability, MIT Press, Cambridge (MA), 1987.
33.
G.Schäfer-Richter, Über Eingabeabhängigkeit und Komplexität von Inferenzstrategien, PhD thesis, RWTH Aachen University, Germany, 1984.
34.
K.Wexler and P.W.Culicover, Formal Principles of Language Acquisition, MIT Press, Cambridge (MA), 1980.
35.
R.Wiehagen, Limes-Erkennung rekursiver Funktionen durch spezielle Strategien, Journal of Information Processing and Cybernetics12 (1976), 93–99. doi:10.1016/0306-4573(76)90031-5.
36.
R.Wiehagen, A thesis in inductive inference, in: Nonmonotonic and Inductive Logic, 1991, pp. 184–207. doi:10.1007/BFb0023324.
37.
T.Zeugmann and S.Lange, A guided tour across the boundaries of learning recursive languages, in: Algorithmic Learning for Knowledge-Based Systems, GOSLER Final Report, 1995, pp. 961:190–961:258.
