betaFeedback

WorksComputer Science

Query Feedback and Teaching for Stable and Certifiable Language Generation

Abstract

Language generation in the limit studies whether a learner observing an enumeration of an unknown target language can eventually generate only valid, previously unseen elements. We study stability, introduced by Kalavasis, Mehrotra, and Velegkas (2025), which requires the generator's infinite output set to eventually remain unchanged, and introduce the stronger notion of certifiability, which requires the generator to determine from its observations that its current output is valid. Drawing on teaching sets in learning theory, we introduce a hierarchy of teaching dimensions for generation under three increasingly strict success criteria: correctness, stability, and certifiability. These dimensions measure the minimum number of selected examples whose appearance guarantees the corresponding success condition. We also study stability and certifiability in the membership-query model of Charikar and Pabbaraju (2025). We characterize stable and certifiable generation, both with and without query feedback, and establish their relationships with uniform generation and identification in the limit. In particular, we give a finite-witness characterization of stable generation, analogous to Angluin's tell-tale characterization of identification, resolving a gap left open by Kalavasis, Mehrotra, and Velegkas (2025). We further compare these generation notions with identification in the limit and contrast their teaching requirements on well-studied language families, including regular and erasing pattern languages.

Introduction

Large Language Models (LLMs) exhibit remarkable capabilities across a wide variety of domains. Yet, despite their empirical success, a rigorous theoretical understanding of how and why these models succeed remains elusive. Because modern LLMs are highly complex systems, developing a mathematical foundation necessitates studying them through clean theoretical abstractions that isolate core phenomena of interest [24, 14, 19, 18, 13, 9].

One such abstraction that has recently gained significant traction is the stylized model of language generation in the limit, introduced by Kleinberg and Mullainathan [14]. Inspired by the classical inductive inference framework of Gold [11] and Angluin [3], this model asks a basic question: when a generative model is trained on a stream of examples from an unknown target language KK belonging to a known countable collection of languages L={L1,L2,…}\mathcal{L} = \{L_1, L_2, \ldots\} over a domain X\mathcal{X}, is there a finite point after which the model consistently produces novel and valid elements of KK? Concretely, the problem is formulated as an online game in which an adversary chooses a target language K∈LK \in\mathcal{L} along with an enumeration x1,x2,…x_1, x_2, \ldots of all elements in KK. At each round tt, after observing St={x1,…,xt}S_t = \{x_1, \ldots, x_t\}, the learner outputs a guess—either a single unseen element yt∈X∖Sty_t \in\mathcal{X} \setminus S_t (element-based generation) or an infinite subset Gt⊆XG_t \subseteq\mathcal{X} of candidate outputs (set-based generation)—and succeeds in the limit if, after some finite round t⋆t^\star, all subsequent outputs are valid for KK.1 The main result of Kleinberg and Mullainathan [14], namely that language generation in the limit is possible for all countable collections of languages, stands in stark contrast to the classical negative results for language identification in the limit, where the learner must eventually pinpoint the exact index of KK in L\mathcal{L} [11, 3]. This separation has sparked a vibrant line of work exploring various facets of language generation, including breadth and density [17, 5, 28, 21, 22], noisy data [32, 4, 25], privacy [26], and memory constraints [15, 7].

Yet, a crucial practical aspect of language generation has remained largely unexplored: the model of Kleinberg and Mullainathan [14] imposes no requirement on the learner to know when it is safe to stop training and start generating. Even though a successful generator is guaranteed to eventually output valid elements after some finite time t⋆t^\star, this convergence time depends on the unknown target language and enumeration, and the learner itself is never aware of whether t⋆t^\star has been reached. In real-world machine learning pipelines, however, practitioners do not train blindly; they continuously track training and validation metrics that inform them about the progress of the run and provide a concrete signal of when training is “complete” and the model can be safely deployed. To capture this phenomenon theoretically, we wish to study language generation in the limit by learners that can eventually certify that they are generating correctly; we call this certifiable language generation.

Closely intertwined with certifiability is a previously studied fundamental property of the learning process, namely stability [17, 16]. In the original setting of Kleinberg and Mullainathan [14], the learning algorithm is permitted to change its mind infinitely often, oscillating indefinitely between different candidate generating sets even after all of them are valid subsets of KK. Stability addresses practical situations in which we would like the training process to eventually converge to a single set to generate from. In fact, stability is a necessary condition for certifiability: once a learner can assess that it is safe to stop training, it can immediately freeze its output and stabilize from that point onward. Conversely, stability alone may not suffice to tell us when to stop training, as a stable generator could converge to a valid set at some finite time t⋆t^\star without ever knowing that the point of stabilization has been reached. Kalavasis, Mehrotra, and Velegkas [17] established a strict separation between stable and non-stable generation even for countable collections, but left open a characterization of when stable generation is possible. Thus, a central goal of our work is to characterize when both stable and certifiable generation can be achieved.

Moreover, we extend the study of stable and certifiable language generation to two natural settings that were recently introduced in the literature: (i) generation with feedback to active queries by the learner [5, 12] and (ii) generation from size-restricted sets of examples provided by the environment [23], akin to teaching sets [8] in the context of concept learning.

(i) Prior work [5, 12] studied settings in which the learner can actively obtain information about the target language KK by asking whether strings xx of its choice are in KK. Since stability and certifiability impose string requirements on language generation, we ask the question in which way query feedback can help to fulfill these requirements.

(ii) Both stability and certifiability require that on every enumeration of the target language KK, the learner eventually reaches a point of (certifiable or non-certifiable) stability, though the time and manner in which this point is reached may depend on the specific order in which examples are presented. An even more appealing scenario is when, for every language K∈LK \in\mathcal{L}, there exists a finite “core” set of examples—which we refer to as a teaching set, borrowing terminology from learning theory [8]—such that as soon as all elements of this set appear in the input stream, the generator is guaranteed to have stabilized (or certified correctness) from that point onward, regardless of the rest of the enumeration. Beyond providing an enumeration-independent guarantee of convergence, the existence of such teaching sets is closely tied to designing data-efficient training curricula. In this work, we seek to understand the exact conditions under which stable generation and certifiable generation can be obtained—with or without teaching sets.

Main Contributions. This paper introduces the notion of certifiable language generation as a natural strengthening of stable generation. We show that certifiability is a strictly stronger requirement than stability alone, as part of a set of separation results establishing a strict hierarchy of the notions of uniform [14, 31], certifiable, stable, and unrestricted language generation, with and without query feedback. Interestingly, under query feedback, stability alone is not a restrictive condition, though certifiability is. Notably, some of our separations are witnessed by the well-studied class of pattern languages [2, 33].

To gain a deeper understanding of the additional difficulty that certifiability imposes over stability, we give characterizations of generation under these two notions, thereby answering an open question of Kalavasis, Mehrotra, and Velegkas [17, 16] asking for a characterization of stable generation. We complement these results by analogous characterizations in the query-augmented learning setting.

Our characterizations in the query-free setting rely on the structure of finite witness sets, akin to tell-tales used in characterizations in the identification setting [3]. Such finite witness sets are closely related to teaching sets studied in learning theory [8]. While teaching sets for language generation were implicitly introduced by [23], we initiate their study in the settings of stable and certifiable generation, again establishing a hierarchy across various notions of generation. In contrast to Li et al.’s [23] result, stating that generation for countable language collections can always be achieved with teaching sets of size 1, we use countable classes to exhibit arbitrarily large separations between teaching set sizes for certifiable generation, stable generation, and generation in the limit. This shows that, in general, larger teaching sets are needed to satisfy stronger requirements on the learning process.

Incidentally, we exhibit a relationship between the size of stable generation teaching sets and the size of finite sets with the so-called non-clashing property, which is known in the context of machine teaching [6], identification in the limit [27], and sample compression [20]. This relationship mirrors an analogous relationship between complexity parameters for identification in the limit [27].

Preliminaries

Let N\mathbb{N} be the set of natural numbers and N0:=N∪{0}\mathbb{N}_0 := \mathbb{N} \cup\{0\}. Fix any countable domain X\mathcal{X}. For any sequence σ∈X∗\sigma\in\mathcal{X}^* we denote by supp⁡(σ)⊆X\operatorname{supp}(\sigma) \subseteq\mathcal{X} the set of elements in σ\sigma. A language LL is consistent with σ\sigma if supp⁡(σ)⊆L\operatorname{supp}(\sigma) \subseteq L. For any σ∈X∗\sigma\in\mathcal{X}^* and finite set TT, we say σ\sigma contains TT if T⊆supp⁡(σ)T \subseteq\operatorname{supp}(\sigma). For any infinite sequence σˉ=(x1,x2,…)\bar{\sigma} = (x_1,x_2,\ldots) and natural number n∈Nn \in\mathbb{N} we denote by σˉn=(x1,…,xn)\bar{\sigma}_n = (x_1,\ldots,x_n) the prefix of length nn of σˉ\bar{\sigma}. The concatenation of finite sequences σ\sigma and σ′\sigma' is denoted by σ⋅σ′\sigma\cdot\sigma'.

Let L\mathcal{L} be a collection of infinite languages over X\mathcal{X}. Denote by BX\mathcal{B}_{\mathcal{X}} the collection of all infinite subsets of X\mathcal{X}. A generator is a sequence G=(Gn)n∈N0\mathcal{G} = (\mathcal{G}_n)_{n\in\mathbb{N}_0}, where, for every n∈N0n \in\mathbb{N}_0, Gn:Xn→BX\mathcal{G}_n : \mathcal{X}^n \to\mathcal{B}_{\mathcal{X}}. For simplicity, we will write G(σ)\mathcal{G}(\sigma) for Gn(σ)\mathcal{G}_n(\sigma), when σ\sigma is a finite sequence of length nn.

A repetition-free enumeration of an infinite language LL is an (infinite) sequence of elements in LL in which each element of LL appears exactly once. Every prefix of a repetition-free enumeration is a repetition-free finite sequence. In generation in the limit, we assume that, at each time step, a previously unseen training datum is presented (alternatively, one may allow for repetitions, which can be ignored by the learner). Therefore, for simplicity, when we use the term enumeration, we implicitly refer to a repetition-free enumeration.

Definition 2.1 ([14]). A collection L\mathcal{L} is generatable in the limit if there is a generator G\mathcal{G} such that, for every K∈LK \in\mathcal{L} and every enumeration σˉ\bar{\sigma} of KK, there exists n∗∈N0n^* \in\mathbb{N}_0 satisfying G(σˉn)⊆K\mathcal{G}(\bar{\sigma}_n) \subseteq K for every n≥n∗n \ge n^*.

Definition 2.2 ([14, 31]). For i∈N0i \in\mathbb{N}_0, a collection L\mathcal{L} is ii-uniformly generatable if there is a generator G\mathcal{G} such that for every K∈LK \in\mathcal{L}, every enumeration σˉ\bar{\sigma} of KK, and every n≥in \ge i we have G(σˉn)⊆K\mathcal{G}(\bar{\sigma}_n) \subseteq K. It is uniformly generatable if it is ii-uniformly generatable for some i∈N0i \in\mathbb{N}_0.

We contrast the notion of generation with the notion of identification, which requires eventual recovery of the whole target, rather than of an infinite subset.

Definition 2.3 ([11]). A collection L\mathcal{L} is identifiable in the limit if there exists a mapping A:X∗→L2A : \mathcal{X}^* \to\mathcal{L}^2 such that, for every K∈LK \in\mathcal{L} and every enumeration σˉ\bar{\sigma} of KK, there is n∗∈N0n^* \in\mathbb{N}_0 satisfying A(σˉn)=KA(\bar{\sigma}_n) = K for every n≥n∗n \ge n^*.

Language collections that are identifiable in the limit can be characterized by assignments of finite sets with a certain structural property, to be defined next.

Definition 2.4 ([3, 6]). Let L\mathcal{L} be a language collection, and let (TL)L∈L(T_L)_{L\in\mathcal{L}} be a family of finite sets such that TL⊆LT_L \subseteq L for every L∈LL \in\mathcal{L}.

(i) (TL)L∈L(T_L)_{L\in\mathcal{L}} is called a tell-tale assignment if TL⊆L′⊆LT_L \subseteq L' \subseteq L implies L′=LL' = L, whenever L,L′∈LL,L' \in\mathcal{L}.

(ii) (TL)L∈L(T_L)_{L\in\mathcal{L}} is called non-clashing if TL⊈L′T_L \nsubseteq L' or TL′⊈LT_{L'} \nsubseteq L for any L,L′∈LL,L' \in\mathcal{L} with L≠L′L \ne L'.

Theorem 2.5 ([3, 27]). For every countable language collection L\mathcal{L}, the following statements are equivalent:

(i) L\mathcal{L} is identifiable in the limit.

(ii) L\mathcal{L} admits a tell-tale assignment of finite sets.

(iii) L\mathcal{L} admits a non-clashing assignment of finite sets.

These characterizations also connect identification in the limit to machine teaching. In the machine teaching literature, the positive non-clash teaching dimension (NCTD+\mathrm{NCTD}^{+}) measures the smallest uniform bound on the sizes of sets in a non-clashing assignment.

Definition 2.6 ([6]). The positive non-clash teaching dimension of a language collection L\mathcal{L} is defined as

NCTD+(L)=inf⁡(TL)L∈L non-clashingsup⁡L∈L∣TL∣.\mathrm{NCTD}^{+}(\mathcal{L}) = \inf_{\left(T_L\right)_{L\in\mathcal{L}}\ \text{non-clashing}} \sup_{L\in\mathcal{L}} |T_L|.

We will later adapt the notion of tell-tale assignment to stable language generation and then show that it is useful to likewise measure the smallest uniform bound on the sizes of such tell-tale sets.

Stable and Certifiable Language Generation

One of our central goals is to model and study language generation with a learner that can eventually certify that it is sufficiently well trained to guarantee correct generation from the target language. Clearly, once such a certificate can be issued, the generator may choose to stabilize on its current output, i.e., no further training is necessary. Stability, which requires the generator to stop changing its output after a finite time, was recently introduced by Kalavasis, Mehrotra, and Velegkas [17]. We will show below that this condition is strictly weaker than our proposed condition of certifiability.

Definition 3.1 ([17]). A collection L\mathcal{L} is stably generatable if there exists a generator G\mathcal{G} such that, for every K∈LK \in\mathcal{L} and every enumeration σˉ\bar{\sigma} of KK, there is n∗∈N0n^{*} \in\mathbb{N}_0 such that for every n≥n∗n \ge n^{*}, we have G(σˉn)=G(σˉn∗)⊆K\mathcal{G}(\bar{\sigma}_n) = \mathcal{G}(\bar{\sigma}_{n^{*}}) \subseteq K.

Definition 3.2. A collection L\mathcal{L} is certifiably generatable if there exist a generator G\mathcal{G} and a certificate c:X∗→{0,1}c : \mathcal{X}^{*} \to\{0,1\} satisfying:

(i) Soundness. For every σ∈X∗\sigma\in\mathcal{X}^{*}, if c(σ)=1c(\sigma) = 1, then G(σ)⊆L\mathcal{G}(\sigma) \subseteq L for every L∈LL \in\mathcal{L} consistent with σ\sigma.

(ii) Eventual certification. For every K∈LK \in\mathcal{L} and every enumeration σˉ\bar{\sigma} of KK, there is n∗∈N0n^{*} \in\mathbb{N}_0 such that c(σˉn∗)=1c(\bar{\sigma}_{n^{*}}) = 1.

