{'fraction_non_alphanumeric': 0.06109258075108446, 'fraction_numerical': 0.009418799578314294, 'mean_word_length': 4.043933054393306, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Normal Forms for (Semantically) Witness-Based Learners in Inductive Inference

We study learners (computable devices) inferring formal languages, a setting referred to as language learning in the limit or inductive inference. In particular, we require the learners we investigate to be witness-based, that is, to justify each of their mind changes. Besides being a natural requirement for a learning task, this restriction deserves special attention as it is a specialization of various important learning paradigms. In particular, with the help of witness-based learning, explanatory learners are shown to be equally powerful under these seemingly incomparable paradigms. Nonetheless, until now, witness-based learners have only been studied sparsely. In this work, we conduct a thorough study of these learners both when requiring syntactic and semantic convergence and obtain normal forms thereof. In the former setting, we extend known results such that they include witness-based learning and generalize these to hold for a variety of learners. Transitioning to behaviourally correct learning, we also provide normal forms for semantically witness-based learners. Most notably, we show that set-driven globally semantically witness-based learners are equally powerful as their Gold-style semantically conservative counterpart. Such results are key to understanding the, yet undiscovered, mutual relation between various important learning paradigms when learning behaviourally correctly.


Introduction
In his seminal paper, Gold (1967) studied the algorithmic learning of formal languages from a growing but finite amount of information thereof. This marked the starting point of inductive inference or language learning in the limit, a branch of (algorithmic) learning theory. Here, a learner h (a computable device) is successively presented all and only the information from a formal language L (a computably enumerable subset of the natural numbers). We call such a list of elements of L a text of L. When given a new datum, the learner h makes a guess (a description for a computably enumerable set) about which language it believes to be presented. Once these guesses converge to a single, correct hypothesis explaining the language, the learner successfully learned the language L on this text. We say that h learns L, if it learns L on every text of L.
We refer to this as explanatory learning as the learner, in the limit, provides an explanation of the presented language and denote it as TxtGEx. Here, Txt indicates that the information is given from text, G stands for Gold-style learning, where the learner has full information on the elements presented to make its guess, and, lastly, Ex refers to explanatory learning. Since a learner which always guesses a particular language can learn this very language, we study classes of languages which can be TxtGEx-learned by a single learner and denote the set of all such classes with [TxtGEx]. We refer to this set as the learning power of TxtGEx-learners.
Many additional restrictions may be imposed on the learners. For example, we may apply memory restrictions, change the criterion for successful learning or require the learner to refrain from certain unwanted behaviour. In this paper, we require each learner to justify any mind change it makes. Kötzing and Schirneck (2016) introduced this as witness-based learning (Wb) as a means to specialize many important restrictions in inductive inference, including conservativeness (Angluin, 1980), weak monotonicity (Jantke, 1991;Wiehagen, 1991) and cautiousness , see Section 2.1 for detailed definitions. While conservative learners are always weakly monotone, there is no general connection to cautious learners. Nonetheless, often these learners are equally powerful, see Kinber and Stephan (1995) or Kötzing and Palenta (2016).
A key result of Kötzing and Schirneck (2016) reveals an explanation for this phenomenon. In the setting they study, they show that witness-based learners are equally powerful as target-cautious learners (Caut Tar ), which may never overgeneralise the target language (Kötzing and Palenta, 2016). Note that this restriction is a generalization of all the restrictions mentioned above. In particular, they study partially set-driven learners (Psd), see Blum and Blum (1975) and Schäfer-Richter (1984), which base their hypotheses solely on the amount and content of the information given. Similar equalities have been shown for Gold-style and set-driven learners (Sd), which base their hypotheses solely on the content of the information given to them (Wexler and Culicover, 1980), by Kinber and Stephan (1995) and Kötzing and Palenta (2016). However, these results do not include witness-based learning.
In this paper we expand these results to also include witness-based learners and generalize them such that they also hold for total and globally witness-based learners. This way, we discover interesting connections between these different "types" of learners and provide normal forms thereof. Furthermore, we also study behaviourally correct learners (Bc), which need to converge semantically to the correct language (Case and Lynes, 1982;. Here, the mutual relation between the considered restrictions is yet to be discovered. Studying semantically witness-based learners (SemWb), the semantic counterpart of witness-based learners , we complement similar studies of (target-) cautious learners conducted by Doskoč and Kötzing (2020) and, thus, get one step closer to discovering these relations.
In particular, in Section 3, we extend the results of Kinber and Stephan (1995) as well as Kötzing and Palenta (2016) regarding conservative, (target-) cautious as well as weakly monotone Ex-learners to include witness-based learning. Simultaneously, we generalize these together with the results of Kötzing and Schirneck (2016) to hold, amongst others, also for total and globally witness-based learners. These results are presented in Theorems 6, 7 and 10 for G-, Psdand Sd-learners, respectively. Besides covering multiple types of learners at once, these results unveil interesting relations. For example, in the case of Gor Psd-learning, a total learner may be assumed globally witness-based, however, only maintaining its learning power for languages it learns target-cautiously.
In Section 4, we study semantically witness-based Bc-learners and show that three normal forms can be assumed simultaneously. In particular, we show that semantically conservative learners (SemWb), the semantic counterpart of conservative learners  and a generalization of semantically witness-based learning, may be assumed (a) globally (b) semantically witness-based and (c) set-driven, see Theorem 13. In Section 5, we conclude this work.

Preliminaries
In this section we introduce notation and preliminary results used throughout this paper. Thereby, we consider basic computability theory as known, for an overview we refer the reader to Rogers Jr. (1987). We start with the mathematical notation and use and ⊆ to denote the proper subset and subset relation between sets, respectively. We denote the set of all natural numbers as N = {0, 1, 2, . . . }. Furthermore, we let P and R be the set of all partial and total computable functions p : N → N. Next, we fix an effective numbering {ϕ e } e∈N of all partial computable functions and denote the e-th computably enumerable set as W e = dom(ϕ e ) and interpret the number e as an index or hypothesis of this set. Additionally, we mention the following important (total) computable functions. Firstly, we fix a total computable coding function ., . and its inverse for the first and second component π 1 and π 2 , respectively. Furthermore, we write pad for an injective computable function such that, for all e, k ∈ N, we have W e = W pad(e,k) . We use unpad 1 and unpad 2 to recover the first and second component, respectively. Note that both functions can be extended iteratively to more coordinates. Lastly, for any finite set D ⊆ N, we let ind(D) be an index for this finite set, that is, W ind(D) = D.
We learn recursively enumerable sets L ⊆ N, called languages, using learners, that is, partial computable functions. By # we denote the pause symbol and for any set S we denote S # := S ∪ {#}. Then, a text is a total function T : N → N ∪ {#} and the collection of all texts is denoted as Txt. In addition, for any text or sequence T , we let content(T ) := range(T ) \ {#} be the content of T . A text of a language L is such that content(T ) = L. We denote the collection of all texts of L as Txt(L). Additionally, for n ∈ N, we denote by T [n] the initial sequence of T of length n, that is, T [0] := ε and T [n] := (T (0), T (1), . . . , T (n−1)). For a set S, we call the sequence (text) where all elements of S are presented in strictly increasing order without interruptions (followed by infinitely many pause symbols if S is finite) the canonical sequence (text) of S. On finite sequences we use ⊆ to denote the extension relation and ≤ to denote the order on sequences interpreted as natural numbers. Given two sequences σ and τ we write σ ⌢ τ to denote the concatenation of these. Occasionally, we omit writing ⌢ to favour readability.
Following the system introduced by Kötzing (2009), we formalize learning criteria. An interaction operator β takes a learner h ∈ P and a text T ∈ Txt as argument and outputs a possibly partial function p. Intuitively, β provides the information for the learner to make its guesses. We consider the interaction operators G for Gold-style or full-information learning (Gold, 1967), Psd for partially set-driven learning (Blum and Blum, 1975;Schäfer-Richter, 1984) and Sd for setdriven learning (Wexler and Culicover, 1980). We define these using eponymous functions which operate on sequences called sequence interaction functions. Define, for any i ∈ N, The intuition is the following. A Gold-style learner has full information on the elements presented to it, while a partially set-driven learner does not have information on the order the elements were presented in or the frequency of each particular element. However, it may base its guess on the total amount of elements presented, an information a set-driven learner is not aware of. Furthermore, for each of the considered interaction operators we define an ordering β using the associated sequence interaction functions as follows. Given finite sequences σ and τ , we define (1) Intuitively, σ β τ indicates that information β(σ) can be extended to β(τ ). Given a learning task, we can distinguish between various criteria for successful learning. Initially, Gold (1967) introduced explanatory learning (Ex) as such a learning criterion, where the learner is expected to converge to a single, correct hypothesis in order to learn a language. This can be loosened to require the learner to converge semantically, that is, from some point onwards it must output correct hypotheses which may change syntactically. This is referred to as behaviourally correct learning and denoted by Bc (Case and Lynes, 1982;. Formally, a learning restriction δ is a predicate on a total learning sequence p, that is, a total function, and a text T ∈ Txt. For the mentioned criteria we have We can impose restrictions on the learners in order to model natural learning restrictions or such found in other sciences. For example, we consider consistent learning (Cons), where each hypothesis has to include the information it is built on, see Angluin (1980). We focus on (semantically) witness-based learners (Kötzing and Palenta, 2016;, which need to justify each of their (semantic) mind changes. These learners specialize a variety of important learning restrictions, such as conservative learning (Conv), weakly monotone learning (WMon) as well as cautious learning (Caut). While being consistent with the information given, conservative learners must not change their mind, see Angluin (1980), and weakly monotone learners may not discard elements from their hypotheses, see Jantke (1991) and Wiehagen (1991). Lastly, cautious learners may never fall back to a proper subset of any previous guess, see . Generalizing these are target-cautious learners (Caut Tar ), which may never overgeneralize the target language, see Kötzing and Palenta (2016). Particular attention will be given to semantically conservative learners (SemConv), the semantic counterpart of conservative learners . We formalize the relevant restrictions as Finally, the always true predicate T denotes the absence of a restriction. Now, a learning criterion is a tuple (α, C, β, δ), where C is a set of admissible learners, typically P or R, β is an interaction operator and α and δ are learning restrictions. We denote this learning criterion as τ (α)CTxtβδ. In the case of C = P, α = T or δ = T we omit writing the respective symbol. For an admissible learner h ∈ C we say that h τ (α)CTxtβδ-learns a language L if and only if on arbitrary text T ∈ Txt we have α(β(h, T ), T ) and on texts of the target language T ∈ Txt(L) we have δ(β(h, T ), T ). With τ (α)CTxtβδ(h) we denote the class of languages τ (α)CTxtβδ-learned by h and the set of all such classes we denote with [τ (α)CTxtβδ].

Normal Forms in Inductive Inference
In this section we discuss helpful normal forms in inductive inference. Except for consistency, all introduced learning restrictions are delayable. Informally, the hypotheses of a delayable restriction may be postponed arbitrarily but not indefinitely. Formally, we call a learning restriction δ delayable if and only if for all texts T and T ′ with content(T ) = content(T ′ ), all learning sequences p and all total, unbounded non-decreasing functions r, we have that if δ(p, T ) and, for all n, content(T [r(n)]) ⊆ content(T ′ [n]), then δ(p • r, T ′ ). Furthermore, we call a restriction semantic if and only if for any learning sequences p and p ′ and any text T , we have that if δ(p, T ) and, for all n, W p(n) = W p ′ (n) implies δ(p ′ , T ). Intuitively, a restriction is semantic if any hypothesis could be replaced by a semantically equivalent one without violating the learning restriction. Adding the requirement that no new syntactic mind change may be introduced by this replacement, we call a restriction pseudo-semantic Kötzing (2017). Note that all considered restrictions are pseudo-semantic and all, but Ex, Wb and Conv, are semantic. Delayable and semantic restrictions are of particular interest as one can provide general results for them. The following theorem holds.
Theorem 1 (Kötzing and Palenta (2016); ) For all interaction operators β, all delayable restrictions δ and all semantic restrictions δ ′ , we have that Lastly, we discuss locking sequences. Intuitively, a locking sequence is a sequence where the learner correctly identifies the target language and does not make a mind change anymore regardless what information of the language it is presented. Formally, given a language L and a G-learner h, a sequence σ ∈ L * # is called a locking sequence for h on L if and only if for every sequence τ ∈ L * # we have that h(σ) = h(στ ) and W h(στ ) = L, see Blum and Blum (1975). Dropping the first requirement, σ becomes a Bc-locking sequence, the semantic counterpart of a locking sequence, see Jain et al. (1999). When talking about Psd-learners, for finite D ⊆ N and t ∈ N, we call (D, t) a locking information if and only if for all (D ′ , t ′ ), such that (D, t) (D ′ , t ′ ) (compare Equation (1)) and D ′ ⊆ L, we have h(D, t) = h(D ′ , t ′ ) and W h(D ′ ,t ′ ) = L. Lastly, for an Sdlearner, a finite set D is a locking set of L if and only if for all D ′ , with D ⊆ D ′ ⊆ L, we have h(D) = h(D ′ ) and W h(D ′ ) = L. Again, the semantic counterpart is obtained by dropping the first requirement. We use the term (Bc-) locking information to subsume all these concepts.
It is an important observation by Blum and Blum (1975) that every learner h has a locking information on every language it learns. However, not every text may have an initial segment which is a locking information. Learners which do have a locking information on every text of a language they learn are called strongly (Bc-) locking (Kötzing and Palenta, 2016). Formally, a learner is strongly (Bc-) locking on some language L if on every text T ∈ Txt(L) there exists n such that T [n] is a (Bc-) locking sequence for h on L. If h is strongly (Bc-) locking on every language it learns, we call h strongly (Bc-) locking. The transition to partially set-driven and set-driven learners is immediate and, thus, omitted.

Normal Forms for Witness-Based Explanatory Learners
In this section we study witness-based learning in the explanatory setting. Kötzing and Schirneck (2016) already show that partially set-driven witness-based learners are equally powerful as targetcautious Psd-learners. Together with the result of Doskoč and Kötzing (2020), where Gold-style target-cautious learners may be assumed partially set-driven, we see this holding true for fullinformation learners as well. However, general results including total or globally witness-based learners are still rare. With Theorems 6, 7 and 10, we provide expansions and generalizations of these results for Gold-style, partially set-driven and set-driven learners, respectively.
We aim to generalize the results in two ways. Firstly, the aforementioned results were shown solely for partial learners, using additional total computable functions in order to get the desired equality. We observe that, for these constructions to work out, it suffices that the learner remains the "same type" after composition with total computable functions. This motivates the following notion of R-monoids.
Definition 2 We call I ⊆ P a R-monoid if and only if (I, •) is a monoid and R ⊆ I.
Intuitively, the composition of a learner h ∈ I with other functions in I (especially total computable ones) shall remain in I. This way, we can use functions obtained from, for example, the S-m-n Theorem, see Rogers Jr. (1987), while keeping the learner's "type". Note that both R and P are R-monoids.
Secondly, we generalize the domain on which we expect the learner to show a certain behaviour. The desire therefore arises from the observation that some of the learners behaviour does not rely on the learnable languages, but rather comes additionally. To require the learner to fulfil additional requirements on such information, we extend the notion of texts to classes of sets. If S = ∅ then we consider no additional text, if S = Pow(N) then we consider all texts and, thus, the corresponding restriction becomes globally required. Already with the next result, we show the gain we have from these notions. Due to Kötzing and Palenta (2016), it is known that Gold-style and set-driven learners may be assumed syntactically decisive, that is, they never return to syntactically abandoned hypotheses. We are able to capture this result containing many different learners, including learners restricted in memory as well as total ones or learners obeying a further restriction on additional text, within a single theorem.
Theorem 4 Let δ and δ ′ be pseudo-semantic restrictions, β ∈ {G, Psd, Sd} and S ⊆ Pow(N) be closed under subsets. Let I be an R-monoid and let h ∈ I. Let L be the class of languages h TxtβδEx-learns while being defined and δ ′ also on Txt(S). Then, h ∈ I can be assumed syntactically decisive on Txt(L) and Txt(S).
Proof We generalize the ideas of Kötzing and Palenta (2016), where a similar result has been shown for Gand Sd-learners. Let h be as stated in the theorem. For a finite sequence σ, we define Without loss of generality, we may assume that we do not encode β(τ σ ) as 0. Intuitively, Q(β(σ)) checks whether h(β(σ)) has been conjectured without interruptions. In this case, h conjectures pad(h(β(σ)), 0), where the second component zero indicates the absence of interruptions. Otherwise, the second component becomes β(τ σ ), which is the minimal information on which no mind change has been witnessed. Note that the first component is, by definition of τ σ , the same in both cases. We first show syntactic decisiveness. Let therefore σ 1 , σ 2 , σ 3 be sequences such that ( 2) To show h ′ (β(σ 1 )) = h ′ (β(σ 2 )), we distinguish between the following cases.
We next show Ex-convergence. Let L ∈ L and T ∈ Txt(L). Let n 0 be minimal such that W h(β(T [n 0 ])) = L and, for all n ≥ n 0 , we have h(β(T [n 0 ])) = h(β(T [n])). Furthermore, let n 1 ≥ n 0 be minimal such that, for all n ≥ n 1 , we have τ T [n 1 ] = τ T [n] . Such n 1 exists as N with ≤ on sequences is a well-order. Now, for n ≥ n 1 , h ′ (β(T [n])) either conjectures pad(h(β(T [n])), 0) if no interruption has been witnessed. Otherwise, there exists n 2 ≥ n 1 where an interruption has been witnessed. Then, for all n ≥ n 2 , we have that h ′ (β(T [n])) conjectures pad(h(β(τ T [n] )), β(τ T [n] )). Note that this does not imply infinitely many mind changes, as we have that n ≥ n 1 and, with it, . In both cases, we have that h ′ Ex-learns L from text T .
Since h ′ only makes mind changes when it witnesses a mind change or interruption of h and since h serves the restrictions δ on Txt(L) and δ ′ on Txt(S), we also have that h ′ serves those. This concludes the proof.
We make use of this result when proving our main generalizations. However, we first have to deal with the following issue. Ideally, when generalizing the result of Kötzing and Palenta (2016), we would obtain that any (possibly globally) target-cautious G-learner is as powerful as a (possibly globally) witness-based one. However, the issue arises as globally target-cautious learners are extremely weak. In fact, as they may never overgeneralize they can solely learn finite languages, as we show in the following theorem.
It remains to be shown that if L ∈ [τ (Caut Tar )TxtGBc] then L ⊆ Pow Fin (N). We show this by contradiction. To that end, let h be a learner such that L ⊆ τ (Caut Tar )TxtGBc(h) and assume there exists an infinite L ∈ L. Let T ∈ Txt(L), and let n be such that W h(T [n]) = L. Now, considering the text Thus, h is not Caut Tar on text T ′ . This is a contradiction, so we have This concludes the proof.
We overcome this issue by observing that witness-based behaviour may be obtained whenever the learner is defined, solely on languages it is supposed to learn it needs to be target-cautious. The idea is that, when being target-cautious, any wrong guess may still be changed when observing a missing element from the target-language. Now we can provide the general versions of the discussed results of Kinber and Stephan (1995), Kötzing and Palenta (2016) and Kötzing and Schirneck (2016). Starting with Gold-style learners, Kötzing and Palenta (2016) show that target-cautious Gold-style learners may be assumed weakly monotone, cautious and conservative without losing learning power. We show that these even may be assumed witness-based. Furthermore, within a single theorem, we show that this is not only the case when dealing with partial learners.
Theorem 6 Let I be an R-monoid and S ⊆ Pow(N) closed under subsets. Let L be a class of languages. Then, the following are equivalent.
(1) L can be TxtGWbEx-learned by an I-learner which is Wb also on Txt(S).
(2) L can be TxtGCaut Tar Ex-learned by an I-learner which is defined also on Txt(S).
Proof The direction (1)⇒(2) follows immediately. For the other direction, we follow and expand the proof of [TxtGConvEx] = [TxtGCaut Tar Ex], see Kötzing and Palenta (2016, Thm. 13). Let h ∈ I be a learner and L be TxtGCaut Tar Ex-learnable by h which is also defined on Txt(S). By Theorem 4 we can assume h ∈ I to be syntactically decisive on Txt(L) and Txt(S). Let p ∈ R be such that otherwise.
Note that for all sequences σ we have For given sequences σ and τ , we define Given finite sequences σ, σ ′ and τ , we define the computable predicate Given a sequence σ we can define the learner h ′ as follows. For convenience, for σ = ε, let σ ′ be such that h ′ (σ − ) = p(σ ′ ). Then, we define We motivate the intuition behind the learner h ′ . Given a sequence σ = ε, let σ ′ be the sequence h ′ based its previous guess on. Then, if not consistent, h ′ only changes its mind if there exists an extension τ of σ ′ on which h made a mind change and if there exist elements in content(τ ) not yet enumerated by W |τ |−1 h(σ ′ ) . We first show that h ′ converges on any text for a language L ∈ L. Let L ∈ L and T ∈ Txt(L). Assume h ′ does not converge on T . Let (p(σ ′ i )) i∈N be the sequence of hypotheses output by h ′ on text T . As h ′ makes infinitely many mind changes, the sequence (p(σ ′ i )) i∈N contains infinitely many different hypotheses. For any i where h ′ (T [i]) makes a mind change, the corresponding hypothesis is, for apt τ i , p(τ i ⌢ T [i]) instead of its previous hypothesis. Thus, in particular, for infinitely many , as seen in the second case of the definition of h ′ . This contradicts the convergence of h on T ′ .
Next, we show that h ′ converges to the correct hypothesis on T . Let n 0 be the point of convergence, that is, n 0 is minimal such that for all n ≥ n 0 we have We consider the following two cases.
2. Case: σ ′ is not a locking sequence for h on L. As h ′ converges, we have for all n and τ with We distinguish the following cases.

Case: For all
. So, h never changes its mind on an extension of σ ′ within the language L, but σ ′ is no locking sequence either. This means that W h(σ) = L, meaning that h does not learn L on any text starting with σ ′ , a contradiction.
2.3. Case: There exists n ∈ N ≥n 0 with ¬(content(σ ′ ) = content(T [n])) and there exists τ ∈ L * , σ ′ ⊆ τ such that h(σ ′ ) = h(τ ). Let n 1 be minimal such that ¬(content(σ ′ ) = content(T [n 1 ])). Let n ≥ n 1 . Note that content(σ ′ ) content(T [n]) holds. We proceed by showing L ⊆ W h(σ ′ ) and afterwards W p(σ ′ ) = W h(σ ′ ) . As h is Caut Tar , this suffices in order to show L = W p(σ ′ ) . Let τ ∈ L * , σ ′ ⊆ τ such that h(σ ′ ) = h(τ ) as assumed to exist in this case. Then, for . Since this holds for all x ∈ L \ content(σ ′ ) and since (4) and, as just shown, However, as n > n 1 , content(σ ′ ) = content(T [n]) does not hold and neither does Finally, we show that h ′ is witness-based on Txt(L) and Txt(S). Let σ be a sequence where h ′ makes a mind change, that is, for some Furthermore, as later hypotheses of h ′ are built on extensions of τ ⌢ σ, this is sufficient in order to show that h ′ is witness-based. We proceed with showing content(σ) In particular, as content(σ ′ ) content(σ), W p(σ ′ ) has to enumerate content(σ) by means of the second condition in the definition of p. Let t > |τ | − 1 be a step where such a enumeration could take place, that is, For example, if one is to take I = R (which is an R-monoid), one gains the same observation as for partial learners, namely that target-cautious learners may be assumed witness-based. However, this theorem provides another interesting result. With I = R and S = Pow(N), Theorem 6 shows that any anywhere defined learner (that is, any total learner) may be assumed everywhere (that is, globally) witness-based. However, it maintains its learning power solely on languages it learns target-cautiously. With the observation of Kötzing and Palenta (2016) that any G-learner may be assumed total, we get this property even for arbitrary learners instead of total ones.
Using our general framework we extend this result even further. Kötzing and Schirneck (2016) show that (possibly partial) target-cautious partially set-driven learners may be assumed witnessbased. We observe that this also holds true for a variety of different learners.
Theorem 7 Let I be an R-monoid and S ⊆ Pow(N) closed under subsets. Furthermore, let L be a class of languages. Then, the following are equivalent.
(1) L can be TxtPsdWbEx-learned by an I-learner which is Wb also on Txt(S).
(2) L can be TxtPsdCaut Tar Ex-learned by an I-learner which is defined also on Txt(S).
Proof The direction (1)⇒(2) follows immediately. For the other direction, we follow the proof of [TxtPsdWbEx] = [TxtPsdCaut Tar Ex], see Kötzing and Schirneck (2016, Thm. 3.5). Let h ∈ I be a learner and L be TxtPsdCaut Tar Ex-learnable by h which is also defined on Txt(S). First, we show that we may assume h to be strongly locking.

Claim 1
The learner h may be assumed strongly locking.

Proof [Claim]
We adapt the proof of Kötzing and Schirneck (2016) for partial Psd-learners. For any finite set D and any number t ≥ |D|, define the learnerĥ(D, t) = h(D, 2t). As h ∈ I, so isĥ. Furthermore,ĥ is target-cautious as h is. Let L ∈ L and let T ∈ Txt(L). Note that h learns L on textT defined as, for any i ∈ N,T (2i) = T (i) ∧T (2i + 1) = #.
Furthermore, note that, for any n ∈ N, As h learns L on textT , there exists n 0 such that, for all n ≥ n 0 , we have h * (T [n]) = h * (T [n 0 ]) and W h * (T [n]) = L. In particular, this holds for all even n and together with Equation (5), we get that alsoĥ converges correctly on text T . It remains to be shown thatĥ is strongly locking. Let L ∈ L and let σ 0 be a locking sequence of the starred learner h * . Let T ∈ Txt(L). We show thatĥ is locking on T . Let n 0 ≥ |σ 0 | such that content(T [n 0 ]) ⊇ content(σ 0 ). We show that (content(T [n 0 ]), n 0 ) is a locking information. Let n ≥ n 0 . As there exists a sequence τ ∈ L * such that content(σ ⌢ τ ) = content(T [n]) and |σ 0 | + |τ | = 2n. As σ 0 is a locking sequence for h * we get So,ĥ is strongly locking.
Now, we build the desired TxtPsdWbEx-learner h ′ which is also witness-based on Txt(S) in the following way. Following Kötzing and Schirneck (2016), we mimic the strongly locking learner h. Given some information, the main idea is to delay until refutation, that is, we wait with abandoning a hypothesis until we see some datum witnessing the current hypothesis being incorrect. Secondly, we search for locking information, a method often applied when mimicking learners. This way, we assure correct convergence. Furthermore, to overcome the problem of multiple possible previous hypotheses, we assume the information appeared in strictly ascending order without pause symbols, that is, we simulate h on ascending text. Next, we poison hypotheses when witnessing them being incorrect, that is, once a possible later mind change is witnessed, we stop enumerating more data into this hypothesis. Lastly, we delay until consistency, that is, we do not accept a new hypothesis until we see it to be consistent with new data.
For this sketched strategy to work, we have to overcome two major problems. Firstly, when simulating h on ascending text, we run into problems learning finite languages, as the learner may learn such languages way after all data has been presented to it. We overcome this problem by searching for such mind changes and returning an index for the finite language in question, unless we have found a consistent hypothesis before. As h is target-cautious, once a hypothesis overgeneralizes the information it got, the given information cannot be the final target.
The second problem is that partially set-driven learners have multiple previous hypotheses. We solve this problem by assuming the information to be presented in strictly ascending order. However, this poses the following difficulty. For example, given the sequence 0, 1, 3, 2, our new learner may base its hypothesis on {0, 1, 2} without ever considering {0, 1, 3} as possible input. We oppose this problem in the following way. For finite D, we only use a conjecture h(D, |D|) when it contains at least D and one additional element. Furthermore, we remove all data from this this conjecture which is less than max(D), but not in D. This way, we may change the conjecture built on {0, 1, 3} as it does not contain the 2. Additionally, conjectures based on {0, 1, 2} will contain all of {0, 1, 2} as we only use conjectures which are consistent. Since we can determine consistency only in the limit, we have to delay conjectures until consistency.
In order to define the desired learner, we continue with the formal details. For any given D, D ′ ⊆ N and t ′ ∈ N such that (D, |D|) (D ′ , t ′ ), define the predicate The function refuted tells us whether there is a mind change between (D, |D|) and (D ′ , t ′ ). Fix, for any set S and any x ∈ N, the notation S >x for the set of all elements in S which are larger than x. The set S ≤x is defined analogously. Furthermore, let c ∈ R such that, for any hypothesis e and any finite set D, The function c(e, D) enumerates the set D itself and all elements of W e which are larger than max(D). Lastly, let p ∈ R such that otherwise.
The function p enumerates the same as W h(D,|D|) until, if ever, a mind change is witnessed. Then, it stops enumerating more data. We combine the previously introduced functions by letting, for all finite D ⊆ N, q(D) := c(p(D), D). The function q does exactly what we explained before: while no mind change is witnessed, it enumerates all of W h(D,|D|) which is larger than any element given and the set D itself as well.
To assure convergence later on, we show for all L ∈ L and all k ∈ N, we have that if (L[k], k) is a locking information of h on L, then W q(L[k]) = L. Let (L[k], k) be a locking information. Thus, no refutation will be witnessed on any extending information of the language. Hence, W p(L) = W h(L[k],k) = L. Since L[k] contains the information in ascending order, we have In order to define that learner h ′ we need the following decision procedure. We show that for D, D ′ and t ′ such that D ′ [|D|] = D and refuted(D, D ′ , t ′ ), there exists an algorithm taking D, D ′ and t ′ as input and deciding D ′ ⊆ W q(D) . Namely, the algorithm computes the finite set otherwise.
Now, either D ′ ⊆ A, in which case D ′ ⊆ W q(D) . Otherwise D ′ ⊆ W q(D) , as the enumeration would have to stop before enumerating the last element of D ′ because it would make the mind change visible.
Lastly, we need the following notation. For any set D and any k ∈ N, we use D[k] to denote the set of the first k elements of D (in ascending order). If k > |D|, we let D[k] = D. Furthermore, let σ D be the sequence of elements in D in strictly ascending order without pause-symbols.
Finally, we can formalise h ′ as in Algorithm 1. First, note that h ∈ I by construction. We proceed by showing that L ⊆ TxtPsdEx(h ′ ). For L ∈ L, we distinguish the following cases.
1. Case: L is finite. We, again, distinguish multiple cases. Finally, we show that h ′ is witness-based on Txt(L) and Txt(S). Let T be an according text. For all i ∈ N, let D i = content(T [i]). Furthermore, let k i be such that Algorithm 1 on information . We first note that, for all i ∈ N, we have and does not contain any other elements which are smaller than any element thereof. This is immediate if the output is ind(D i [k i ]). When the output is q(D i [k i ]), the corresponding consistency has to be witnessed, see line 1 and line 1, respectively. Smaller elements cannot be enumerated since q applies function c. This proves that Equation 6 holds. Now, let a, b and d, with a < d ≤ b, be such that h ′ (D a , a) = h ′ (D d , d). We show We distinguish the following cases.
It is straightforward to verify that, by Algorithm 1, the only way this is possible is by having x < y. Let x be minimal such. Using Equation (6) it suffices to show that  (D a , a).

Thus, as in the previous case, we get
, then there was no mind change between h ′ (D a , a) and h ′ (D b , b), a contradiction to what we assumed. As refuted(D a [k a ], D a , a) and the predicate refuted is monotone in its second and third component, we get Otherwise, we get that k b is such that, with k 0 as chosen by Algorithm 1 on (D b , b), Since we assumed a mind change between h ′ (D a , a) and (6), as desired.

Case
there could not be a mind change between h ′ (D a , a) and h ′ (D b , b). Hence, D a D b . Now, we also have k b > k a . By Equation (6) . Altogether, as desired we have 3.3. Case: h ′ (D a , a) = q(D a [k a ]) from line 1. By assumption, q(D a [k a ]) was abandoned until In this case, we have This is what we desired for.
This result shows that a similar situation as for G-learners holds true for Psd-learners. Admittedly, it is not true that every Psd-learner may be assumed total, as for example is shown by Kötzing and Schirneck (2016) who provide an example of such a learner. However, the work of Doskoč and Kötzing (2020) shows that, in particular, Gold-style target-cautious learners may be assumed partially set-driven. This result does not suffice for our needs however, as it is only stated for (possibly) partial learners. We extend this result within our framework to fit our needs and obtain a powerful normal form for partially set-driven witness-based learners, see Corollary 9.
Theorem 8 Let I be an R-monoid and S ⊆ Pow(N) closed under subsets. Furthermore, let L be a class of languages. Then, the following are equivalent.
(1) L can be TxtGCaut Tar Ex-learned by an I-learner which is defined also on Txt(S).
(2) L can be TxtPsdCaut Tar Ex-learned by an I-learner which is defined also on Txt(S).
Proof We generalize the proof of [TxtGCaut Tar Ex] = [TxtPsdCaut Tar Ex] as can be found in Doskoč and Kötzing (2020, Thm. 2). The direction (2)⇒(1) is immediate. For the other, let h ∈ I be a learner which TxtGCaut Tar Ex-learns L and is defined on Txt(S). To ensure correct learning on Txt(L), we define a learner h ′ to search for the minimal, possible locking sequence given a finite set D and t ≥ 0 as information. This will also maintain h ′ being defined on Txt(S). Formally, with D ≤t # being the set of all sequences of elements in D # := D ∪ {#} of at most length t, we define h ′ as Obviously, if h is defined on T ∈ Txt(S) then so is h ′ . Next, we show that h ′ TxtGCaut Tar Exlearns L. Let L ∈ L and let T ∈ Txt(L). By Blum and Blum (1975) there exists a locking sequence σ for h on L. Let σ 0 be a minimal such locking sequence. Now, let n 0 be large enough such that, with D 0 := content(T [n 0 ]) for notational convenience, • content(σ 0 ) ⊆ D 0 , • |σ 0 | ≤ n 0 and As h ′ mimics h on sequences in L * , we also have that h ′ is Caut Tar .

Corollary 9 We have that [τ (Wb)TxtPsdEx] = [TxtGCaut Tar Ex].
This result cannot be extended to set-driven learners, as these are known to be weaker than partially set-driven ones, see Kinber and Stephan (1995) or Doskoč and Kötzing (2020). Another difference is that set-driven learners may be assumed conservative, weakly monotone and cautious without loss of generality, compare the results of Kinber and Stephan (1995) and Kötzing and Palenta (2016). Nonetheless, we again provide a general result including witness-based learners.
Theorem 10 Let I be an R-monoid and S ⊆ Pow(N) closed under subsets. Let L be a class of languages. Then, the following are equivalent.
(1) L can be TxtSdWbEx-learned by an I-learner which is Wb also on Txt(S).
(2) L can be TxtSdEx-learned by an I-learner which is defined also on Txt(S).
Proof The direction (1)⇒(2) is immediate. For the other, we follow the proof of [TxtSdEx] = [TxtSdConvEx], see Kinber and Stephan (1995, Thm. 7.1). Let L be TxtSdEx-learned by an I-learner h which is defined on Txt(S). By Theorem 4, we may assume h ∈ I to be syntactically decisive on Txt(L) and Txt(S). We show that L can be TxtSdWbEx-learned by an I-learner h ′ which is Wb on Txt(S).
In order to define learner h ′ , we need the following auxiliary function. For a set D and x ∈ N, we write D >x for the set of all elements in D which are larger than x. Analogously, we use the notation D <x for the set of all elements in D which are less than x. Then, for finite D ⊆ N, we define p as Intuitively, h ′ mimics h on the smallest set (sorted in ascending order) on which no mind change is witnessed. There, it only enumerates larger elements which do not cause a mind change.
We show that h ′ TxtSdWbEx-learns L and is witness-based on Txt(S). First, we show that h ′ TxtSdEx-learns L. Let L ∈ L and let D 0 ⊆ L be a locking set for h on L. Without loss of generality, we may assume that (L \ D 0 ) <max(D 0 ) = ∅, that is, there are no elements smaller than max(D 0 ) which are in L but not in Lastly, we show that h ′ is Wb on Txt(L) and Txt(S). Let T be an according text. Let n 1 < n 2 and D 1 = content(T [n 1 ]) and We distinguish the following cases.
. Note that these are not equal to h(D ′ 1 ) = h(D 1 ) as h is syntactically decisive. Thus, as D ′ 3 . By the search h ′ conducts upon choosing its hypothesis, the case D ′ 1 \ D ′ 3 = ∅ cannot be realized. Thus, the proof is concluded.
Immediately, we see that any total Sd-learner may be assumed globally witness-based and any (possibly) partial Sd-learner may be assumed witness-based on the languages it learns. In contrast to Gand Psd-learners, we show set-driven learners may not be assumed total in general. We provide a separating class using self-learning classes as presented in Case and Kötzing (2016).
For finite D, let k D = max(π 2 (D)) and otherwise.
Intuitively, learner h waits with its decision until it sees what a possible learner ϕ e ′ does. Then, it outputs its hypothesis accordingly. Let L = TxtSdEx(h) and assume there exists some total learner h ′ such that L ⊆ RTxtSdEx(h ′ ). Let e ′ be such that ϕ e ′ = h ′ . Using ORT, there exists e such that W e = { e, e ′ , i : i ∈ N ∧ Q(e, e ′ , i)}.
We show that we can find a language which h learns, but h ′ cannot. We distinguish the following cases.
1. Case: W e is infinite. Then h learns W e as it, given finite non-empty D ⊆ W e , outputs e. That is the correct behaviour. On the other hand, h ′ cannot learn W e as it makes infinitely many mind changes on the text T : n → e, e ′ , n .
So, h ′ cannot distinguish between L 1 and L 2 and, thus, is not able to learn both languages simultaneously.
Altogether, we obtain the following normal form for explanatory set-driven witness-based learners. Any (total) set-driven learner may be assumed (globally) witness-based, respectively. However, total set-driven learners lack the learning power of their (possibly) partial counterpart.

Corollary 12
The following equalities hold, while the two classes separate.

Semantic Witness-based Learning
Transitioning the results of the previous section to behaviourally correct learners is not immediate since the connection between cautious, weakly monotone and semantically conservative, the semantic counterpart to conservative learning, learners is yet to be discovered in this setting. The work of Doskoč and Kötzing (2020) shows that (target-) cautious learners solely rely on the content of the information given, that is, they may be assumed set-driven in general. We show that the same holds true for semantically witness-based learners, the semantic counterpart to witness-based learners. Expanding the findings of , who show that semantically conservative learners may be assumed semantically witness-based, we show the main result of this section, namely that globally semantically witness-based behaviourally correct Sd-learners are as powerful as (possibly partial) Gold-style semantically conservative ones.
We observe that the mentioned relaxation of constraints works in three ways. Firstly, we may vary the information we give to the learner without forfeiting learning power, that is, fullinformation learners are equally powerful as set-driven ones. Secondly, we may swap between the requirement of semantically witness-based and semantically conservative learning. Lastly, we may assume these restrictions to hold globally, that is, on arbitrary text. In this section, Theorems 14 to 16 provide the proof for the following theorem.

Theorem 13 We have that [τ (SemWb)TxtSdBc] = [TxtGSemConvBc].
We give an overview on how we proceed to obtain this result. We show the equality from right to left. Firstly, we show that semantically conservative learners may be assumed so globally. Then, we show that Gold-style globally semantically conservative learners maintain the same learning power even when only basing their hypotheses on the content of the information given, that is, they may be assumed set-driven without loss of learning power. This significantly extends the results of , where such learners are shown to be equally powerful when being partially set-driven or set-driven. Then, lastly, in order to "jump" from globally semantically conservative learning to its semantically witness-based counterpart, we generalize the result for the non-global case provided by .
It follows the detailed process. We start with a TxtGSemConvBc-learner h. Firstly, we show how to make h globally semantically conservative. The idea here is to monitor all possible prior and posterior hypotheses simultaneously. Especially here, Gold-style learners come in handy as they have all information about prior hypotheses at hand. It is important to the learner whether any previous hypothesis is consistent with the current information. If so, the learner, on this hypothesis, simply follows this prior hypothesis' lead. For this to work out, one has to closely monitor what the learner does on future hypotheses. Here, we take advantage of a peculiar property of consistent semantically conservative learners. Such learners need to include all seen data while not overgeneralizing the target language, meaning that finite languages are learnt as soon as all information of it is seen. Thus, it suffices to just consider information without repetition or pause-symbols. Hence, even a check for all possible future hypotheses, which usually is not achievable for Gold-style learners as the crucial correct mind change may come way after all data is seen, is possible in this scenario. The following theorem holds. For the other, let h be a learner and let L = TxtGSemConvBc(h). Without loss of generality, we may assume that h is consistent, see . We provide a learner h ′ which τ (SemConv)TxtGBc-learns L.
We do so with the help of an auxiliary τ (SemConv)TxtGBc-learnerĥ, which only operates on sequences without repetitions or pause symbols. For convenience, we omit explicitly mentioning pause symbols. When h ′ is given a sequence with repetitions, say (7, 1, 5, 1, 4, #, 3, 1), it mimicŝ h given the same sequence without duplicates, that is, h ′ (7, 1, 5, 1, 4, #, 3, 1) =ĥ (7,1,5,4,3). First, note that this mapping of sequences preserves the ⊆-relation on sequences, thus making h ′ also a τ (SemConv)-learner. Furthermore, it suffices to focus on sequences without duplicates. This is the case since consistent, semantically conservative learners cannot change their mind when presented a datum they have already witnessed (or a pause symbol). Thus,ĥ will be presented sufficient information for the learning task, which then again is transferred to h ′ . With this in mind, we only consider sequences without repetitions (or pause symbols) for the entirety of this proof. Sequences where duplicates may potentially still occur (for example when looking at the initial sequence of a text) are also replaced as described above. To ease notation, given a set A, we write S(A) for the subset of A * # where the sequences do not contain repetitions. Now, we define the auxiliary learnerĥ.
Consider the learnerĥ as in Algorithm 2 with parameter h. Given some input σ, the intuition is the following. Onceĥ, on any previous sequence σ ′ , is consistent with the currently given information content(σ), the learner only enumerates the same as such hypotheses (see lines 2 to 2). While no such hypothesis is found,ĥ does a forward search (see lines 2 to 2) and only enumerates elements if all visible future hypotheses also witness these elements. As already discussed,ĥ operates only on sequences without repetitions, thus making it possible to check all future hypotheses.
First we show that for any L ∈ L and any T ∈ Txt(L) we have, for n ∈ N, Note that, while the (infinite) text T may contain duplicates, the (finite) sequence T [n] does not by our assumption. Now, we show Equation (7) by induction on n. The case n = 0 follows immediately. Assume Equation (7) Algorithm 2: The auxiliary τ (SemConv)-learnerĥ used in the proof of Theorem 14 Parameter: TxtGSemConv-learner h. Input: Finite sequence σ ∈ S(N). Semantic Output: The first inclusion follows as the big union contains all previous hypotheses found in the first ifclause (lines 2 to 2) and as W h(T [n+1]) contains all elements possibly enumerated by the second if-clause (lines 2 to 2). Note that the latter also contains content(T [n + 1]), thus covering the initialization. The second inclusion follows by the induction hypothesis and semantic conservativeness of h.
We continue by showing thatĥ TxtGBc-learns L. To that end, let L ∈ L and T ∈ Txt(L). We distinguish the following two cases. Thus, elements enumerated by Wĥ (T [n 0 ]) cannot be enumerated by the first if-clause (lines 2 to 2) but only by the second one (lines 2 to 2). We show Wĥ (T [n 0 ]) = L. The ⊆-direction follows immediately from Equation (7). For the other direction, let t ′ be the current step of enumeration. As T [n 0 ] is a Bc-locking sequence, we have, for all τ ∈ S(W t ′ h(T [n 0 ]) ), Thus, at some step t, E t+1 ← W t ′ h(T [n 0 ]) and, then, the enumeration continues with t ′ ← t ′ +1. In the end we have L ⊆ Wĥ (T [n 0 ]) and, altogether, L = Wĥ (T [n 0 ]) .
It remains to be shown thatĥ is SemConv on arbitrary text T ∈ Txt. The problem is that when a previous hypothesis becomes consistent with information currently given, the learner may have already enumerated incomparable data in its current hypothesis. This is prevented by closely monitoring the time of enumeration, namely by waiting until the enumerated data will certainly not cause such problems. We prove thatĥ is τ (SemConv) formally. Let n < n ′ be such that  and continues to follow Wĥ (T [n]) . Now, observe that t x < t content as x ∈ Wĥ (T [n ′ ]) but x / ∈ Wĥ (T [n]) . But then which must be witnessed in order for Wĥ (T [n]) to enumerate content(T [n ′ ]) via the second ifclause (lines 2 to 2), that is, to get content(T [n ′ ]) ⊆ Wĥ (T [n]) . This contradicts x / ∈ Wĥ (T [n]) , concluding the proof.
Applying this result, we may assume h to be globally semantically conservative. Next, we show that even restricting the learners memory does not affect its learning power. In particular, we show that h may be assumed set-driven. This significantly extends the result shown by  where (not necessarily globally) semantically conservative partially set-driven learners may be assumed set-driven. While the latter result relies on such learners requirement to include all seen data while not being allowed to overgeneralize, our result originates from another fact. Being semantically conservative and therefore consistent  at the same time means that, given any information, whenever the learner h overgeneralizes it may not change its mind on information from this overgeneralization. Thus, we may pretend that the information given came in a certain, for the sake of simplicity say ascending, order. Then, if the learner suggests an element out of this order in its hypothesis, one simply checks whether learner guesses the current information extended by this element on the shortest string of information not containing this element but maintaining the order. If so, both hypotheses are the same and thus both may include this element. Otherwise, the learner skips that element. We provide the rigorous proof.
Theorem 15 We have that Proof We show all three equalities at once. Let h be a learner and L = τ (SemConv)TxtGBc(h). Without loss of generality, we may assume h to be globally consistent, as shown in . We provide a learner h ′ such that L ⊆ τ (SemConv)TxtSdBc(h ′ ). To that end, we introduce the following auxiliary notation which we use throughout this proof. For each x ∈ N and each finite set D ⊆ N, let The latter definition can be extended to ≤, > and ≥, as well as infinite sets in a natural way. Now, let h ′ be such that Intuitively, h ′ (D) simulates h assuming it got the information in the canonical order, that is, h ′ (D) simulates h(σ D ). All elements x ∈ W h(σ D ) such that x > d can be enumerated, as any later, consistent hypothesis will do so as well. If x < d, then we check whether the learner h given the canonical sequence up to x is consistent with D ∪ {x}, that is, whether D ∪ {x} ⊆ W h(σ (D <x ) ) . If so, we enumerate x as it will be done by the previous hypotheses as well. Note that, for each finite D ⊆ N, we have We proceed by proving that h ′ τ (SemConv)TxtSdBc-learns L. First, we show the TxtSdBcconvergence. The idea here is to find a Bc-locking sequence of the canonical text. Doing so ensures that even if elements are shown out of order they will be enumerated as h will not make a mind change and thus the consistency condition will be observed. To that end, let L ∈ L. We distinguish whether L is finite or not.
1. Case: L is finite. We show that W h ′ (L) = L. By definition of h ′ , we have L ⊆ W h ′ (L) . For the other inclusion, note that as h is consistent and semantically conservative (which in particular implies it being target-cautious), we have that W h(σ L ) = L. Then, by Equation (8), we have that W h ′ (L) ⊆ W h(σ L ) = L, concluding this case.
2. Case: L is infinite. Let T c be the canonical text of L, and let σ 0 be a Bc-locking sequence for h on T c . Such a Bc-locking sequence exists, as h is strongly Bc-locking, see Kötzing et al. (2017, Thm. 7). Let D 0 := content(σ 0 ). For any input D ⊆ L such that D ⊇ D 0 , we show that W h ′ (D) = L. By Equation (8), we get W h ′ (D) ⊆ W h(σ D ) = L. To show L ⊆ W h ′ (D) , let x ∈ L. We distinguish the relative position of x and d.
x > d: In this case we have x ∈ W h ′ (D) by definition of h ′ .
x ≤ d: In this case either x ∈ D and we immediately get x ∈ W h ′ (D) , or we have to check whether D ∪ {x} ⊆ W h(σ (D <x ) ) . Since σ 0 is an initial segment of the canonical text of L, it holds that x > max(content(σ 0 )) and, thus, we get σ 0 ⊆ σ (D<x) . Now W h(σ (D <x ) ) = L, meaning that D ∪ {x} ⊆ W h(σ (D <x ) ) will be observed at some point in the computation. Thus, x ∈ W h ′ (D) in this case as well.
Altogether, we get W h ′ (D) = L and thus TxtSdBc-convergence. It remains to be shown that h ′ is τ (SemConv). Let D ′ ⊆ D ′′ and D ′′ ⊆ W h ′ (D ′ ) . The trick here is that upon checking for consistency with elements shown out of order, the learner has to check the same, minimal sequence regardless whether the input is D ′ or D ′′ . We proceed with the formal proof. Therefore, we expand the initially introduced notation of this proof. For any x ∈ N define Analogously, we use σ ′′ , d ′′ and σ ′′ <x when D ′′ is the underlying set. First, we show that W h(σ ′ ) = W h(σ ′′ ) . Since W h ′ (D ′ ) enumerates D ′′ , that is, D ′′ ⊆ W h ′ (D ′ ) , we have for all y ∈ (D ′′ \ D ′ ) <d ′ that D ′ ∪ {y} ⊆ W h(σ ′ <y ) by definition of h ′ . Thus, we have Note that, if (D ′′ \ D ′ ) <d ′ is empty, then σ ′ <d ′ +1 = σ ′ . Thus, Equation (9) also holds true for otherwise.
Furthermore, it holds true that for any x ≤ m we have By Equations (8) and (9), we have D ′′ ⊆ W h ′ (D ′ ) ⊆ W h(σ ′ ) = W h(σ ′ <m ) . As, by Equation (10), σ ′ <m = σ ′′ <m ⊆ σ ′′ and h is τ (SemConv), we get We conclude the proof by showing that W h ′ (D ′ ) = W h ′ (D ′′ ) . We check each direction separately by checking every possible position of an element, which is a candidate for enumeration, relative to the given information D ′ and D ′′ . ⊇: Let x ∈ W h ′ (D ′′ ) . For x ∈ D ′′ we have x ∈ W h ′ (D ′ ) by assumption. Otherwise, by Equations (8) and (11), we get x ∈ W h(σ ′ ) . Thus, x will be considered in the enumeration of W h ′ (D ′ ) . We distinguish the relation between x and d ′ .
x < d ′ : As d ′ ≤ d ′′ and since x is enumerated into W h ′ (D ′′ ) , we have D ′′ ∪ {x} ⊆ W h(σ ′′ <x ) . We, again, distinguish the relative position of x and m and get . We use h being τ (SemConv) in the steps marked by ( * ). Thus, x ∈ W h ′ (D ′ ) .
Thus, x will be considered in the enumeration of W h ′ (D ′′ ) . We now distinguish between the possible relation of x and d ′′ .
x > d ′′ : In this case x ∈ W h ′ (D ′′ ) by definition of h ′ .
Thus, we may assume h to be globally semantically conservative set-driven. Lastly, by extending the result of , who show that SemWband SemConv-learners are equally powerful for all considered interaction operators, to hold for the global counterpart as well, we see that h remains equally powerful even when being globally semantically witness-based. The following result concludes the proof of Theorem 13 and, therefore, also this section.  Kötzing et al. (2017, Lem. 11), the theorem holds.

Conclusion and Future Work
In this work, we study the behaviour of witness-based learners in different settings. Being a specialization to important restrictions within inductive inference, first studies of witness-based learners have been provided by Kötzing and Schirneck (2016) and . With this work, we provide a thorough investigation of the behaviour of these learners and provide normal forms thereof. In particular, we provide a general framework with which we obtain results for witnessbased explanatory learners with multiple additional restrictions. Most notably, we show that globally witness-based Psd-learners are equally powerful as target-cautious G-learners. Furthermore, we provide results in the behaviourally correct case, showing that globally semantically witnessbased set-driven learners are equally powerful as semantically conservative full-information learners. The latter result is vital in order to obtain a full map for delayable restrictions in the behaviourally correct case, which is left as future work.