Remark 3.3. After certification, the generator may retain its certified output on every extension of the prefix σˉn∗\bar{\sigma}_{n^{*}} on which the certificate was obtained. This preserves soundness, because every language consistent with the extension was also consistent at the time of certification. Thus a certifiable generator can be made stable. Theorem 3.6 will show that the converse is not true in general.

Finite-Witness Characterizations

Pinpointing the structural properties of language classes that are generatable in a given model provides insights into the nature of standardized underlying learning processes. To this end, we derive finite-witness characterizations for stable and certifiable generation, similar to the analogous characterizations for identification, see Theorem 2.5. Our finite witnesses for stable generation satisfy a weakened non-clashing condition, allowing distinct languages to receive the same witness.

Theorem 3.4. A collection L\mathcal{L} is stably generatable if and only if there is an assignment of finite sets TL⊆LT_L \subseteq L, L∈LL \in\mathcal{L}, satisfying:

(i) For every L∈LL \in\mathcal{L},

∣⋂L′∈L: TL′=TLL′∣=∞.(1)\left|\bigcap_{L'\in\mathcal{L}:~T_{L'}=T_L} L'\right|=\infty. \tag*{(1)}

(ii) For every L,L′∈LL,L' \in\mathcal{L}, TL⊆L′T_L \subseteq L', TL′⊆L⟹TL=TL′T_{L'} \subseteq L \Longrightarrow T_L=T_{L'}.

Equation not extracted
(2)

Proof. If direction. Define the generator G\mathcal{G} as follows. For every finite sequence σ\sigma, choose an arbitrary language L∈LL \in\mathcal{L} with TL⊆supp⁡(σ)⊆LT_L \subseteq\operatorname{supp}(\sigma) \subseteq L, and define

G(σ):=⋂L′∈L: TL′=TLL′.\mathcal{G}(\sigma):=\bigcap_{L'\in\mathcal{L}:~T_{L'}=T_L}L'.

If no language L∈LL \in\mathcal{L} with TL⊆supp⁡(σ)⊆LT_L \subseteq\operatorname{supp}(\sigma) \subseteq L exists, define G(σ)\mathcal{G}(\sigma) arbitrarily. Fix a target language K∈LK \in\mathcal{L}. Since TKT_K is finite, every enumeration of KK has a prefix containing TKT_K. Consider any extension σ\sigma of such prefix, satisfying TK⊆supp⁡(σ)⊆KT_K \subseteq\operatorname{supp}(\sigma) \subseteq K. Suppose that some L∈LL \in\mathcal{L} also satisfies TL⊆supp⁡(σ)⊆LT_L \subseteq\operatorname{supp}(\sigma) \subseteq L. Then TL∪TK⊆supp⁡(σ)⊆L∩KT_L \cup T_K \subseteq\operatorname{supp}(\sigma) \subseteq L \cap K. By condition (ii), this implies TL=TKT_L=T_K. Therefore, every language that can be selected by the generator at this point has the same associated set as KK. Consequently, G(σ)=⋂L∈L: TL=TKL\mathcal{G}(\sigma)=\bigcap_{L\in\mathcal{L}:~T_L=T_K}L, which is infinite by condition (i), is contained in KK, and remains unchanged on every subsequent prefix. Hence, L\mathcal{L} is stably generatable.

Only-if direction. Consider a generator G\mathcal{G} that stably generates L\mathcal{L}. Consider a fixed ordering ≺\prec of X\mathcal{X}. For every L∈LL \in\mathcal{L}, we construct a finite sequence σL∈L∗\sigma_L \in L^* in phases and then take TL=supp⁡(σL)T_L=\operatorname{supp}(\sigma_L).

Initialize τL,0=()\tau_{L,0}=(). In phase n≥1n\geq1, let zL,nz_{L,n} be the first element in L∖supp⁡(τL,n−1)L\setminus\operatorname{supp}(\tau_{L,n-1}) according to the ordering ≺\prec, and set ηL,n=τL,n−1⋅zL,n\eta_{L,n}=\tau_{L,n-1}\cdot z_{L,n}. Consider all finite repetition-free sequences ρ\rho over L∖supp⁡(ηL,n)L\setminus\operatorname{supp}(\eta_{L,n}). If there is such a sequence with G(ηL,n⋅ρ)≠G(ηL,n)\mathcal{G}(\eta_{L,n}\cdot\rho)\ne\mathcal{G}(\eta_{L,n}), let ρL,n\rho_{L,n} be the first such sequence in the shortlex order on finite sequences induced by the ordering ≺\prec of X\mathcal{X}, and set τL,n=ηL,n⋅ρL,n\tau_{L,n}=\eta_{L,n}\cdot\rho_{L,n}. Otherwise, stop and define σL:=ηL,n\sigma_L:=\eta_{L,n} and TL:=supp⁡(σL)T_L:=\operatorname{supp}(\sigma_L).

Because each phase includes the least unseen element in the fixed order, an infinite run would enumerate LL with G\mathcal{G} changing its output infinitely many times, contradicting stable generation. Therefore the process terminates after a finite number of phases, and TLT_L is finite.

By the stopping condition, no continuation over L∖TLL\setminus T_L changes the output. Complete σL\sigma_L to an enumeration of LL. The generator outputs G(σL)\mathcal{G}(\sigma_L) on every subsequent prefix, and correctness on this enumeration implies that this set is contained in LL. Thus

G(σL⋅ρ)=G(σL)⊆Lfor every continuation ρ over L∖supp⁡(σL).(3)\mathcal{G}(\sigma_L\cdot\rho)=\mathcal{G}(\sigma_L)\subseteq L\qquad\text{for every continuation }\rho\text{ over }L\setminus\operatorname{supp}(\sigma_L). \tag*{(3)}

We next compare the constructions for two languages L,L′∈LL,L'\in\mathcal{L} such that TL∪TL′⊆L∩L′T_L\cup T_{L'}\subseteq L\cap L'. For the sake of contradiction, suppose σL≠σL′\sigma_L\ne\sigma_{L'}. Let n∈Nn\in\mathbb{N} be the largest index such that τL,n−1=τL′,n−1\tau_{L,n-1}=\tau_{L',n-1}. There are two cases. First observe that since zL,n,zL′,n∈Lz_{L,n},z_{L',n}\in L, we have zL,n⪯zL′,nz_{L,n}\preceq z_{L',n}. Similarly zL′,n⪯zL,nz_{L',n}\preceq z_{L,n}. Thus, zL,n=zL′,nz_{L,n}=z_{L',n}. This indicates that ηL,n=ηL′,n\eta_{L,n}=\eta_{L',n}.

Case 1. Construction of LL or L′L' stops at phase nn. Without loss of generality, suppose that the construction for LL stops and note that the construction of L′L' cannot stop as otherwise σL=σL′\sigma_L=\sigma_{L'}. The extension ρL′,n\rho_{L',n} satisfies G(η⋅ρL′,n)≠G(η)\mathcal{G}(\eta\cdot\rho_{L',n})\ne\mathcal{G}(\eta). It is also consistent with LL and is a sequence of L′∖supp⁡(η)L'\setminus\operatorname{supp}(\eta). Thus, it is also a sequence of L∖supp⁡(η)L\setminus\operatorname{supp}(\eta). This contradicts LL stopping.

Case 2. Both constructions continue, but ρ:=ρL,n\rho:=\rho_{L,n} is not equal to ρ′:=ρL′,n\rho':=\rho_{L',n}. Without loss of generality, suppose ρ\rho comes first in the shortlex order. Observe that supp⁡(ρ)⊆L∖supp⁡(η)\operatorname{supp}(\rho)\subseteq L\setminus\operatorname{supp}(\eta) and that G(η⋅ρ)≠G(η)\mathcal{G}(\eta\cdot\rho)\ne\mathcal{G}(\eta). Thus, ρ\rho was an available continuation of η\eta for L′L' that would change the output of G\mathcal{G} as well. Hence, it should have been chosen before ρ′\rho' contradicting the rule of selecting the first such continuation in shortlex order.

::: Since neither case is possible, the two constructions agree in every phase and thus σL=σL′\sigma_L = \sigma_{L'}. Therefore, TL=TL′T_L = T_{L'}. This proves condition (ii).

Finally, fix L∈LL \in\mathcal{L}. Whenever TL′=TLT_{L'} = T_L, these sets are mutually consistent with LL and L′L', so the preceding argument gives σL′=σL\sigma_{L'} = \sigma_L. Applying (3) to each such L′L' yields G(σL)⊆⋂L′∈L:TL′=TLL′G(\sigma_L) \subseteq\bigcap_{L' \in\mathcal{L}:T_{L'}=T_L} L'. Since G(σL)G(\sigma_L) is infinite, this proves condition (i) and completes the proof. □

The following characterization of certifiable generatability is not difficult to prove (see Appendix A); the standardized generator for the “if” direction always simply outputs the intersection of all languages in L\mathcal{L} that are consistent with the observed data whenever the intersection is infinite.

Theorem 3.5. A collection L\mathcal{L} is certifiably generatable if and only if, for every K∈LK \in\mathcal{L}, there is a finite set TK⊆KT_K \subseteq K such that

∣⋂L∈L:TK⊆LL∣=∞.(4)\left|\bigcap_{L \in\mathcal{L}:T_K \subseteq L} L\right| = \infty. \tag*{(4)}

These characterizations now help to establish the following hierarchy of requirements on language generation; see also Figure 1 for a complete hierarchy including notions introduced in § 4.

Hierarchy of language generation

Figure 1. Hierarchy of language generation. A path from AA to BB exists if and only if every language family having a generator/learner of type AA also has a generator/learner of type BB.

Theorem 3.6. For every collection L\mathcal{L} of infinite languages, the following implications hold.

L is uniformly generatable⟹L is certifiably generatable.L is certifiably generatable⟹L is stably generatable.L is stably generatable⟹L is generatable in the limit.\begin{aligned} \mathcal{L}\text{ is uniformly generatable} &\Longrightarrow\mathcal{L}\text{ is certifiably generatable}.\\ \mathcal{L}\text{ is certifiably generatable} &\Longrightarrow\mathcal{L}\text{ is stably generatable}.\\ \mathcal{L}\text{ is stably generatable} &\Longrightarrow\mathcal{L}\text{ is generatable in the limit.} \end{aligned}

Every implication is strict.

Proof. (Sketch.) Implications A⇒BA \Rightarrow B are shown by standardizing generators witnessing AA so as to satisfy the criteria for BB. Strictness is shown using the class of all languages {2,4,…,2i}∪{2i(2k−1)−1:k∈N}\{2,4,\ldots,2i\} \cup\{2^i(2k-1)-1:k\in\mathbb{N}\} for the first implication; the class of all languages N∖{i}\mathbb{N}\setminus\{i\} for the second implication; and the class of all languages N∖{i}\mathbb{N}\setminus\{i\} plus the language N\mathbb{N} (which was also used by [16]) for the third implication. See Appendix A for a full proof. □

Separations Witnessed by Families of Pattern Languages

It is not difficult to construct language families that are stably or certifiably generatable, but are not identifiable in the limit. For instance, any language collection with a common infinite intersection is 1-uniformly generatable. Notably though, we will show that similar separations also arise for natural structured language families, specifically, for classes of (erasing) pattern languages, which we will introduce next, following the original definitions by Angluin [2] and Shinohara [33].

Let Σ\Sigma be a finite alphabet with ∣Σ∣≥2|\Sigma| \ge2 and let Z\mathcal{Z} be a countable set of variables disjoint from Σ\Sigma. A pattern is a finite word α∈(Σ∪Z)+\alpha\in(\Sigma\cup\mathcal{Z})^+ containing at least one variable.6 An erasing substitution fixes the symbols of Σ\Sigma and maps each variable to an arbitrary word in Σ∗\Sigma^*, possibly the empty word ε\varepsilon. It extends to a homomorphism on patterns. The corresponding erasing pattern language is

LE(α)={h(α):h is an erasing substitution}.L_E(\alpha) = \{h(\alpha): h\text{ is an erasing substitution}\}.

We write ePΣ_\Sigma for the collection of these languages, and eTFPΣ_\Sigma for the subcollection defined by nonempty terminal-free patterns α∈Z+\alpha\in\mathcal{Z}^+. All these languages are infinite.

While uniform generation is a very strong requirement, for binary alphabets, the class eTFPΣ\mathrm{eTFP}_{\Sigma} is a “natural” language family that is 2-uniformly generatable, but not identifiable in the limit. 2-uniform generatability is shown by constructing an infinite subset of the target language LL directly from the first non-empty word observed in the enumeration of LL; see Appendix § 8 for details.

Theorem 3.7. The collection eTFPΣ\mathrm{eTFP}_{\Sigma} is certifiably generatable and 2-uniformly generatable, but is not 1-uniformly generatable, and, when ∣Σ∣=2|\Sigma| = 2, not identifiable in the limit.

Allowing terminal symbols results in a class that is no longer uniformly, but still stably generatable. The proof details are more involved than for Theorem 3.7 and are also provided in Appendix § 8.

Theorem 3.8. The collection ePΣ\mathrm{eP}_{\Sigma} is stably generatable, but is not uniformly generatable, and, when ∣Σ∣∈{2,3,4}|\Sigma| \in\{2, 3, 4\}, not identifiable in the limit.

Stable and Certifiable Language Generation with Query Feedback

Since stable and certifiable generation is difficult to achieve even for some structurally simple language classes, it is natural to ask whether feedback can help the learner. We therefore define and analyze stability and certifiability in the membership-query model of Charikar and Pabbaraju [5], which was later studied by Hanneke et al. [12]. In this model, at round nn, the generator observes the initial segment σˉn=(x1,…,xn)\bar{\sigma}_n = (x_1,\ldots,x_n) of an enumeration σˉ\bar{\sigma} of the target language KK, chooses a query yn∈Xy_n \in\mathcal{X} based on σˉn\bar{\sigma}_n and the previous query answers, and receives an=1{yn∈K}a_n = \mathbf{1}\{y_n \in K\}. The generator’s output may depend on the full interaction history (σˉn,αˉn)(\bar{\sigma}_n,\bar{\alpha}_n), where αˉ=(a1,a2,…)\bar{\alpha} = (a_1,a_2,\ldots). The query strategy is fixed as part of the generating procedure, and hence the queried points can be reconstructed from the interaction history. We first recall the set-output version of generation with query feedback introduced by Hanneke et al. [12].

Definition 4.1 ([5]). A query-feedback generator consists of a query strategy and a sequence of maps G=(Gn)n∈N0\mathcal{G} = (\mathcal{G}_n)_{n\in\mathbb{N}_0} where for every n∈N0n \in\mathbb{N}_0, Gn:Xn×{0,1}n→BX\mathcal{G}_n : \mathcal{X}^n \times\{0,1\}^n \to\mathcal{B}_{\mathcal{X}}. It generates L\mathcal{L} in the limit with query feedback if, for every K∈LK \in\mathcal{L} and every enumeration σˉ\bar{\sigma} of KK, there exists n∗∈N0n^* \in\mathbb{N}_0 satisfying G(σˉn,αˉn)⊆K\mathcal{G}(\bar{\sigma}_n,\bar{\alpha}_n) \subseteq K for all n≥n∗n \ge n^*.

We generalize this model to stable and certifiable generation with query feedback.

Definition 4.2. A collection L\mathcal{L} is stably generatable with query feedback if there is a query-feedback generator G\mathcal{G} such that, for every K∈LK \in\mathcal{L} and every enumeration σˉ\bar{\sigma} of KK, there exists n∗∈N0n^* \in\mathbb{N}_0 satisfying G(σˉn,αˉn)=G(σˉn∗,αˉn∗)⊆K\mathcal{G}(\bar{\sigma}_n,\bar{\alpha}_n) = \mathcal{G}(\bar{\sigma}_{n^*},\bar{\alpha}_{n^*}) \subseteq K for every n≥n∗n \ge n^*.

The notion of certifiability is defined analogously to the no-feedback setting, except that the certificate may now depend on both the observed positive examples and the answers to the membership queries. Thus, when certification occurs, the current output must be valid for every language consistent with the entire interaction history, including the answers to the queries. To formalize this, for finite disjoint sets P,N⊆XP,N \subseteq\mathcal{X}, define the signed version space

VL(P,N)={L∈L:P⊆L, L∩N=∅}.\mathcal{V}_{\mathcal{L}}(P,N)=\{L\in\mathcal{L}:P\subseteq L,\ L\cap N=\varnothing\}.

At round nn, let Pn=supp⁡(σˉn)∪{yt:t≤n, at=1}P_n=\operatorname{supp}(\bar{\sigma}_n)\cup\{y_t:t\le n,\ a_t=1\} and Nn={yt:t≤n, at=0}N_n=\{y_t:t\le n,\ a_t=0\}. Then VL(Pn,Nn)\mathcal{V}_{\mathcal{L}}(P_n,N_n) is exactly the collection of languages in L\mathcal{L} that are consistent with all observed examples and all membership-query answers up to round nn.

Definition 4.3. A collection L\mathcal{L} is certifiably generatable with query feedback if there exist a query-feedback generator G\mathcal{G} and certificate c:⋃n∈N0(Xn×{0,1}n)→{0,1}c : \bigcup_{n\in\mathbb{N}_0}(X^n \times\{0,1\}^n) \to\{0,1\} satisfying:

(i) On every realizable finite interaction, if c(σˉn,αˉn)=1c(\bar{\sigma}_n,\bar{\alpha}_n) = 1, then G(σˉn,αˉn)⊆⋂L∈VL(Pn,Nn)L\mathcal{G}(\bar{\sigma}_n,\bar{\alpha}_n) \subseteq\bigcap_{L\in\mathcal{V}_{\mathcal{L}}(P_n,N_n)} L.

(ii) For every K∈LK \in\mathcal{L} and every enumeration σˉ\bar{\sigma} of KK, the induced interaction satisfies c(σˉn∗,αˉn∗)=1c(\bar{\sigma}_{n^*},\bar{\alpha}_{n^*}) = 1 for some n∗∈N0n^* \in\mathbb{N}_0.

Query-feedback generation was characterized by Hanneke et al. [12] in terms of the existence of a countable inner-cover, defined below. Interestingly, stable query-feedback generation admits the same characterization; the reader is referred to Appendix § 9 for a proof of Theorem 4.5.

Definition 4.4. A countable inner-cover of L\mathcal{L} is a countable family C={C1,C2,…}⊆BX\mathcal{C} = \{C_1, C_2, \ldots\} \subseteq\mathcal{B}_X such that every K∈LK \in\mathcal{L} contains some CiC_i. The sets CiC_i need not belong to L\mathcal{L}.

Theorem 4.5. For a collection L\mathcal{L}, the following are equivalent:

(i) L\mathcal{L} is stably generatable with query feedback.

(ii) L\mathcal{L} is generatable in the limit with query-feedback generator (with set-valued output).

(iii) L\mathcal{L} has a countable inner-cover.

We next characterize certifiable generation with query feedback in terms of finite positive and negative witnesses; the proof is again provided in Appendix § 9.

Theorem 4.6. A collection L\mathcal{L} is certifiably generatable with query feedback if and only if, for every K∈LK \in\mathcal{L}, there exist finite sets PK⊆KP_K \subseteq K and NK⊆X∖KN_K \subseteq X \setminus K such that ∣⋂L∈VL(PK,NK)L∣=∞\left|\bigcap_{L\in\mathcal{V}_{\mathcal{L}}(P_K,N_K)} L\right| = \infty.

Figure 1 summarizes the relationships between the notions studied in this paper. In particular, it shows that certifiable generation with query feedback is fundamentally different from both stable and ordinary query-feedback generation. We show that there exists a collection that is stably generatable in the limit even without feedback (and identifiable in the limit), but not certifiably generatable with query feedback. Thus, although membership queries allow a learner to observe negative examples, they do not suffice to certify every stably generatable collection. See Appendix § 9 for proof details.

Theorem 4.7. In Figure 1, there is a directed path from AA to BB if and only if every language family having a generator/learner of type AA also has a generator/learner of type BB.

Stable and Certifiable Language Generation with a Teacher

Stability and certifiability conditions require a generator to eventually stabilize, regardless of the input enumeration chosen for the target language. It is natural to ask whether, for any language LL in a stably or certifiably generatable family L\mathcal{L}, there is a finite set T⊆LT \subseteq L such that, as soon as TT appears in the input enumeration, a generator can stabilize. We call such TT a teaching set for LL (with respect to L\mathcal{L}). One can then measure the complexity of training a generator for L\mathcal{L} by the supremal size of a smallest teaching set for LL, where the supremum—called teaching dimension—is taken over all languages L∈LL \in\mathcal{L}. This approach parallels machine teaching for language identification [8], except that the objective here is successful generation rather than exact identification of the target language.

We begin by defining notions of teaching set and teaching dimension for generation in the limit, stable generation in the limit, and finally certifiable generation in the limit. [23] already established that finite teaching sets always exist for generation in the limit, without stability and certifiability conditions. They introduced a parameter called positive separation width, which coincides with our notion of generation teaching dimension (GTD\mathrm{GTD}), when the latter is finite.

Definition 5.1. For a generator G\mathcal{G} and K∈LK \in\mathcal{L}, a finite set T⊆KT \subseteq K is a generation teaching set for KK if G(σ)⊆K\mathcal{G}(\sigma) \subseteq K for every σ∈K∗\sigma\in K^{*} containing TT. Let TG(K)\mathcal{T}_{\mathcal{G}}(K) be the collection of all such sets. Define

GTD(L,G)=sup⁡K∈Linf⁡T∈TG(K)∣T∣andGTD(L)=inf⁡GGTD(L,G).\mathrm{GTD}(\mathcal{L},\mathcal{G}) = \sup_{K \in\mathcal{L}} \inf_{T \in\mathcal{T}_{\mathcal{G}}(K)} |T| \qquad\text{and} \qquad\mathrm{GTD}(\mathcal{L}) = \inf_{\mathcal{G}} \mathrm{GTD}(\mathcal{L},\mathcal{G}).

Here we assume that the infimum taken over the empty set is ∞\infty.

Note that we require the generator to generate successfully on every input that contains the teaching set, rather than only on the teaching set itself. This is analogous in spirit to the collusion-freeness requirements used in machine teaching which prevent the teacher and learner from using coding tricks [10, 6]. Without this requirement, a teacher could, for example, encode a representation of the target language in the teaching set, which the learner (or generator) would be able to decode. Successful learning from any enumeration containing the teaching set prevents such coding tricks.

[23] showed that every collection that is generatable in limit admits a generator with finite generation teaching sets; for countable collections, the size of these sets can be bounded by 1.

Theorem 5.2. ([23]). A language collection L\mathcal{L} is generatable in the limit if and only if there is a generator G~\widetilde{\mathcal{G}} such that every K∈LK \in\mathcal{L} has a finite generation teaching set with respect to G~\widetilde{\mathcal{G}}. Moreover, for every countable collection L\mathcal{L}, we have GTD(L)≤1\mathrm{GTD}(\mathcal{L}) \leq1.

We next adapt teaching to stable generation. In addition to guaranteeing correctness after the teaching set has appeared, we require the generator’s output to remain unchanged under every subsequent target-consistent continuation, yielding the notion of Stable Generation Teaching Dimension.

Definition 5.3. For a generator G\mathcal{G} and K∈LK \in\mathcal{L}, a finite set T⊆KT \subseteq K is a stable generation teaching set if, for every σ∈K∗\sigma\in K^{*} containing TT and every σ′∈(K∖supp⁡(σ))∗\sigma' \in(K \setminus\operatorname{supp}(\sigma))^{*}, we have G(σ)=G(σ⋅σ′)⊆K\mathcal{G}(\sigma) = \mathcal{G}(\sigma\mathbin{\cdot} \sigma') \subseteq K. Let TGst(K)\mathcal{T}_{\mathcal{G}}^{\mathrm{st}}(K) be the collection of these sets. Define

SGTD(L,G)=sup⁡K∈Linf⁡T∈TGst(K)∣T∣andSGTD(L)=inf⁡GSGTD(L,G).\mathrm{SGTD}(\mathcal{L},\mathcal{G}) = \sup_{K \in\mathcal{L}} \inf_{T \in\mathcal{T}_{\mathcal{G}}^{\mathrm{st}}(K)} |T| \qquad\text{and} \qquad\mathrm{SGTD}(\mathcal{L}) = \inf_{\mathcal{G}} \mathrm{SGTD}(\mathcal{L},\mathcal{G}).

Here we assume that the infimum taken over the empty set is ∞\infty.

Finally, we define a notion of Certifiable Generation Teaching Dimension. Here, a teaching set must provide enough information to certify an infinite set of outputs that is valid for every language consistent with the teaching set.

Definition 5.4. For K∈LK \in\mathcal{L}, a finite set T⊆KT \subseteq K is a certifiable generation teaching set if

∣⋂L∈L:T⊆LL∣=∞.\left|\bigcap_{L\in\mathcal{L}:T\subseteq L} L\right| = \infty.

Define

CGTD⁡(L)=sup⁡K∈Linf⁡{∣T∣:T⊆K, ∣⋂L∈L:T⊆LL∣=∞}.\operatorname{CGTD}(\mathcal{L}) = \sup_{K\in\mathcal{L}} \inf\left\{|T| : T\subseteq K,\ \left|\bigcap_{L\in\mathcal{L}:T\subseteq L} L\right| = \infty\right\}.

Relationships and Basic Properties

It is easy to see that GTD⁡(L)≤SGTD⁡(L)≤CGTD⁡(L)\operatorname{GTD}(\mathcal{L}) \le\operatorname{SGTD}(\mathcal{L}) \le\operatorname{CGTD}(\mathcal{L}) for every language collection L\mathcal{L}. This subsection addresses the question by how much these parameters can differ. Since teaching sets for each of the studied notions of generation bear some conceptual similarity with the non-clashing finite witness sets from our characterization of stable generatability (Theorem 3.4), we will additionally compare our three teaching dimension parameters to the size of the finite witnesses therein:

Definition 5.5. Let A(L)\mathcal{A}(\mathcal{L}) be the set of assignments T=(TL)L∈L\mathbf{T}=(T_L)_{L\in\mathcal{L}} of finite sets TL⊆LT_L\subseteq L satisfying (1) and (2). Define the Stable Non-Clashing Positive Witness Size by

SNC⁡+(L):=inf⁡T∈A(L)sup⁡L∈L∣TL∣.\operatorname{SNC}^{+}(\mathcal{L}) := \inf_{\mathbf{T}\in\mathcal{A}(\mathcal{L})}\sup_{L\in\mathcal{L}} |T_L|.

In the identification setting, [27] noted that non-clashing assignments are always tell-tale assignments, and thus that the smallest uniform bound on the tell-tale size never exceeds NCTD⁡+\operatorname{NCTD}^{+}. Interestingly, in a setting without computability requirements, tell-tales can be construed as teaching sets for identification in the same sense as stable generation teaching sets are teaching sets for stable generation. (If the learner has seen the tell-tale for a consistent language LL, it is safe to output LL: If LL is incorrect, the target cannot be a proper subset of LL, as it contains the tell-tale for LL. Hence, some string outside LL will be enumerated at some point, at which the learner will be allowed to change its mind again.) This motivates the following definition of Teaching Dimension for Identification.

Definition 5.6. ITD⁡(L):=inf⁡Tsup⁡L∈L∣TL∣\operatorname{ITD}(\mathcal{L}) := \inf_{\mathbf{T}}\sup_{L\in\mathcal{L}} |T_L|, where T\mathbf{T} ranges over all tell-tale assignments for L\mathcal{L}.

Thus, according to [27], ITD never exceeds NCTD⁡+\operatorname{NCTD}^{+} (but it may be smaller). Theorem 5.7 establishes an analogous relationship between SGTD and SNC⁡+\operatorname{SNC}^{+}.

Theorem 5.7. GTD⁡(L)≤SGTD⁡(L)≤SNC⁡+(L)≤CGTD⁡(L)\operatorname{GTD}(\mathcal{L}) \le\operatorname{SGTD}(\mathcal{L}) \le\operatorname{SNC}^{+}(\mathcal{L}) \le\operatorname{CGTD}(\mathcal{L}) for every collection L\mathcal{L}. Moreover, there are countable collections L1,L2,L3\mathcal{L}_1,\mathcal{L}_2,\mathcal{L}_3 such that GTD⁡(L1)≤1\operatorname{GTD}(\mathcal{L}_1) \le1 and SGTD⁡(L1)=∞\operatorname{SGTD}(\mathcal{L}_1)=\infty, SGTD⁡(L2)≤1\operatorname{SGTD}(\mathcal{L}_2)\le1 and SNC⁡+(L2)=∞\operatorname{SNC}^{+}(\mathcal{L}_2)=\infty, as well as SNC⁡+(L3)≤1\operatorname{SNC}^{+}(\mathcal{L}_3)\le1 and CGTD⁡(L3)=∞\operatorname{CGTD}(\mathcal{L}_3)=\infty.

Proof. (Partial sketch.) Proving the chain of inequalities is fairly straightforward. The first separation is obtained with L1={N∪{N∖{i}:i∈N}}\mathcal{L}_1=\{\mathbb{N}\cup\{\mathbb{N}\setminus\{i\}:i\in\mathbb{N}\}\}. The construction of the classes L2\mathcal{L}_2 and L3\mathcal{L}_3 is much more intricate; the reader is referred to Appendix § 10. □\square

Knowing that GTD⁡≤1\operatorname{GTD}\le1 for countable collections, it is natural to ask whether the same holds for SGTD, SNC⁡+\operatorname{SNC}^{+}, and CGTD. The following theorem shows that these parameters can take any positive integer value even for countable classes.

Theorem 5.8. For every integer n≥1n\ge1, there exists a countable collection Ln\mathcal{L}_n of infinite languages over a countable domain such that SGTD⁡(Ln)=SNC⁡+(Ln)=CGTD⁡(Ln)=n\operatorname{SGTD}(\mathcal{L}_n)=\operatorname{SNC}^{+}(\mathcal{L}_n)=\operatorname{CGTD}(\mathcal{L}_n)=n.

Proof. (Sketch.) The claim can be verified by defining disjoint countably infinite sets A={a1,a2,…}A = \{a_1, a_2, \ldots\} and B={b1,b2,…}B = \{b_1, b_2, \ldots\}, setting X=A⊔B\mathcal{X} = A \sqcup B, and Ln={X}∪{A∪F:F⊆B,∣F∣≤n−1}∪{B∪F:F⊆A,∣F∣≤n−1}\mathcal{L}_n = \{\mathcal{X}\} \cup\{A \cup F : F \subseteq B, \lvert F \rvert\le n - 1\} \cup\{B \cup F : F \subseteq A, \lvert F \rvert\le n - 1\}. See Appendix C for details.

For finite collections, however, we show in Appendix C that all four teaching-related parameters for the generation setting are at most one. By Theorem 5.7, it suffices to prove this bound for CGTD.

Theorem 5.9. For every finite collection L\mathcal{L}, the dimensions GTD⁡(L)\operatorname{GTD}(\mathcal{L}), SGTD⁡(L)\operatorname{SGTD}(\mathcal{L}), SNC⁡+(L)\operatorname{SNC}^{+}(\mathcal{L}), and CGTD⁡(L)\operatorname{CGTD}(\mathcal{L}) all equal 00 if ⋂L∈LL\bigcap_{L \in\mathcal{L}} L is infinite, and 11 otherwise.

GTD versus Complexity of Identification and Uniform Generation

We conclude this section by comparing the complexity of teaching for generation with the complexity of uniform generation and the complexity of teaching for identification. As discussed before Theorem 5.7, we use ITD as a notion of teaching dimension for identification; recall that ITD ≤\le NCTD+^{+}. We provide very simple arguments showing that, even for finite collections of regular languages, (i) uniform generation and (ii) identification can demand many examples, while certifiable generation requires at most one carefully chosen example for each target.

Theorem 5.10. (i) There exists k∈Nk \in\mathbb{N} such that, for every ℓ,n∈N\ell, n \in\mathbb{N}, there exists a family F\mathcal{F} of infinite binary regular languages such that ∣F∣=2ℓ\lvert\mathcal{F}\rvert= 2^\ell, each L∈FL \in\mathcal{F} is accepted by a DFA with at most k⋅ℓ⋅nk \cdot\ell\cdot n states, and F\mathcal{F} is not 2∣F∣2^{\lvert\mathcal{F}\rvert}-uniformly generatable, while CGTD⁡(F)=1\operatorname{CGTD}(\mathcal{F}) = 1.

(ii) For every ℓ∈N\ell\in\mathbb{N}, there exists a finite family F\mathcal{F} of infinite binary regular languages such that ∣F∣=2ℓ\lvert\mathcal{F}\rvert= 2^\ell, every L∈FL \in\mathcal{F} is recognizable by a DFA with at most ℓ+1\ell+ 1 states, and NCTD⁡+(F)≥ITD⁡(F)≥∣F∣−1\operatorname{NCTD}^{+}(\mathcal{F}) \ge\operatorname{ITD}(\mathcal{F}) \ge\lvert\mathcal{F}\rvert- 1, while CGTD⁡(F)=0\operatorname{CGTD}(\mathcal{F}) = 0 and F\mathcal{F} is 00-uniformly generatable.

Proof. (Sketch.) The first statement can be derived from the proof of Theorem 4.1 by [1]. The second statement is witnessed by the class {Σ∗}∪{Σ∗∖{w}:∣w∣<ℓ}\{\Sigma^*\} \cup\{\Sigma^* \setminus\{w\} : \lvert w\rvert< \ell\}. One can show that any tell-tale for Σ∗\Sigma^* in this class has size at least 2ℓ−12^\ell- 1. See Appendix C for details.

Conclusion

We introduced certifiable language generation, which requires a generator to eventually recognize that its output is valid. We studied it alongside the stability requirement of [17]. Our finite-witness characterizations of stable and certifiable generation resolve the open question of characterizing stable generation, and they place both notions in a strict hierarchy between uniform generation and generation in the limit. Natural families such as erasing pattern languages witness some of these separations. With queries, stability imposes no restriction beyond generation in the limit. Certifiability remains restrictive: some collections are identifiable in the limit yet cannot be certifiably generated even with queries. We initiated the study of teaching sets for generation, and showed that stronger success criteria can require arbitrarily larger teaching sets, in contrast to the bound of one for generation in the limit. We also showed that, already for finite families of regular languages, teaching for certifiable generation can be far cheaper than uniform generation or identification. Interesting future directions include resource-bounded versions of our notions in the query feedback framework, and certification guarantees under noisy or adversarially corrupted data.

AI Disclosure. Generative AI tools were used to assist with working out details of some of our technical proofs, with drafting small parts of the writing, as well as with checking earlier drafts for technical errors and typos. The authors assume full responsibility for the entire content and presentation of the paper.

References

Proofs Omitted from Section 3

Theorem 3.5. A collection L\mathcal{L} is certifiably generatable if and only if, for every K∈LK \in\mathcal{L}, there is a finite set TK⊆KT_K \subseteq K such that

∣⋂L∈L:TK⊆LL∣=∞.(5)\left\lvert\bigcap_{L \in\mathcal{L}:T_K \subseteq L} L \right\rvert= \infty. \tag*{(5)}

Proof. For the only-if direction, fix K∈LK \in\mathcal{L} and any enumeration σˉ\bar{\sigma} of KK. Let mm be a round at which certification occurs, and set TK=supp⁡(σˉm)T_K = \operatorname{supp}(\bar{\sigma}_m). Soundness gives

G(σˉm)⊆⋂L∈L:TK⊆LL.\mathcal{G}(\bar{\sigma}_m) \subseteq\bigcap_{L \in\mathcal{L}:T_K \subseteq L} L.

The left-hand side is infinite, so (4) holds.

For the if direction, suppose that every K∈LK \in\mathcal{L} contains a finite set TKT_K satisfying (4). For a finite sequence σ∈X∗\sigma\in\mathcal{X}^*, consider

I(σ):=⋂L∈L:supp⁡(σ)⊆LL.I(\sigma) := \bigcap_{L \in\mathcal{L}:\operatorname{supp}(\sigma) \subseteq L} L.

If at least one language is consistent with σ\sigma and I(σ)I(\sigma) is infinite, define c(σ)=1c(\sigma) = 1 and G(σ)=I(σ)\mathcal{G}(\sigma) = I(\sigma). Otherwise, define c(σ)=0c(\sigma) = 0 and G(σ)=X\mathcal{G}(\sigma) = \mathcal{X}. This procedure is sound.

Fix K∈LK \in\mathcal{L} and an enumeration σˉ\bar{\sigma} of KK. Since TKT_K is finite, there is a round mm such that TK⊆supp⁡(σˉn)T_K \subseteq\operatorname{supp}(\bar{\sigma}_n) for every n≥mn \ge m. For every such nn, any language containing supp⁡(σˉn)\operatorname{supp}(\bar{\sigma}_n) also contains TKT_K. Therefore,

I(σˉn)⊇⋂L∈L:TK⊆LL.I(\bar{\sigma}_n) \supseteq\bigcap_{L \in\mathcal{L}:T_K \subseteq L} L.

The right-hand side is infinite by assumption. Hence c(σˉn)=1c(\bar{\sigma}_n) = 1 for every n≥mn \ge m, which proves eventual certification.

Theorem 3.6. For every collection L\mathcal{L} of infinite languages, the following implications hold.

L is uniformly generatable⟹L is certifiably generatable.L is certifiably generatable⟹L is stably generatable.L is stably generatable⟹L is generatable in the limit.\begin{aligned} \mathcal{L}\text{ is uniformly generatable} &\Longrightarrow\mathcal{L}\text{ is certifiably generatable}.\\ \mathcal{L}\text{ is certifiably generatable} &\Longrightarrow\mathcal{L}\text{ is stably generatable}.\\ \mathcal{L}\text{ is stably generatable} &\Longrightarrow\mathcal{L}\text{ is generatable in the limit}. \end{aligned}

Every implication is strict.

Proof. Suppose first that L\mathcal{L} is ii-uniformly generatable by G\mathcal{G}. Set c(σ)=1c(\sigma) = 1 whenever ∣σ∣≥i\lvert\sigma\rvert\ge i, and set c(σ)=0c(\sigma) = 0 otherwise. If σ∈X∗\sigma\in\mathcal{X}^* has length at least ii, uniform generation guarantees G(σ)⊆L\mathcal{G}(\sigma) \subseteq L for every L∈LL \in\mathcal{L} consistent with σ\sigma. Thus this certification rule is sound. Every target is infinite, so its enumeration eventually reaches the threshold. Therefore L\mathcal{L} is certifiably generatable.

Next, suppose that L\mathcal{L} is certifiably generatable. Modify the generator so that, after its first certification, it retains the certified output. On an enumeration of a target KK, certification occurs after a finite number of rounds, and soundness implies that the retained infinite set is contained in KK. The modified generator is therefore stable. Finally, a stable generator is eventually correct, so stable generation implies generation in the limit.

A collection that is certifiably generatable but not uniformly generatable can be defined as follows: For every i∈Ni \in\mathbb{N}, define Ai:={2i(2k−1)−1:k∈N}A_i := \{2^i(2k-1)-1 : k \in\mathbb{N}\}. These are infinite sets of odd numbers. They are pairwise disjoint because, for every a∈Aia \in A_i, the largest power of two dividing a+1a+1 is exactly 2i2^i. Now consider

L1:={Li:i∈N},Li:={2,4,…,2i}∪Ai.\mathcal{L}_1 := \{L_i : i \in\mathbb{N}\}, \qquad L_i := \{2,4,\ldots,2i\} \cup A_i.

We first show that L1\mathcal{L}_1 is certifiably generatable. Fix a target LiL_i and choose any a∈Aia \in A_i. If a∈Lja \in L_j, then, since aa is odd, it must belong to AjA_j. Disjointness of the sets AjA_j implies j=ij=i. Thus the only language in L1\mathcal{L}_1 containing aa is LiL_i, and ⋂L∈L:{a}⊆LL=Li\bigcap_{L\in\mathcal{L}:\{a\}\subseteq L}L=L_i. This intersection is infinite. Therefore {a}\{a\} is a certifying witness for LiL_i, and Theorem 3.5 gives certifiable generation. On the other hand, notice that for every m∈Nm\in\mathbb{N} we have

∣⋂j≥mLj∣=∣{2,4,…,2m}∣=m\left|\bigcap_{j\geq m}L_j\right|=\left|\{2,4,\ldots,2m\}\right|=m

This implies that L1\mathcal{L}_1 is not mm-uniformly generatable. Thus, L1\mathcal{L}_1 is not uniformly generatable.

A collection that is stably generatable but not certifiably generatable is given by L2:={Li:=N∖{i}:i∈N}\mathcal{L}_2:=\{L_i:=\mathbb{N}\setminus\{i\}:i\in\mathbb{N}\} over X=NX=\mathbb{N}. Define G(σ):=Lj(σ)G(\sigma):=L_{j(\sigma)}, where j(σ):=min⁡{j:j∉supp⁡(σ)}j(\sigma):=\min\{j:j\notin\operatorname{supp}(\sigma)\}. For a target LiL_i, all of {1,…,i−1}\{1,\ldots,i-1\} eventually appears, whereas ii never appears. From that point onward, j(σn)=ij(\sigma_n)=i, so the generator always outputs LiL_i. Thus L2\mathcal{L}_2 is stably generatable. (Since the output eventually equals the target language itself, the same map also identifies L2\mathcal{L}_2 in the limit.) On the other hand, for every finite T⊆NT\subseteq\mathbb{N}, we have ⋂L∈L2:T⊆LL=⋂i∉T(N∖{i})=T\bigcap_{L\in\mathcal{L}_2:T\subseteq L}L=\bigcap_{i\notin T}(\mathbb{N}\setminus\{i\})=T. This intersection is finite, so Theorem 3.5 implies that L2\mathcal{L}_2 is not certifiably generatable.

Finally, Theorem 8.7 of Kalavasis, Mehrotra, and Velegkas [16] showed that the collection L3={X}∪{X∖{w}:w∈X}\mathcal{L}_3=\{X\}\cup\{X\setminus\{w\}:w\in X\} is not stably generatable, but it is generatable in the limit due to countability [14].

Theorem 3.7. The collection eTFP⁡Σ\operatorname{eTFP}_{\Sigma} is certifiably generatable and 2-uniformly generatable, but is not 1-uniformly generatable, and, when ∣Σ∣=2|\Sigma|=2, not identifiable in the limit.

Proof. Reidenbach [29] proved that, when ∣Σ∣=2|\Sigma|=2, the class eTFP⁡Σ\operatorname{eTFP}_{\Sigma} is not (even non-computably) identifiable in the limit. To see that eTFP⁡Σ\operatorname{eTFP}_{\Sigma} is not 1-uniformly generatable, note that the first example in an enumeration of a target language may be the empty word ε\varepsilon, which belongs to every terminal-free erasing pattern language, while ⋂r≥1LE(xr)={ε}\bigcap_{r\geq1}L_E(x^r)=\{\varepsilon\}. Thus no infinite output can be valid for every language consistent with this first example.

On the other hand, consider the first two examples in any enumeration of any target language L∈eTFP⁡ΣL\in\operatorname{eTFP}_{\Sigma}. One of these two examples must be a nonempty word w=a1⋯am∈Lw=a_1\cdots a_m\in L for some m≥1m\geq1 and ai∈Σa_i\in\Sigma. We claim that W:={a1k⋯amk:k≥1}W:=\{a_1^k\cdots a_m^k:k\geq1\} is an infinite subset of LL. Indeed, take a substitution generating ww and replace each letter cc in its variable images by ckc^k. Since the pattern is terminal-free, this produces a1k⋯amka_1^k\cdots a_m^k. These words have distinct lengths, so WW is infinite. The generator can therefore output WW and certify its validity. Hence the collection is 2-uniformly generatable. Moreover, any nonempty word in a target language forms a singleton certifiable teaching set, implying certifiable generatability. \qed

Theorem 3.8. The collection eP⁡Σ\operatorname{eP}_{\Sigma} is stably generatable, but is not uniformly generatable, and, when ∣Σ∣∈{2,3,4}|\Sigma|\in\{2,3,4\}, not identifiable in the limit.

Proof. For ∣Σ∣∈{2,3,4}|\Sigma|\in\{2,3,4\}, Reidenbach [30] proved that eP⁡Σ\operatorname{eP}_{\Sigma} is not (even non-computably) identifiable in the limit. (Reidenbach’s proof goes through even when excluding patterns that have no variables.) We first prove stable generatability using two-word witnesses, and then prove the impossibility of uniform generation using finite intersections of pattern languages.

Stable generation. Fix a shortlex ordering ⪯\preceq on Σ∗\Sigma^*. For every L∈eP⁡ΣL\in\operatorname{eP}_{\Sigma}, let sLs_L and wLw_L denote, respectively, the first and second elements of LL according to ⪯\preceq, and define TL:={sL,wL}T_L:=\{s_L,w_L\}.

We verify the two conditions in Theorem 3.4, starting with the second condition. For L,L′∈eP⁡ΣL,L'\in\operatorname{eP}_{\Sigma}, suppose TL∪TL′⊆L∩L′T_L\cup T_{L'}\subseteq L\cap L'. Since sL∈L′s_L\in L' and sL′∈Ls_{L'}\in L, by minimality of the first elements we have sL′⪯sLs_{L'}\preceq s_L, and sL⪯sL′s_L\preceq s_{L'}, and hence sL=sL′=:ss_L=s_{L'}=:s. Similarly, wL∈L′w_L\in L' and wL′∈Lw_{L'}\in L. Since these are the smallest elements strictly larger than ss in the respective languages, wL=wL′w_L = w_{L'}. Thus TL=TL′T_L = T_{L'}.

Consider any s,w∈Σ∗s,w \in\Sigma^*, and any L=LE(α)∈ePΣL = L_E(\alpha) \in\mathrm{eP}_\Sigma such that sL=ss_L = s and wL=ww_L = w, i.e., TL={s,w}T_L = \{s,w\}. The word obtained by erasing every variable from α\alpha is the unique shortest word of LL; hence it is ss.

For every variable x∈var⁡(α)x \in\operatorname{var}(\alpha), let ∣α∣x|\alpha|_x denote the number of occurrences of xx and let r:=min⁡x∈var⁡(α)∣α∣xr := \min_{x \in\operatorname{var}(\alpha)} |\alpha|_x. Every word in L∖{s}L \setminus\{s\} has length at least ∣s∣+r|s| + r, and this bound is attained by mapping a variable xx with ∣α∣x=r|\alpha|_x = r to a single terminal symbol and erasing every other variable. Therefore, ∣w∣=∣s∣+r|w| = |s| + r.

Moreover, every substitution producing a word of this length maps exactly one variable xx with ∣α∣x=r|\alpha|_x = r to a single symbol c∈Σc \in\Sigma and maps all other variables to the empty word. Thus ww is obtained from ss by inserting exactly rr copies of one symbol cc.

Write

s=cq0a1cq1a2⋯amcqm,ai≠c.s = c^{q_0}a_1c^{q_1}a_2 \cdots a_mc^{q_m}, \qquad a_i \ne c.

Then, for uniquely determined d0,…,dm≥0d_0,\ldots,d_m \ge0 with ∑idi=r\sum_i d_i = r,

w=cq0+d0a1cq1+d1a2⋯amcqm+dm.w = c^{q_0+d_0}a_1c^{q_1+d_1}a_2 \cdots a_mc^{q_m+d_m}.

For every k≥0k \ge0, define

bk(s,w):=cq0+kd0a1cq1+kd1a2⋯amcqm+kdm.b_k(s,w) := c^{q_0+kd_0}a_1c^{q_1+kd_1}a_2 \cdots a_mc^{q_m+kd_m}.

Mapping xx to ckc^k and every other variable to the empty word shows that for every k≥0k \ge0, bk(sL,wL)∈Lb_k(s_L,w_L) \in L. Hence

BsL,wL:={bk(sL,wL):k≥0}B_{s_L,w_L} := \{b_k(s_L,w_L) : k \ge0\}

is an infinite subset of LL.

Since LL is chosen arbitrarily, this implies ∣⋂L:TL={s,w}L∣=∞\left|\bigcap_{L:T_L=\{s,w\}} L\right| = \infty. This proves the first condition.

Impossibility of uniform generation. Choose distinct symbols a,b∈Σa,b \in\Sigma, and consider P:=LE(xaxb)P := L_E(xaxb), and Q:=LE(yaby)Q := L_E(yaby). We first prove that

P∩Q=R:={bjabj+1:j≥0}.P \cap Q = R := \{b^jab^{j+1} : j \ge0\}.

A word in the intersection has representations uaub=vabvuaub = vabv. Comparing lengths gives ∣u∣=∣v∣|u| = |v|, and comparing the initial blocks of this length gives u=vu = v. Cancelling the common prefix uaua then gives ub=buub = bu, which forces uu to consist only of copies of bb. Conversely, substituting u=v=bju = v = b^j implies that bjabj+1b^jab^{j+1} is in both languages and establishes the displayed equality.

Fix any m≥1m \ge1, and define

Rm:={bjabj+1:0≤j<m},αm:=z11⋯zm−1m−1az01z12⋯zm−1m,R_m := \{b^jab^{j+1} : 0 \le j < m\}, \qquad\alpha_m := z_1^1 \cdots z_{m-1}^{m-1} a z_0^1 z_1^2 \cdots z_{m-1}^m,

where z0,…,zm−1z_0,\ldots,z_{m-1} are distinct variables. We claim that R∩LE(αm)=RmR \cap L_E(\alpha_m) = R_m. Observe that proving this claim shows that ePΣ\mathrm{eP}_\Sigma is not mm-uniformly generatable. Since mm was chosen arbitrarily this proves that ePΣ\mathrm{eP}_\Sigma is not uniformly generatable.

For each 0≤j<m0 \le j < m, map zjz_j to bb and erase every other variable. This produces bjabj+1b^jab^{j+1}, so Rm⊆R∩LE(αm)R_m \subseteq R \cap L_E(\alpha_m).

We now prove R∩LE(αm)⊆RmR \cap L_E(\alpha_m) \subseteq R_m. Consider a substitution of αm\alpha_m producing a word in RR. The word has exactly one occurrence of aa, already defined by the terminal in αm\alpha_m, and all its other symbols are bb. Every variable must therefore be substituted by bℓjb^{\ell_j} for some ℓj≥0\ell_j \ge0. The numbers of bb's before and after the terminal aa are, respectively, ∑j=0m−1ℓj\sum_{j=0}^{m-1}\ell_j and ∑j=0m−1(j+1)ℓj\sum_{j=0}^{m-1}(j+1)\ell_j. For a word in RR, their difference must be one. Thus ∑j=0m−1jℓj=1\sum_{j=0}^{m-1}j\ell_j = 1, i.e., exactly one variable zjz_j for j<mj < m is mapped to bb, and all other variables are erased. This will imply that the word is in RmR_m, proving the claim. □\square

Proofs Omitted from Section 4

Theorem 4.5. For a collection L\mathcal{L}, the following are equivalent:

(i) L\mathcal{L} is stably generatable with query feedback.

(ii) L\mathcal{L} is generatable in the limit with query-feedback generator (with set-valued output).

(iii) L\mathcal{L} has a countable inner-cover.

Proof. The equivalence of (ii) and (iii) is Theorem 3.4 of Hanneke et al. [12]. The following proof makes the stable-support conclusion explicit. Furthermore, (i) ⇒\Rightarrow (ii) follows directly from the definition: a stable output that is contained in the target is, in particular, eventually correct. It remains to prove (iii) ⇒\Rightarrow (i).

Suppose that L\mathcal{L} has a countable inner-cover {C1,C2,…}\{C_1,C_2,\ldots\}. A finite nonempty cover can be listed in this form by repeating its elements. Fix an enumeration u1,u2,…u_1,u_2,\ldots of X\mathcal{X}, and query unu_n at round nn. Let

Nn:={ut:t≤n, at=0}N_n := \{u_t : t \le n,\, a_t = 0\}

be the set of negatively answered query points. Define

in:=min⁡{i≥1:Ci∩Nn=∅},G(σˉn,αˉn):=Cin.i_n := \min\{i \ge1 : C_i \cap N_n = \varnothing\}, \qquad G(\bar{\sigma}_n,\bar{\alpha}_n) := C_{i_n}.

This minimum exists on every realizable interaction. Indeed, the target contains some cover element CiC_i, and no point of CiC_i can receive a negative answer. Thus at least one index is always eligible. On an unrealizable interaction for which there is no eligible index, define the output arbitrarily as X\mathcal{X}.

Fix a target K∈LK \in\mathcal{L}, and let

i∗:=min⁡{i≥1:Ci⊆K}.i^* := \min\{i \ge1 : C_i \subseteq K\}.

The index i∗i^* is never excluded, so in≤i∗i_n \le i^* at every round. For each i<i∗i < i^*, the minimality of i∗i^* implies Ci⊈KC_i \not\subseteq K. Choose a point zi∈Ci∖Kz_i \in C_i \setminus K. The fixed query sequence eventually queries ziz_i and receives a negative answer. From that round onward, Ci∩Nn≠∅C_i \cap N_n \ne\varnothing, so index ii is permanently excluded.

There are only finitely many indices below i∗i^*. Hence there is a finite round n0n_0 by which all of them have been excluded. Since i∗i^* remains eligible, for every n≥n0n \ge n_0 we have

in=i∗,G(σˉn,αˉn)=Ci∗⊆K.i_n = i^*, \qquad G(\bar{\sigma}_n,\bar{\alpha}_n) = C_{i^*} \subseteq K.

The output is therefore constant and valid from round n0n_0 onward. This proves stable generation. □\square

Theorem 4.6. A collection L\mathcal{L} is certifiably generatable with query feedback if and only if, for every K∈LK \in\mathcal{L}, there exist finite sets PK⊆KP_K \subseteq K and NK⊆X∖KN_K \subseteq\mathcal{X} \setminus K such that ∣⋂L∈VL(PK,NK)L∣=∞\left|\bigcap_{L \in\mathcal{V}_{\mathcal{L}}(P_K,N_K)} L\right| = \infty.

Proof. For necessity, fix K∈LK \in\mathcal{L} and an enumeration of KK. Take a finite transcript at which certification occurs. Let PKP_K consist of the observed positive examples and positive query points, and let NKN_K consist of the negative query points. Every language in VL(PK,NK)\mathcal{V}_{\mathcal{L}}(P_K,N_K) is consistent with this transcript. Soundness therefore places the certified infinite output in their common intersection.

For sufficiency, fix an enumeration u1,u2,…u_1,u_2,\ldots of X\mathcal{X} and query utu_t at round tt. Let Pt,NtP_t,N_t record all positive and negative information available at that time. Define

It:=⋂L∈VL(Pt,Nt)LI_t := \bigcap_{L \in\mathcal{V}_{\mathcal{L}}(P_t,N_t)} L

Let the output of generator be arbitrary whenever ItI_t is finite, and ItI_t whenever it is infinite. Furthermore, certify whenever, ItI_t is infinite. On every realizable transcript, the target belongs to the version space, so certification is sound.

Fix a target KK and its finite witnesses PK,NKP_K, N_K. Since the queries exhaust X\mathcal{X} in the fixed order, every element of PK∪NKP_K \cup N_K is eventually queried at a time tt. At that time,

VL(Pt,Nt)⊆VL(PK,NK),\mathcal{V}_{\mathcal{L}}(P_t,N_t) \subseteq\mathcal{V}_{\mathcal{L}}(P_K,N_K),

and hence

It⊇⋂L∈VL(PK,NK)L.I_t \supseteq\bigcap_{L\in\mathcal{V}_{\mathcal{L}}(P_K,N_K)} L.

The latter intersection is infinite, so certification occurs after finitely many rounds.

Theorem 4.7. In Figure 1, there is a directed path from AA to BB if and only if every language family having a generator/learner of type AA also has a generator/learner of type BB.

Proof. Theorem 3.6 establishes the three strict inclusions between uniform, certifiable, stable, and generation in the limit. Propositions B.1 and B.2 establish the strict inclusion of certifiable generation with query feedback in stable generation without feedback. The strictness of inclusion of generation in limit in generation in limit with query-feedback is proven in Theorem 3.10 of Hanneke et al. [12]. The equivalence of stable and ordinary generation with query feedback follows from Theorem 4.5.

We establish the remaining relations.

Certifiable generation versus certifiable generation with query feedback. By Theorem 3.6 the collection L:={Li:=N∖{i}:i∈N}\mathcal{L} := \{L_i := \mathbb{N} \setminus\{i\} : i \in\mathbb{N}\} is not certifiably generatable without feedback. However, for each target Li=N∖{i}L_i = \mathbb{N} \setminus\{i\}, let Ni={i}N_i = \{i\} and Pi=∅P_i = \varnothing. Then VL(Pi,Ni)=Li\mathcal{V}_{\mathcal{L}}(P_i,N_i) = L_i. Theorem 4.6 implies that the collection is certifiably generatable with query feedback. The reverse inclusion follows by ignoring queries.

Identification in the limit. Identification implies stable generation by outputting the language hypothesized by the identifier. The inclusion is strict by Theorem 3.8, which gives a stably generatable collection that is not identifiable in the limit. Furthermore, Theorem 3.7 gives a uniformly generatable collection that is not identifiable in the limit. Conversely, the collection in Proposition B.2 is also identifiable in the limit, but is not certifiably generatable even with query feedback.

Therefore, identification is incomparable with uniform generation, certifiable generation, and certifiable generation with query feedback. This proves all the claimed relations.

:::

Proposition B.1. If a collection L\mathcal{L} is certifiably generatable with query feedback, then it is stably generatable even without feedback.

Proof. For finite disjoint sets P,N⊆XP,N \subseteq\mathcal{X}, let I(P,N):=⋂L∈VL(P,N)LI(P,N) := \bigcap_{L\in\mathcal{V}_{\mathcal{L}}(P,N)} L. Define the family of finite pairs that can witness the characterization in Theorem 4.6 as

W:={(P,N):P,N⊆X are finite and disjoint, VL(P,N)≠∅, ∣I(P,N)∣=∞}.\mathcal{W} := \{(P,N) : P,N \subseteq\mathcal{X}\text{ are finite and disjoint},\ \mathcal{V}_{\mathcal{L}}(P,N) \ne\varnothing,\ |I(P,N)| = \infty\}.

Observe that since X\mathcal{X} is countable, W\mathcal{W} is also countable. Let (Pi,Ni)i≥1(P_i,N_i)_{i\ge1} be an enumeration of W\mathcal{W} and let Ci:=I(Pi,Ni)C_i := I(P_i,N_i). By definition, every CiC_i is infinite. Moreover, by the characterization of certifiable generation with query feedback, for every K∈LK \in\mathcal{L} there is an index ii such that Pi⊆KP_i \subseteq K and Ni∩K=∅N_i \cap K = \varnothing.

We now define the generator without feedback. For a finite sequence σˉ\bar{\sigma}, let S=supp⁡(σˉ)S=\operatorname{supp}(\bar{\sigma}) and define i(σˉ)=min⁡{i≥1:Pi⊆S, Ni∩S=∅}i(\bar{\sigma})=\min\{i\geq1:P_i\subseteq S,\ N_i\cap S=\varnothing\}, whenever the defined set is not empty. The generator is defined as

G(σˉ):={Ci(σˉ),if i(σˉ) is defined,X,otherwise.\mathcal{G}(\bar{\sigma}) := \begin{cases} C_{i(\bar{\sigma})}, & \text{if } i(\bar{\sigma}) \text{ is defined},\\ \mathcal{X}, & \text{otherwise}. \end{cases}

Fix a target language K∈LK\in\mathcal{L} and an enumeration σˉ\bar{\sigma} of KK. Let

i∗:=min⁡{i≥1:Pi⊆K, Ni∩K=∅}.i^{*}:=\min\{i\geq1:P_i\subseteq K,\ N_i\cap K=\varnothing\}.

Since Pi∗P_{i^{*}} is finite, every enumeration of KK eventually contains Pi∗P_{i^{*}}. Furthermore, no element of Ni∗N_{i^{*}} appears in the enumeration. Consequently, there will be some round such that Pi∗P_{i^{*}} is a subset of the instances appeared so far and Ni∗N_{i^{*}} has empty intersection with the input, meaning that the generator will consider this as an index in the set it is minimizing.

Now consider any i<i∗i<i^{*}. By the minimality of i∗i^{*}, either Pi⊈KP_i\not\subseteq K or Ni∩K≠∅N_i\cap K\neq\varnothing. In the first case, PiP_i is never contained in the observed examples, so ii is never considered by the generator. In the second case, choose xi∈Ni∩Kx_i\in N_i\cap K. Since σˉ\bar{\sigma} enumerates KK, there is a finite round at which xix_i appears. From that round onward, Ni∩supp⁡(σˉn)≠∅N_i\cap\operatorname{supp}(\bar{\sigma}_n)\neq\varnothing, so ii will never be considered.

There are only finitely many indices smaller than i∗i^{*}. Thus there is a round n∗n^{*} such that i(σˉn)=i∗i(\bar{\sigma}_n)=i^{*} for every n≥n∗n\geq n^{*}. Since K∈VL(Pi∗,Ni∗)K\in\mathcal{V}_{\mathcal{L}}(P_{i^{*}},N_{i^{*}}), we have

G(σˉn)=Ci∗=⋂L∈VL(Pi∗,Ni∗)L⊆Kfor every n≥n∗.\mathcal{G}(\bar{\sigma}_n)=C_{i^{*}}=\bigcap_{L\in\mathcal{V}_{\mathcal{L}}(P_{i^{*}},N_{i^{*}})}L\subseteq K\qquad\text{for every }n\geq n^{*}.

The output is therefore constant and valid from round n∗n^{*} onward, proving stable generation without feedback.

We now show that the above implication is strict, namely, there is a countable collection that is stably generatable but not certifiably generatable even with query feedback.

Proposition B.2. There exists a countable collection that is both stably generatable without feedback and identifiable in the limit but not certifiably generatable with query feedback.

Proof. Let A={a1,a2,…}A=\{a_1,a_2,\ldots\} and M={m1,m2,…}M=\{m_1,m_2,\ldots\} be disjoint countably infinite sets, and let X=A⊔M\mathcal{X}=A\sqcup M. Define

K⋆:=A,Kj:=(A∖{aj})∪{mj}(j≥1),L:={K⋆}∪{Kj:j≥1}.K_{\star}:=A,\qquad K_j:=(A\setminus\{a_j\})\cup\{m_j\}\quad(j\geq1),\qquad\mathcal{L}:=\{K_{\star}\}\cup\{K_j:j\geq1\}.

Note that every language in L\mathcal{L} is infinite.

We first show that L\mathcal{L} is stably generatable. For a finite sequence σ\sigma, define J(σ):={j≥1:mj∈supp⁡(σ)}J(\sigma):=\{j\geq1:m_j\in\operatorname{supp}(\sigma)\}, and let

G(σ):={K⋆,J(σ)=∅,Kmin⁡J(σ),J(σ)≠∅.\mathcal{G}(\sigma):= \begin{cases} K_{\star}, & J(\sigma)=\varnothing,\\ K_{\min J(\sigma)}, & J(\sigma)\neq\varnothing. \end{cases}

On every enumeration of K⋆K_{\star}, no element from MM will appear, and hence the generator outputs K⋆K_{\star} in every round. For any target KjK_j, the element mjm_j eventually appears in the enumeration. Since Kj∩M={mj}K_j\cap M=\{m_j\} from that round onward the generator outputs KjK_j and never changes its output. Thus L\mathcal{L} is stably generatable without feedback. Since the output of the generator eventually equals the target language itself, the same map also identifies L\mathcal{L} in the limit.

We next show that L\mathcal{L} is not certifiably generatable with query feedback. Consider the target K⋆=AK_{\star}=A and any finite sets P⊆AP\subseteq A and N⊆MN\subseteq M. By construction,

VL(P,N)={K⋆}∪{Kj:aj∉P, mj∉N}.(6)\mathcal{V}_{\mathcal{L}}(P,N)=\{K_{\star}\}\cup\{K_j:a_j\notin P,\ m_j\notin N\}. \tag*{(6)}

Since KjK_j excludes aja_j and K⋆K_\star excludes every element from MM, we obtain

⋂L∈V(P,N)L=P∪{aj:mj∈N}.\bigcap_{L\in\mathcal{V}(P,N)} L = P \cup\{a_j : m_j \in N\}.

The right-hand side is finite. Therefore no finite sets PP and NN can be a witness to the characterization of certifiable generation for K⋆K_\star. Hence, L\mathcal{L} is not certifiably generatable with query feedback.

Proofs Omitted from Section 5

Theorem 5.7. GTD⁡(L)≤SGTD⁡(L)≤SNC⁡+(L)≤CGTD⁡(L)\operatorname{GTD}(\mathcal{L}) \leq\operatorname{SGTD}(\mathcal{L}) \leq\operatorname{SNC}^{+}(\mathcal{L}) \leq\operatorname{CGTD}(\mathcal{L}) for every collection L\mathcal{L}. Moreover, there are countable collections L1,L2,L3\mathcal{L}_1,\mathcal{L}_2,\mathcal{L}_3 such that GTD⁡(L1)≤1\operatorname{GTD}(\mathcal{L}_1) \leq1 and SGTD⁡(L1)=∞\operatorname{SGTD}(\mathcal{L}_1) = \infty, SGTD⁡(L2)≤1\operatorname{SGTD}(\mathcal{L}_2) \leq1 and SNC⁡+(L2)=∞\operatorname{SNC}^{+}(\mathcal{L}_2) = \infty, as well as SNC⁡+(L3)≤1\operatorname{SNC}^{+}(\mathcal{L}_3) \leq1 and CGTD⁡(L3)=∞\operatorname{CGTD}(\mathcal{L}_3) = \infty.

Proof. We first prove the chain of inequalities. Every stable generation teaching set is a generation teaching set, giving the first inequality.

Next, consider any admissible assignment T=(TL)L∈L∈A(L)\mathbf{T}=(T_L)_{L\in\mathcal{L}}\in\mathcal{A}(\mathcal{L}). In the if direction of Theorem 3.4, we constructed a generator G\mathcal{G} that satisfies SGTD⁡(L,G)≤sup⁡L∈L∣TL∣\operatorname{SGTD}(\mathcal{L},\mathcal{G})\leq\sup_{L\in\mathcal{L}}|T_L|, which proves the second inequality.

To prove SNC⁡+(L)≤CGTD⁡(L)\operatorname{SNC}^{+}(\mathcal{L})\leq\operatorname{CGTD}(\mathcal{L}), it suffices to consider the case CGTD⁡(L)=m<∞\operatorname{CGTD}(\mathcal{L})=m<\infty. Fix an enumeration of all finite sets of size at most mm that satisfy the property in (4). Such sets form a countable family because X\mathcal{X} is countable. For every L∈LL\in\mathcal{L}, assign the first set in this enumeration that is contained in LL, and denote it by TLT_L. The definition of CGTD ensures that this choice exists.

We show that the assignment (TL)L∈L(T_L)_{L\in\mathcal{L}} satisfies (1) and (2). Consider any TLT_L and TL′T_{L'} such that TL∪TL′⊆L,L′T_L\cup T_{L'}\subseteq L,L'. Then each assigned set was an available choice for both languages. Since we chose the first available set according to a fixed enumeration for both languages, we must have TL=TL′T_L=T_{L'}. Therefore, the assignment satisfies (2). Furthermore, we have

⋂L∈L:TL=TL⊇⋂L∈L:T⊆LL.\bigcap_{L\in\mathcal{L}:T_L=T}L\supseteq\bigcap_{L\in\mathcal{L}:T\subseteq L}L.

Consequently, the assignment satisfies (1). Therefore SNC⁡+(L)≤sup⁡L∈L∣TL∣≤m\operatorname{SNC}^{+}(\mathcal{L})\leq\sup_{L\in\mathcal{L}}|T_L|\leq m, proving the last inequality.

For the first separation, use the collection L1={X}∪{X∖{w}:w∈X}\mathcal{L}_1=\{\mathcal{X}\}\cup\{\mathcal{X}\setminus\{w\}:w\in\mathcal{X}\} which is also used by Kalavasis, Mehrotra, and Velegkas [16]. This collection is not stably generatable, so SGTD⁡(L1)=∞\operatorname{SGTD}(\mathcal{L}_1)=\infty. On the other hand, since L1\mathcal{L}_1 is countable, Theorem 5.2 gives GTD⁡(L1)≤1\operatorname{GTD}(\mathcal{L}_1)\leq1.

The second and third separations are witnessed by the constructions in Corollary C.3 and Proposition C.1.

Throughout this appendix, the term “admissible assignment” refers to an element of A(L)\mathcal{A}(\mathcal{L}), as in Definition 5.5.

The following construction witnesses the third separation in Theorem 5.7, between SNC⁡+\operatorname{SNC}^{+} and CGTD.

Proposition C.1. There exists a countable collection L\mathcal{L} such that SNC⁡+(L)=1\operatorname{SNC}^{+}(\mathcal{L})=1 and CGTD⁡(L)=∞\operatorname{CGTD}(\mathcal{L})=\infty.

Proof. For 1≤i<j1\leq i<j, define

Li,j:={2k−1:1≤k<i}∪{2,4,…,2j}∪{2k−1:k≥j},L_{i,j}:=\{2k-1:1\leq k<i\}\cup\{2,4,\ldots,2j\}\cup\{2k-1:k\geq j\},

and let L:={Li,j:1≤i<j}\mathcal{L}:=\{L_{i,j}:1\le i<j\}. This collection is countably infinite, and every language contains an infinite odd tail.

We first show that SNC⁡+(L)≤1\operatorname{SNC}^{+}(\mathcal{L})\le1. Assign TLi,j:={2j}T_{L_{i,j}}:=\{2j\}. Every language assigned {2j}\{2j\} contains the odd tail starting at 2j−12j-1, so

{2k−1:k≥j}⊆⋂L∈L:TL={2j}L\{2k-1:k\ge j\}\subseteq\bigcap_{L\in\mathcal{L}:T_L=\{2j\}}L

Thus the languages assigned the same set have infinite intersection. Furthermore, if j<j′j<j', then 2j′∉Li,j2j'\notin L_{i,j}, since the largest even number in Li,jL_{i,j} is 2j2j. Hence two languages assigned different sets cannot both contain one another’s assigned set. The assignment is therefore admissible, proving SNC⁡+(L)≤1\operatorname{SNC}^{+}(\mathcal{L})\le1. Since the intersection of languages in the class is not infinite, we have SNC⁡+(L)=1\operatorname{SNC}^{+}(\mathcal{L})=1.

We next show that no target has a finite certifiable teaching set. Fix any finite T⊆NT\subseteq\mathbb{N}, and choose an integer m>max⁡(T∪{0})m>\max(T\cup\{0\}). Then T⊆Lm,jT\subseteq L_{m,j} for every j>mj>m. Consequently,

⋂L∈L:T⊆LL⊆⋂j>mLm,j={2k−1:1≤k<m}∪{2,4,…,2m+2}.\bigcap_{L\in\mathcal{L}:T\subseteq L}L\subseteq\bigcap_{j>m}L_{m,j} =\{2k-1:1\le k<m\}\cup\{2,4,\ldots,2m+2\}.

Indeed, the common even elements are those at most 2m+22m+2, and every odd number beyond the initial odd segment is excluded once jj is large enough. The displayed intersection is finite. Since TT was chosen arbitrarily, this implies that CGTD⁡(L)=∞\operatorname{CGTD}(\mathcal{L})=\infty.

The following construction witnesses the second separation in Theorem 5.7, between SGTD and SNC⁡+\operatorname{SNC}^{+}.

Theorem C.2. For every n≥1n\ge1, there is a countably infinite collection Ln\mathcal{L}_n of cofinite languages over a countable domain such that

SGTD⁡(Ln)=1andSNC⁡+(Ln)=n.\operatorname{SGTD}(\mathcal{L}_n)=1\qquad\text{and}\qquad\operatorname{SNC}^{+}(\mathcal{L}_n)=n.

Moreover, the generator witnessing the first equality depends only on the set of observed examples and has exactly two possible outputs.

Proof. Fix n≥1n\ge1, and set

r:=n−1,q:=r2,N:=(2q+1)(q+1),F:=([N]r).r:=n-1,\qquad q:=r^2,\qquad N:=(2q+1)(q+1),\qquad\mathcal{F}:=\binom{[N]}{r}.

We have N≥nN\ge n. When r=0r=0, the family F\mathcal{F} consists only of the empty set. Define two finite marker sets

A:={a1,…,aN},B:={bF:F∈F},A:=\{a_1,\ldots,a_N\},\qquad B:=\{b_F:F\in\mathcal{F}\},

where a1,…,aNa_1,\ldots,a_N and bFb_F, F∈FF\in\mathcal{F} are distinct elements, and countably infinite sets U,VU,V such that AA, BB, UU, and VV are pairwise disjoint. Let M:=A∪BM:=A\cup B and X:=M⊔U⊔VX:=M\sqcup U\sqcup V.

For every i∈[N]i\in[N] and F∈FF\in\mathcal{F}, define

Pi:={bF:i∉F}∪A∪U∪V,P_i:=\{b_F:i\notin F\}\cup A\cup U\cup V,
QF:={ai:i∈F}∪B∪U∪V.Q_F:=\{a_i:i\in F\}\cup B\cup U\cup V.

Now define families Pi\mathcal{P}_i and QF\mathcal{Q}_F that are obtained by allowing at most one deletion from Pi\mathcal{P}_i and QF\mathcal{Q}_F, respectively, as follows:

Pi:={Pi}∪{Pi∖{v}:v∈V},QF:={QF}∪{QF∖{u}:u∈U}.\mathcal{P}_i := \{P_i\} \cup\{P_i \setminus\{v\} : v \in V\}, \qquad\mathcal{Q}_F := \{Q_F\} \cup\{Q_F \setminus\{u\} : u \in U\}.

Set

Ln:=⋃i∈[N]Pi∪⋃F∈FQF.\mathcal{L}_n := \bigcup_{i \in[N]} \mathcal{P}_i \cup\bigcup_{F \in\mathcal{F}} \mathcal{Q}_F.

This collection is countably infinite. Every language omits only finitely many markers and at most one point of U∪VU \cup V, so every language is cofinite. Furthermore, every language in a family Pi\mathcal{P}_i contains all of UU, and every language in a family QF\mathcal{Q}_F contains all of VV.

Proof of SGTD(Ln\mathcal{L}_n) = 1. For a finite training sequence σ∈X∗\sigma\in\mathcal{X}^*, define

J(σ):={i:ai∈supp⁡(σ)}∖⋃F∈FbF∈supp⁡(σ)F.J(\sigma) := \{i : a_i \in\operatorname{supp}(\sigma)\} \setminus\bigcup_{\substack{F \in\mathcal{F}\\ b_F \in\operatorname{supp}(\sigma)}} F.

and let

G(σ):={U,J(σ)≠∅,V,J(σ)=∅.\mathcal{G}(\sigma) := \begin{cases} U, & J(\sigma) \ne\varnothing,\\ V, & J(\sigma) = \varnothing. \end{cases}

This generator depends only on the observed set and always outputs one of the two infinite sets U,VU,V.

For a target L∈PiL \in\mathcal{P}_i, use the singleton teaching set {ai}\{a_i\}. Consider any σ∈L∗\sigma\in L^* containing aia_i. Observe that

i∈{i:ai∈supp⁡(σ)}i \in\{i : a_i \in\operatorname{supp}(\sigma)\}

Furthermore, any bFb_F in any language in Pi\mathcal{P}_i satisfies i∉Fi \notin F. Therefore i∈J(σ)i \in J(\sigma). Consequently, G(σ)=U⊆L\mathcal{G}(\sigma) = U \subseteq L. The same reasoning applies for every continuation of σ\sigma in LL, so the output remains UU.

For a target L∈QFL \in\mathcal{Q}_F, use the singleton teaching set {bF}\{b_F\}. Every marker aia_i that can appear in a sequence consistent with LL has i∈Fi \in F. Once bFb_F has appeared, the union subtracted in the definition of J(σ)J(\sigma) contains all of FF. It therefore contains every possible ii for any observed aia_i, so J(σ)=∅J(\sigma) = \varnothing and G(σ)=V⊆L\mathcal{G}(\sigma) = V \subseteq L. Again, the same argument holds on every consistent continuation, and the output remains VV. Consequently, every target has a singleton stable generation teaching set, proving SGTD(Ln\mathcal{L}_n) ≤1\le1.

Every u∈Uu \in U is excluded by a language QF∖{u}Q_F \setminus\{u\}, and every v∈Vv \in V is excluded by a language Pi∖{v}P_i \setminus\{v\}. It follows that ⋂L∈LnL⊆M\bigcap_{L \in\mathcal{L}_n} L \subseteq M. This intersection is finite, so SGTD(Ln\mathcal{L}_n) =1= 1.

Proof of SNC+(Ln)≤n^+(\mathcal{L}_n) \le n. Assign

TL:={{a1,…,an},L∈⋃iPi,∅,L∈⋃FQF.T_L := \begin{cases} \{a_1,\ldots,a_n\}, & L \in\bigcup_i \mathcal{P}_i,\\ \varnothing, & L \in\bigcup_F \mathcal{Q}_F. \end{cases}

The assigned sets are contained in their targets and have size at most nn. All the languages that are assigned the set {a1,…,an}\{a_1,\ldots,a_n\} contain UU, and all those assigned to ∅\varnothing contain VV. Hence both required intersections are infinite and satisfy the condition (1).

We prove the condition (2). For a pair of languages to be assigned to different sets it must be that one belongs to ⋃FQF\bigcup_F \mathcal{Q}_F and the other belongs to ⋃iPi\bigcup_i \mathcal{P}_i. However, for every F∈FF \in\mathcal{F}, every language in QF\mathcal{Q}_F contains exactly r=n−1r=n-1 markers from AA. Hence, it cannot contain {a1,…,an}\{a_1,\ldots,a_n\}, so mutual consistency is impossible. Therefore the assignment is admissible, and SNC+(Ln)≤n^+(\mathcal{L}_n) \le n.

Proof of SNC⁡+(Ln)≥n\operatorname{SNC}^{+}(\mathcal{L}_n) \ge n. Suppose, for the sake of contradiction, that there is an admissible assignment with ∣TL∣≤n−1=r|T_L| \le n-1=r for every L∈LnL \in\mathcal{L}_n. For a finite set T⊆XT \subseteq\mathcal{X}, define

E(T):=⋃F∈FbF∈TF.E(T):=\bigcup_{\substack{F\in\mathcal{F}\\ b_F\in T}}F.

Each set F∈FF \in\mathcal{F} has size rr, and an assigned teaching set contains at most rr markers from BB. Therefore

∣E(TL)∣≤r∣TL∣≤r2=q.|E(T_L)|\le r|T_L|\le r^2=q.

The only instances missing from PjP_j are the markers bFb_F for which j∈Fj\in F. Consequently, for every finite set TT,

T⊆Pj⟺j∉E(T).(7)T\subseteq P_j\quad\Longleftrightarrow\quad j\notin E(T). \tag*{(7)}

Write Ti:=TPiT_i:=T_{P_i}. If Ti≠TjT_i\ne T_j, condition (2) implies that at least one of Ti⊆PjT_i\subseteq P_j and Tj⊆PiT_j\subseteq P_i fails. By (7), this means j∈E(Ti)j\in E(T_i) or i∈E(Tj)i\in E(T_j). Select ss indices whose teaching sets are pairwise distinct. Each of their (s2)\binom{s}{2} pairs requires at least one such membership. On the other hand, each selected E(Ti)E(T_i) contains at most qq indices and can account for at most qq pairs. Hence, (s2)≤sq\binom{s}{2}\le sq, which gives s≤2q+1s\le2q+1. There are therefore at most 2q+12q+1 different teaching sets among the languages P1,…,PNP_1,\ldots,P_N.

Since N=(2q+1)(q+1)N=(2q+1)(q+1), some teaching set TT occurs on at least q+1q+1 indices. Let

I:={i:Ti=T},∣I∣≥q+1.I:=\{i:T_i=T\},\qquad|I|\ge q+1.

We next show that there must exist some F∈FF\in\mathcal{F} such that QFQ_F receives this same teaching set. The set of indices {i:ai∈T}\{i:a_i\in T\} has size at most rr, so choose an rr-element set F∈FF\in\mathcal{F} containing all of these indices. The language QFQ_F contains the corresponding AA-markers and every point of B∪U∪VB\cup U\cup V. Hence T⊆QFT\subseteq Q_F. Furthermore, ∣E(TQF)∣≤q<∣I∣|E(T_{Q_F})|\le q<|I|, so there is an index i∈I∖E(TQF)i\in I\setminus E(T_{Q_F}). By (7), TQF⊆PiT_{Q_F}\subseteq P_i. We also know from the definition of II that TPi=TT_{P_i}=T and hence TPi⊆QFT_{P_i}\subseteq Q_F. The two teaching sets are mutually consistent. Condition (2) therefore forces TPi=TQF=TT_{P_i}=T_{Q_F}=T.

Fix any v∈V∖Tv\in V\setminus T. The language Pi∖{v}P_i\setminus\{v\} contains TT and is a subset of PiP_i. Its own teaching set is contained in Pi∖{v}P_i\setminus\{v\}, and therefore in PiP_i. Thus TPi=T⊆Pi∖{v}T_{P_i}=T\subseteq P_i\setminus\{v\} and TPi∖{v}⊆PiT_{P_i\setminus\{v\}}\subseteq P_i. Applying (2) again gives TPi∖{v}=TT_{P_i\setminus\{v\}}=T.

Similarly, fix any u∈U∖Tu\in U\setminus T. Since QF∖{u}Q_F\setminus\{u\} contains TT and is contained in QFQ_F, we have TQF=T⊆QF∖{u}T_{Q_F}=T\subseteq Q_F\setminus\{u\} and TQF∖{u}⊆QFT_{Q_F\setminus\{u\}}\subseteq Q_F. Therefore TQF∖{u}=TT_{Q_F\setminus\{u\}}=T as well.

Thus, for every x∈(U∪V)∖Tx\in(U\cup V)\setminus T, there is some L∈LnL\in\mathcal{L}_n with TL=TT_L=T and x∉Lx\notin L. Consequently,

⋂L∈Ln:TL=TL⊆M∪T.\bigcap_{\substack{L\in\mathcal{L}_n:T_L=T}}L\subseteq M\cup T.

Since M∪TM\cup T is finite, this contradicts the infinite-intersection condition for languages assigned the same teaching set. Hence, no assignment of maximum size r=n−1r=n-1 is possible and SNC⁡+(Ln)≥n\operatorname{SNC}^{+}(\mathcal{L}_n)\ge n. Combining the upper and lower bounds proves SNC⁡+(Ln)=n\operatorname{SNC}^{+}(\mathcal{L}_n)=n.

Corollary C.3. There is a countably infinite collection L∞\mathcal{L}_\infty over a countable domain such that SGTD⁡(L∞)=1\operatorname{SGTD}(\mathcal{L}_\infty)=1 and SNC⁡+(L∞)=∞\operatorname{SNC}^{+}(\mathcal{L}_\infty)=\infty.

Proof. For each n≥1n\ge1, let Xn\mathcal{X}_n be the domain of the collection Ln\mathcal{L}_n constructed in Theorem C.2, and let G(n)\mathcal{G}^{(n)} be its generator. Take disjoint tagged copies of these collections. Formally, let

X∞:=⋃n≥1({n}×Xn)andL∞:=⋃n≥1{{n}×L:L∈Ln}.\mathcal{X}_\infty:=\bigcup_{n\ge1}(\{n\}\times\mathcal{X}_n) \qquad\text{and}\qquad \mathcal{L}_\infty:=\bigcup_{n\ge1}\{\{n\}\times L:L\in\mathcal{L}_n\}.

Both the domain and the collection are countable. We first show that SGTD⁡(L∞)=1\operatorname{SGTD}(\mathcal{L}_{\infty})=1.

On a nonempty training sequence σ\sigma whose elements all have the same tag nn, remove the tags, apply G(n)G^{(n)}, and add tag nn to every element of its output. On the empty sequence output any fixed infinite set. For a target {n}×L\{n\}\times L, use the tagged copy of the singleton teaching set for LL. Every consistent sequence containing this point is nonempty and lies entirely in component nn. The component generator is stable and correct once its singleton has appeared, so the tagged generator has the same property. Therefore SGTD⁡(L∞)≤1\operatorname{SGTD}(\mathcal{L}_{\infty})\le1. Languages in different components are disjoint, so their common intersection is empty, ruling out dimension zero.

We next show that SNC⁡+(L∞)=∞\operatorname{SNC}^{+}(\mathcal{L}_{\infty})=\infty. Consider any admissible assignment and restrict it to one tagged component. The no-clash condition continues to hold, since it concerns only pairs of languages. Also, restricting the assignment only removes languages from each collection {L:TL=T}\{L:T_L=T\}, so their common intersection remains infinite. Thus the restriction is an admissible assignment on that component. Removing the tags does not change any teaching-set size. Consequently,

SNC⁡+(L∞)≥SNC⁡+(Ln)=nfor every n≥1.\operatorname{SNC}^{+}(\mathcal{L}_{\infty})\ge\operatorname{SNC}^{+}(\mathcal{L}_n)=n \qquad\text{for every }n\ge1.

No uniform finite bound can satisfy these inequalities, and hence SNC⁡+(L∞)=∞\operatorname{SNC}^{+}(\mathcal{L}_{\infty})=\infty.

Theorem 5.8. For every integer n≥1n\ge1, there exists a countable collection Ln\mathcal{L}_n of infinite languages over a countable domain such that SGTD⁡(Ln)=SNC⁡+(Ln)=CGTD⁡(Ln)=n\operatorname{SGTD}(\mathcal{L}_n)=\operatorname{SNC}^{+}(\mathcal{L}_n)=\operatorname{CGTD}(\mathcal{L}_n)=n.

Proof. Let A={a1,a2,…}A=\{a_1,a_2,\ldots\}, B={b1,b2,…}B=\{b_1,b_2,\ldots\} be disjoint countably infinite sets, and set X=A⊔B\mathcal{X}=A\sqcup B. Define

An={A∪F:F⊆B,∣F∣≤n−1},Bn={B∪F:F⊆A,∣F∣≤n−1},\mathcal{A}_n=\{A\cup F:F\subseteq B,\lvert F\rvert\le n-1\},\qquad\mathcal{B}_n=\{B\cup F:F\subseteq A,\lvert F\rvert\le n-1\},

and let Ln={X}∪An∪Bn\mathcal{L}_n=\{\mathcal{X}\}\cup\mathcal{A}_n\cup\mathcal{B}_n. Every language in Ln\mathcal{L}_n is infinite. Furthermore, Ln\mathcal{L}_n is countable, since a countable set has only countably many finite subsets. By Theorem 5.7, it suffices to show that CGTD⁡(Ln)≤n\operatorname{CGTD}(\mathcal{L}_n)\le n and SGTD⁡(Ln)≥n\operatorname{SGTD}(\mathcal{L}_n)\ge n.

**Proof of CGTD⁡(Ln)≤n.∗∗Define\operatorname{CGTD}(\mathcal{L}_n)\le n.** DefineT_A={a_1,\ldots,a_n}$, TB={b1,…,bn}T_B=\{b_1,\ldots,b_n\}. Every language in Bn\mathcal{B}_n contains at most n−1n-1 elements of AA, so none contains TAT_A. Therefore,

⋂L∈LnTA⊆LL=X∩(⋂L∈An ⁣L)=A.\bigcap_{\substack{L\in\mathcal{L}_n\\T_A\subseteq L}}L=\mathcal{X}\cap\left(\bigcap_{\substack{L\in\mathcal{A}_n}}\!L\right)=A.

The last equality holds because every language in An\mathcal{A}_n contains AA, and AA itself belongs to An\mathcal{A}_n. Similarly, ⋂L∈LnTB⊆LL=B\bigcap_{\substack{L\in\mathcal{L}_n\\T_B\subseteq L}}L=B. Both intersections are infinite. Thus TAT_A certifies every target in An\mathcal{A}_n and the target X\mathcal{X}, while TBT_B certifies every target in Bn\mathcal{B}_n. Since these sets have size nn, we conclude that CGTD⁡(Ln)≤n\operatorname{CGTD}(\mathcal{L}_n)\le n.

Proof of SGTD⁡(Ln)≥n\operatorname{SGTD}(\mathcal{L}_n)\ge n. We first show that, for every finite T⊆XT\subseteq\mathcal{X} with ∣T∣≤n−1\lvert T\rvert\le n-1,

⋂L∈LnT⊆LL=T.(8)\bigcap_{\substack{L\in\mathcal{L}_n\\T\subseteq L}}L=T. \tag*{(8)}

Consider the languages KA=A∪(T∩B)K_A=A\cup(T\cap B), KB=B∪(T∩A)K_B=B\cup(T\cap A). Since ∣T∣≤n−1\lvert T\rvert\le n-1, we have KA∈AnK_A\in\mathcal{A}_n and KB∈BnK_B\in\mathcal{B}_n. Both languages contain TT, and KA∩KB=TK_A\cap K_B=T. Consequently,

T⊆⋂L∈LnT⊆LL⊆KA∩KB=T,T\subseteq\bigcap_{\substack{L\in\mathcal{L}_n\\T\subseteq L}}L\subseteq K_A\cap K_B=T,

proving (8). This already shows that CGTD⁡(Ln)≥n\operatorname{CGTD}(\mathcal{L}_n)\ge n. Next, for the sake of contradiction, suppose there exists a generator G\mathcal{G} which admits stable teaching sets TK⊆KT_K \subseteq K of size at most n−1n-1 for every K∈LnK \in\mathcal{L}_n. Let T=TXT=T_{\mathcal{X}}, and let σ\sigma be a sequence listing the elements of TT. Since TT is a stable teaching set for X\mathcal{X}, we have

G(σ⋅ρ)=G(σ)(9)\mathcal{G}(\sigma\cdot\rho)=\mathcal{G}(\sigma) \tag*{(9)}

for every continuation ρ\rho over X∖T\mathcal{X}\setminus T.

We claim that G(σ)⊆H\mathcal{G}(\sigma)\subseteq H for every H∈LnH\in\mathcal{L}_n containing TT. To prove this, fix such a language HH, and let ρH\rho_H list the elements of TH∖TT_H\setminus T. The concatenation σ⋅ρH\sigma\cdot\rho_H is a sequence of distinct elements of HH and contains THT_H. Therefore, the teaching guarantee for HH gives G(σ⋅ρH)⊆H\mathcal{G}(\sigma\cdot\rho_H)\subseteq H. On the other hand, (9) gives G(σ⋅ρH)=G(σ)\mathcal{G}(\sigma\cdot\rho_H)=\mathcal{G}(\sigma). Thus G(σ)⊆H\mathcal{G}(\sigma)\subseteq H, proving the claim.

It follows that G(σ)⊆⋂H∈Ln,T⊆HH\mathcal{G}(\sigma)\subseteq\bigcap_{H\in\mathcal{L}_n,T\subseteq H}H. Since ∣T∣≤n−1|T|\leq n-1, equation (6) implies that the intersection on the right is TT. Hence G(σ)⊆T\mathcal{G}(\sigma)\subseteq T, contradicting the requirement that G(σ)\mathcal{G}(\sigma) is infinite. Therefore SGTD⁡(Ln)≥n\operatorname{SGTD}(\mathcal{L}_n)\geq n.

Theorem 5.9. For every finite collection L\mathcal{L}, the dimensions GTD⁡(L)\operatorname{GTD}(\mathcal{L}), SGTD⁡(L)\operatorname{SGTD}(\mathcal{L}), SNC⁡+(L)\operatorname{SNC}^{+}(\mathcal{L}), and CGTD⁡(L)\operatorname{CGTD}(\mathcal{L}) all equal 00 if ⋂L∈LL\bigcap_{L\in\mathcal{L}}L is infinite, and 11 otherwise.

Proof. Upper bound of 1. For every A⊆LA\subseteq\mathcal{L}, let IA:=⋂K∈AKI_A:=\bigcap_{K\in A}K. Fix L∈LL\in\mathcal{L} and define

BL=⋃A⊆L:L∈A, ∣IA∣<∞IA.B_L=\bigcup_{\substack{A\subseteq\mathcal{L}:\\L\in A,\ |I_A|<\infty}} I_A.

Since L\mathcal{L} is finite, there are only finitely many subfamilies A⊆LA\subseteq\mathcal{L}. Hence BLB_L is a finite union of finite sets and therefore is finite. Since LL is infinite, choose tL∈L∖BLt_L\in L\setminus B_L and set TL:={tL}T_L:=\{t_L\}.

Let AL:={K∈L:tL∈K}A_L:=\{K\in\mathcal{L}:t_L\in K\}. Suppose for the sake of contradiction that IAL=⋂K∈ALKI_{A_L}=\bigcap_{K\in A_L}K is finite. Since L∈ALL\in A_L, the subfamily ALA_L appears in the definition of BLB_L, and hence IAL⊆BLI_{A_L}\subseteq B_L. On the other hand, by the definition of ALA_L, tL∈IALt_L\in I_{A_L}. Therefore tL∈BLt_L\in B_L, contradicting the choice of tLt_L. Thus ∣⋂K∈L:TL⊆KK∣=∞\left|\bigcap_{K\in\mathcal{L}:T_L\subseteq K}K\right|=\infty. Hence, GTD⁡(L)=SGTD⁡(L)=SNC⁡+(L)=CGTD⁡(L)≤1\operatorname{GTD}(\mathcal{L})=\operatorname{SGTD}(\mathcal{L})=\operatorname{SNC}^{+}(\mathcal{L})=\operatorname{CGTD}(\mathcal{L})\leq1.

Dimension 0 iff ⋂L∈LL\bigcap_{L\in\mathcal{L}}L is infinite. If ∣⋂L∈LL∣=∞\left|\bigcap_{L\in\mathcal{L}}L\right|=\infty, we may take TL=∅T_L=\varnothing for every L∈LL\in\mathcal{L}, yielding GTD⁡(L)=SGTD⁡(L)=SNC⁡+(L)=CGTD⁡(L)≤0\operatorname{GTD}(\mathcal{L})=\operatorname{SGTD}(\mathcal{L})=\operatorname{SNC}^{+}(\mathcal{L})=\operatorname{CGTD}(\mathcal{L})\leq0. Conversely, if GTD⁡(L)=0\operatorname{GTD}(\mathcal{L})=0, choose a generator with GTD⁡(L,G)=0\operatorname{GTD}(\mathcal{L},\mathcal{G})=0. Then for every L∈LL\in\mathcal{L}, G(())⊆L\mathcal{G}(())\subseteq L. Thus, ∣⋂L∈LL∣=∞\left|\bigcap_{L\in\mathcal{L}}L\right|=\infty. Together with Theorem 5.7 this completes the proof.

Theorem 5.10. (i) There exists k∈Nk\in\mathbb{N} such that, for every ℓ,n∈N\ell,n\in\mathbb{N}, there exists a family F\mathcal{F} of infinite binary regular languages such that ∣F∣=2ℓ|\mathcal{F}|=2^\ell, each L∈FL\in\mathcal{F} is accepted by a DFA with at most k⋅ℓ⋅nk\cdot\ell\cdot n states, and F\mathcal{F} is not 2n∣F∣2^{n|\mathcal{F}|}-uniformly generatable, while CGTD⁡(F)=1\operatorname{CGTD}(\mathcal{F})=1.

(ii) For every ℓ∈N\ell\in\mathbb{N}, there exists a finite family F\mathcal{F} of infinite binary regular languages such that ∣F∣=2ℓ|\mathcal{F}|=2^\ell, every L∈FL\in\mathcal{F} is recognizable by a DFA with at most ℓ+1\ell+1 states, and NCTD⁡+(F)≥ITD⁡(F)≥∣F∣−1\operatorname{NCTD}^{+}(\mathcal{F})\geq\operatorname{ITD}(\mathcal{F})\geq|\mathcal{F}|-1, while CGTD⁡(F)=0\operatorname{CGTD}(\mathcal{F})=0 and F\mathcal{F} is 00-uniformly generatable.

Proof. The first statement follows from Theorem 4.1 of [1]. The family constructed there has the stated DFA complexity and is not 2n∣F∣2^{n|\mathcal{F}|}-uniformly generatable. Moreover, the common intersection of the languages in the construction is finite. Since F\mathcal{F} is a finite collection of infinite languages, Theorem 5.9 implies that CGTD⁡(F)=1\operatorname{CGTD}(\mathcal{F})=1.

For the second statement, let Σ={a,b}\Sigma=\{a,b\} and define W={w∈Σ∗:∣w∣<ℓ}W=\{w\in\Sigma^*:|w|<\ell\}. Then

∣W∣=∑i=0ℓ−12i=2ℓ−1.|W|=\sum_{i=0}^{\ell-1}2^i=2^\ell-1.

Define L⋆:=Σ∗L_{\star} := \Sigma^{*} and, for every w∈Ww \in W, Lw:=Σ∗∖{w}L_w := \Sigma^{*} \setminus\{w\}. Let F={L⋆}∪{Lw:w∈W}\mathcal{F} = \{L_{\star}\} \cup\{L_w : w \in W\}. Clearly, ∣F∣=1+∣W∣=2ℓ|\mathcal{F}| = 1 + |W| = 2^{\ell}. Furthermore, ⋂L∈FL=Σ∗∖W\bigcap_{L \in\mathcal{F}} L = \Sigma^{*} \setminus W, which implies CGTD⁡(F)=0\operatorname{CGTD}(\mathcal{F}) = 0 and F\mathcal{F} is 0-uniformly generatable.

The language L⋆L_{\star} is recognizable by a one-state DFA. Moreover, for every w∈Ww \in W, the language Σ∗∖{w}\Sigma^{*} \setminus\{w\} can be recognized by a DFA with ∣w∣+2≤ℓ+1|w| + 2 \le\ell+ 1 states: the automaton keeps track of the longest prefix of ww read so far, moves to an accepting sink upon any mismatch, and rejects only when the input ends exactly after reading ww.

We next prove ITD⁡(F)≥2ℓ−1\operatorname{ITD}(\mathcal{F}) \ge2^{\ell} - 1, which immediately implies NCTD⁡+(F)≥2ℓ−1\operatorname{NCTD}^{+}(\mathcal{F}) \ge2^{\ell} - 1. Let (TL)L∈F(T_L)_{L \in\mathcal{F}} be a tell-tale assignment. For every w∈Ww \in W, Lw⊂L⋆L_w \subset L_{\star}, so that the tell-tale set TL⋆T_{L_{\star}} for L⋆L_{\star} is not a subset of LwL_w. Thus w∈TL⋆w \in T_{L_{\star}} for all w∈Ww \in W; in particular, ∣TL⋆∣≥∣W∣=2ℓ−1|T_{L_{\star}}| \ge|W| = 2^{\ell} - 1. □\square

References

  1. [1]Marcelo Arenas, Pablo Barceló, Luis Cofré, and Alexander Kozachinskiy. “Language generation: Complexity barriers and implications for learning”. In: arXiv preprint arXiv:2511.05759 (2025).arxiv.org/abs/2511.05759
  2. [2]Dana Angluin. “Finding Patterns Common to a Set of Strings”. In: Journal of Computer and System Sciences 21.1 (1980), pp. 46–62.DOI
  3. [3]Dana Angluin. “Inductive inference of formal languages from positive data”. In: Information and Control 45.2 (1980), pp. 117–135.DOI
  4. [4]Yannan Bai, Debmalya Panigrahi, and Ian Zhang. “Language generation in the limit: Noise, loss, and feedback”. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2026, pp. 794–816.DOI
  5. [5]Moses Charikar and Chirag Pabbaraju. “Exploring Facets of Language Generation in the Limit”. In: Proceedings of 38th Conference on Learning Theory (COLT). Vol. 291. Proceedings of Machine Learning Research. 2025, pp. 854–887.arxiv.org/abs/2411.15364
  6. [6]Shaun M. Fallat, David G. Kirkpatrick, Hans Ulrich Simon, Abolghasem Soltani, and Sandra Zilles. “On Batch Teaching Without Collusion”. In: Journal of Machine Learning Research 24 (2023), 40:1–40:33.
  7. [7]Nicolas Flammarion, Chirag Pabbaraju, Hristo Papazov, Miltiadis Stouras, and Ola Svensson. “Space-Efficient Language Generation in the Limit”. In: arXiv preprint arXiv:2606.25777 (2026).arxiv.org/abs/2606.25777
  8. [8]Sally A. Goldman and Michael J. Kearns. “On the Complexity of Teaching”. In: Journal of Computer and System Sciences 50.1 (1995), pp. 20–31.
  9. [9]Noah Golowich, Allen Liu, and Abhishek Shetty. “Provably Learning from Modern Language Models via Low Logit Rank”. In: arXiv preprint arXiv:2512.09892 (2025).arxiv.org/abs/2512.09892
  10. [10]Sally A. Goldman and H. David Mathias. “Teaching a Smarter Learner”. In: Journal of Computer and System Sciences 52.2 (1996), pp. 255–267.DOI
  11. [11]E. Mark Gold. “Language identification in the limit”. In: Information and Control 10.5 (1967), pp. 447–474.DOI
  12. [12]Steve Hanneke, Amin Karbasi, Anay Mehrotra, and Grigoris Velegkas. “Language Generation with Feedback: Queries and Mistakes”. In: Proceedings of the 43rd International Conference on Machine Learning (ICML). 2026.
  13. [13]Nirmit Joshi, Gal Vardi, Adam Block, Surbhi Goel, Zhiyuan Li, Theodor Misiakiewicz, and Nathan Srebro. “A theory of learning with autoregressive chain of thought”. In: arXiv preprint arXiv:2503.07932 (2025).arxiv.org/abs/2503.07932
  14. [14]Jon Kleinberg and Sendhil Mullainathan. “Language generation in the limit”. In: Advances in Neural Information Processing Systems (NeurIPS) 37 (2024), pp. 66058–66079.arxiv.org/abs/2404.06757
  15. [15]Jon Kleinberg, Anay Mehrotra, Amin Saberi, and Grigoris Velegkas. “On Language Generation in the Limit with Bounded Memory”. In: arXiv preprint arXiv:2605.30324 (2026).arxiv.org/abs/2605.30324
  16. [16]Alkis Kalavasis, Anay Mehrotra, and Grigoris Velegkas. “On Characterizations for Language Generation: Interplay of Hallucinations, Breadth, and Stability”. In: arXiv preprint arXiv:2412.18530 (2025).arxiv.org/abs/2412.18530
  17. [17]Alkis Kalavasis, Anay Mehrotra, and Grigoris Velegkas. “On the limits of language generation: Trade-offs between hallucination and mode-collapse”. In: Proceedings of the 57th Annual ACM Symposium on Theory of Computing. 2025, pp. 1732–1743.arxiv.org/abs/2411.09642
  18. [18]Adam Tauman Kalai, Ofir Nachum, Santosh S. Vempala, and Edwin Zhang. “Why language models hallucinate”. In: arXiv preprint arXiv:2509.04664 (2025).arxiv.org/abs/2509.04664
  19. [19]Adam Tauman Kalai and Santosh S. Vempala. “Calibrated language models must hallucinate”. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC). 2024, pp. 160–171.arxiv.org/abs/2311.14648
  20. [20]Dima Kuzmin and Manfred K. Warmuth. “Unlabeled Compression Schemes for Maximum Classes”. In: Journal of Machine Learning Research 8 (2007), pp. 2047–2081.
  21. [21]Jon Kleinberg and Fan Wei. “Density measures for language generation”. In: Proceedings of the 66th Annual Symposium on Foundations of Computer Science (FOCS). 2025, pp. 620–658.arxiv.org/abs/2504.14370
  22. [22]Jon Kleinberg and Fan Wei. “Language generation and identification from partial enumeration: Tight density bounds and topological characterizations”. In: Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC). 2026, pp. 1684–1691.arxiv.org/abs/2511.05295
  23. [23]Xiaoyu Li, Andi Han, Jiaojiao Jiang, and Junbin Gao. “Characterizing Language Generation in the Limit: Finite Witnesses and a Separation-Width Hierarch”. In: arXiv preprint arXiv:2609.10525 (2026).arxiv.org/abs/2609.10525
  24. [24]Eran Malach. “Auto-regressive next-token predictors are universal learners”. In: arXiv preprint arXiv:2309.06979 (2023).arxiv.org/abs/2309.06979
  25. [25]Anay Mehrotra, Grigoris Velegkas, Xifan Yu, and Felix Zhou. “Language generation with infinite contamination”. In: arXiv preprint arXiv:2511.07417 (2025).arxiv.org/abs/2511.07417
  26. [26]Anay Mehrotra, Grigoris Velegkas, Xifan Yu, and Felix Zhou. “Differentially private language generation and identification in the limit”. In: arXiv preprint arXiv:2604.08504 (2026).arxiv.org/abs/2604.08504
  27. [27]S. Mahmoud Mousawi and Sandra Zilles. “Positive Characteristic Sets for Relational Pattern Languages”. In: Proceedings of the 49th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM). 2024, pp. 398–412.arxiv.org/abs/2511.12039
  28. [28]Charlotte Peale, Vinod Raman, and Omer Reingold. “Representative language generation”. In: arXiv preprint arXiv:2505.21819 (2025).arxiv.org/abs/2505.21819
  29. [29]Daniel Reidenbach. “A non-learnable class of E-pattern languages”. In: Theoretical Computer Science 350.1 (2006), pp. 91–102.DOI
  30. [30]Daniel Reidenbach. “Discontinuities in pattern inference”. In: Theoretical Computer Science 397.1 (2008). Forty Years of Inductive Inference: Dedicated to the 60th Birthday of Rolf Wiehagen, pp. 166–193.DOI
  31. [31]Vinod Raman, Jiaxun Li, and Ambuj Tewari. “Generation through the lens of learning theory”. In: Proceedings of the 38th Conference on Learning Theory (COLT). Vol. 291. Proceedings of Machine Learning Research. 2025, pp. 4740–4776.arxiv.org/abs/2410.13714
  32. [32]Ananth Raman and Vinod Raman. “Generation from noisy examples”. In: arXiv preprint arXiv:2501.04179 (2025).arxiv.org/abs/2501.04179
  33. [33]Takeshi Shinohara. “Polynomial Time Inference of Extended Regular Pattern Languages”. In: Proceedings of the RIMS Symposium on Software Science and Engineering. 1982, pp. 115–127.

Paper details

vlnc:W_367cgyz6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents