arXiv:2605.30324v1 [cs.DS] 28 May 2026
On Language Generation in the Limit with Bounded Memory Jon Kleinberg Cornell University [email protected]
Anay Mehrotra Stanford University [email protected]
Amin Saberi Stanford University [email protected]
Grigoris Velegkas Google Research [email protected]
Abstract We study language generation in the limit under bounded memory. In this task, a learner observes examples from an unknown target language one at a time and must eventually output only new valid examples from the target. Existing work assumes the learner has access to the entire example history which is a strong assumption, since algorithms operating under realistic resource constraints can retain only limited information about the past. A large body of work in learning theory shows that memory constraints can dramatically change what is learnable; we extend this line of work to language generation in the limit. First, we first study generators that remember no past examples. We show that under a mild restriction on the enumeration, every countable collection of infinite languages remains generable even with no memory. Without this restriction, we give an exact characterization of when memoryless generation is possible. We then turn to quantitative coverage guarantees for finite collections, characterizing the optimal minimax density achievable by memoryless generators — the best density one can guarantee against any collection of a given size. This minimax bound is combinatorial and relies on Sperner’s theorem together with symmetric chain decompositions. We further show that giving the learner a sliding window of the last W examples does not improve this worst-case density, whereas allowing it to store b adaptively chosen past examples strictly improves the achievable density for every b ≥ 1. Finally, we revisit identification in the limit, the classical task where the learner must converge to a single correct hypothesis for the target language. We focus on its well-studied incremental variant, where the learner remembers only its previous guess. Here, although exact identification already fails on a collection of just three languages, we show that a mild relaxation, which only requires convergence to an “approximate” version of the target, is achievable for every finite collection. Together, these results show that bounded memory affects the three tasks differently: generation remains achievable for every countable collection, while density and identification are confined to finite collections, with guarantees that weaken as the collection grows.
Contents 1
Introduction 1 1.1 Model and Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.1 Generation, Density, and Identification . . . . . . . . . . . . . . . . . . . . . . 2 1.1.2 Two Types of Memory and the Resulting Models . . . . . . . . . . . . . . . . . 3 1.1.3 Generation with No Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.4 Density with No Memory, Sliding-Window Examples, and Chosen Examples 4 1.1.5 Approximate Identification with Last-Guess Memory . . . . . . . . . . . . . . 6 1.2 Proof Overviews . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Discussion and Open Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2
Preliminaries
11
3
Generators with No Memory 3.1 Proof of Theorem 1.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Proof of Theorem 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Proof of Theorem 3.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13 14 15 15
4
Density Bounds for Generators with Limited Memory 4.1 Density Bounds for Memoryless Generators . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 No Positive Lower-Density Guarantee . . . . . . . . . . . . . . . . . . . . . . . 4.1.2 Minimax Upper Set-Density for Finite Collections . . . . . . . . . . . . . . . . 4.2 Density Bounds for Generators with a Sliding Window . . . . . . . . . . . . . . . . . 4.3 Density Bounds for Generators with Adaptive Buffers . . . . . . . . . . . . . . . . . .
16 18 18 21 24 29
5
Identification with Last Guess: Incremental Learning 31 5.1 Proof of Proposition 5.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.2 Proof of Theorem 5.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
6
Conclusion
A Further Results on Incremental Generation A.1 Three Languages Already Prevent Exact Identification . . . . . . . . . . . . . . . . . . A.2 Element-Based Generation Can Simulate Infinite Memory via Coding . . . . . . . . . A.3 A Positive Result for Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35 40 40 42 44
1
Introduction
Modeling how languages are learned has long fascinated theoretical computer scientists, and one of the central formal models in this direction is language identification in the limit [Gol67; Ang79; Ang80]. In this task, given a positive enumeration of an unknown target language, the learner repeatedly outputs a hypothesis for the language itself and succeeds if these hypotheses eventually stabilize on the correct target language. This requirement turns out to be quite stringent: Angluin’s [Ang80] results show that identification is achievable only for very limited language families, ruling out even simple infinite collections such as the regular languages. This model of language identification was itself motivated in part by the question of how humans acquire language from positive examples. Building on this perspective, Kleinberg and Mullainathan [KM24] showed that if one weakens the learner’s goal from identifying the target language to generating fresh correct examples from it (which is closer to the real-world requirements of the task), the problem becomes significantly more tractable. They termed this weaker requirement language generation in the limit. More concretely, fix a countable collection of infinite languages L = { L1 , L2 , . . .} over a countable domain X. An adversary chooses a target language K ∈ L and reveals an enumeration x1 , x2 , . . . of K; after round t, the learner has seen the sample St = { x1 , . . . , xt }. It then outputs a new string yt and its goal is that after some finite time t⋆ every output yt lies in K \ St . Kleinberg and Mullainathan [KM24] showed that this weaker task is possible for every countable collection of languages. The contrast between these two results is stark. In both settings, the learner receives the same information: a stream of positive examples from the target language. The only difference is what it must produce. Yet, this difference has dramatic consequences: Identification is possible only for highly restricted families of countable languages, while generation is possible for all of them. This stark contrast raises a natural question: how much more can we demand of a generator before its task becomes as hard as identification? A line of subsequent work has explored this by introducing intermediate notions in which the learner must cover “dense” subsets of the target language [CP25; KW25; KMV26; KW26]. These notions form a hierarchy of tasks between generation and identification, graded by how much of the target language the learner must cover. All of these results, however, share a common assumption: the learner has access to the entire interaction history—at each round, its output depends on the full sample St , and existing constructions rely heavily on this. This is a strong assumption on two fronts. Practically, it does not reflect how humans or modern machine learning systems generate language, since neither retains its full “training data.” Theoretically, it obscures a basic question: how much information about the past is actually necessary for successful generation? Both concerns naturally motivate studying language generation under bounded memory. Bounded-memory restrictions have a long history in learning theory and theoretical computer science. In learning theory, for instance, they appear in active learning [HKLM21], in estimation [Raz16; SVW16; Raz17; SSV19], and in online learning [SWXZ22; PR23]. Most directly relevant to our setting, bounded memory has even been studied for language identification in the limit, through certain iterative and incremental identification models which we discuss in more detail later [LZ96a; CJLZ99]. A recurring lesson from these works is that bounds on memory can qualitatively change what is learnable. This naturally raises the following question for language generation: Which collections can be generated in the limit and what density guarantees are achievable when the learner has bounded memory? 1
1.1
Model and Results
In this section, we state informal statements of our main results. 1.1.1
Generation, Density, and Identification
As discussed above, language generation in the limit (or simply generation) is the easiest task in this hierarchy, and language identification in the limit (or simply identification) is the hardest. Formally, let L = { L1 , L2 , . . .} be a countable collection of infinite languages over a countable domain X, where every Li ⊆ X. An adversary chooses a target language K = Lz ∈ L and reveals an enumeration x1 , x2 , . . . of K, meaning that every element of K appears at least once, though repetitions are allowed. After round t, the learner has seen the sample St = { x1 , . . . , xt }. Then, generation is defined as follows. Informal Definition 1 (Generators; see Section 2). A generator can be of two types: it is element-based if its output at time t is an element yt ∈ X, and it is set-based if its output at time t is an infinite set Gt ⊆ X. Definition 1 (Generation in the limit). The generator G is said to generate K in the limit if, for every enumeration of K, there is a time t∗ such that every output after time t∗ is valid for K. In the element-based case, validity means yt ∈ K \ St ; in the set-based case, it means that the output is an infinite set Gt ⊆ K. The generator G is said to generate a collection L = { L1 , L2 , . . .} if it generates every K ∈ L. In other words, after some finite time, an element-based generator must always produce an unseen element of K, while a set-based generator must always produce an infinite subset of K. As mentioned above, Kleinberg and Mullainathan [KM24] constructed a generator that can generate from any countable collection of languages L in the limit. This generator, however, suffers from “mode collapse:” it may keep generating from smaller and smaller subsets of K, covering only a vanishing fraction of the language. In other words, generation in the limit guarantees validity, but not coverage of K. This motivated several works to study the next task in the hierarchy: generation with “breadth” or density. Dense generation strengthens generation by requiring the learner’s outputs to cover a non-trivial fraction of the target language. To speak about density, it is convenient to think of the learner at round t as outputting a set Gt . One may then ask not just whether Gt ⊆ K, but whether it captures a non-trivial fraction of the target language. Several recent works have proposed quantitative notions of density for measuring how much of the target language the generator covers [CP25; KMV25; KW25; KMV26]. Many of these notions are strong enough to become equivalent to identification or close variants of it. By contrast, the density notions introduced by Kleinberg and Wei [KW25] and subsequently studied by Kleinberg and Wei [KW26] and Mehrotra et al. [MVYZ26] are more tractable. In our work, we follow this density viewpoint. We define and discuss density more carefully in Section 1.1.4. For now, consider the following example: if K = N and at some round the learner outputs Gt = 2N = {2, 4, . . .}, then Gt has density µ ( Gt ; K ) = 1/2 inside K. We say that a generator achieves density 1/2 if it outputs sets Gt with µ ( Gt ; K ) ≥ 1/2 for infinitely many values of t. Finally, we turn to the hardest task in the hierarchy, identification.
2
Definition 2 (Identification in the limit; [Gol67]). The identifier I is said to identify K in the limit if, for every enumeration of K, there is a time t∗ such that for every t ≥ t∗ its output it satisfies Lit = K. The identifier I is said to identify a collection L = { L1 , L2 , . . .} if it identifies every K ∈ L. In other words, identification asks the learner to recover the target language entirely. Generation only requires the learner to produce new elements of K, and ρ-dense generation asks it to produce sets covering a ρ-fraction of the target. Identification is much more restrictive: Gold [Gol67] showed that every finite collection is identifiable, while certain countable collections are not. Later, work by Angluin [Ang80] gives a complete characterization of identifiable collections; this characterization was largely negative and showed that identifiability does not extend much beyond finite collections. Hence, in some sense, finite collections are the most natural family of languages for which identification is possible, and they serve as a testbed for identification results when one imposes additional constraints. With this hierarchy in place, we ask how it changes under bounded memory. 1.1.2
Two Types of Memory and the Resulting Models
To make this question precise, we must first specify what information the learner can carry from one round to the next. In the unbounded-memory model, the learner conditions its output on the entire sample history St . Once memory is bounded, only some of this information can survive. Here, we separate two conceptually different types of information. 1. Information from the environment: The learner may remember previously seen examples from the adversary’s enumeration. 2. Information from the learner’s past actions: A learner may forget the raw examples it has seen and still retain some internal state through its previous outputs. With unbounded memory, the first kind of information is strictly more powerful than the second: a learner that remembers all observed examples can reconstruct its past actions, while the same action sequence could have arisen from many different example histories. With limited memory, however, both kinds of information matter. Past examples are direct evidence about the target language. Past outputs, by contrast, were computed from the entire history seen at the time, so storing a past output is in effect storing a summary of that history. To isolate the contribution of each resource, we study them separately. First, we consider a fully memoryless learner that only “reacts” to the current example (Section 1.1.3). Next, we add two natural forms of limited memory over past examples: a sliding window of the last W examples and a buffer of b examples chosen by the learner. The contrast between them (keeping recent examples versus keeping chosen ones) isolates whether selecting which examples to remember is meaningful (Section 1.1.4). Finally, we strip away memory of past examples and allow only the simplest form of memory over past outputs: the learner’s most recent guess (Section 1.1.5). This last model has also been extensively studied in the iterative and incremental identification literature [LZ96a; CJLZ99]. 1.1.3
Generation with No Memory
We begin with the most extreme setting outlined above: a generator that carries no state from one 3
round to the next. It remembers neither past examples nor its own past outputs, and the current example is its only source of information. Definition 3 (Memoryless generator). Fix an output space Ω. A generator with output space Ω is memoryless if it is specified by a deterministic function G : X → Ω. On round t, after observing the current example xt , the generator outputs G ( xt ). In particular, a memoryless generator is not aware of the round number and has no internal state. Depending on the output model, Ω is either X (for element-based generation) or X∞ (for set-based generation, where X∞ denotes the family of all infinite subsets of X). Since a memoryless generator remembers neither past examples nor its own past outputs, generating from any interesting collection seems hopeless. Indeed, suppose that there is a single “bad” element b on which the generator’s output is invalid for K. Then, the adversary can construct a hard enumeration for G by interleaving copies of b with an otherwise complete enumeration of K, producing a stream of the form x1 , b, x2 , b, x3 , b, . . . and thereby forcing the same mistake infinitely many times. Thus, without restricting repetitions, the adversary can turn a single mistake into infinitely many. This motivates the following mild restriction on the adversary in the memoryless model. Definition 4 (Finitely repeating enumerations). An enumeration ( xn )n∈N of an infinite language K ⊆ X is finitely repeating if every element of X appears only finitely many times in the sequence. Surprisingly, under finitely repeating enumerations, we obtain the following positive result: Theorem 1.1. Every countable collection of infinite languages admits a memoryless set-based generator under finitely repeating enumerations. This extends the positive result of Kleinberg and Mullainathan [KM24] from full-memory to fully memoryless generators. In particular, it shows that the tractability of language generation does not stem from having access to the entire interaction history. The set-based output is essential here (Theorem 3.2). If, given x, the generator could only output a single new string y, it would have no way of telling from the current example x alone whether that string had appeared earlier (and this allows the adversary to always say y before x and force the generator to make a mistake). Outputting an infinite subset of the target avoids this: after viewing finitely many examples, at least one element of the set could still be unseen. One may also ask what happens when the adversary is allowed to repeat elements infinitely often. We give a tight characterization: memoryless generation is possible if and only if, in the full-memory set-based model, every language in L can already be generated after seeing any single example (Theorem 3.1). We overview the proof of Theorem 1.1 in Section 1.2; formal details of this setting are in Section 3. 1.1.4
Density with No Memory, Sliding-Window Examples, and Chosen Examples
The previous section established that memoryless generation is possible in the limit (Theorem 1.1). In other words, that there is an algorithm which in the limit produces new unseen examples from the target language and never outputs examples from outside it. However, the outputs of
4
this generator may still cover only a vanishing fraction of the target. We now ask what density guarantees are possible under bounded memory. We study three memory models: the memoryless model from the previous section, a sliding window of the last W examples, and a buffer of b examples chosen by the learner. For each, we ask for the best density a generator can guarantee against any collection of a given size. It turns out that no positive density is achievable for arbitrary countable collections under bounded memory, so we focus on finite collections. As we noted earlier, finite collections serve as the natural testbed for identification under additional constraints; here we use them analogously for density. The answer is governed by the “width” of the Boolean lattice: For z ∈ N, define z µ(z) := . ⌊z/2⌋ This is the size of the largest antichain in the lattice 2[z] . (Recall that an antichain in 2[z] is a collection of subsets of {1, . . . , z} in which no subset contains another.) Informal Theorem 1.2 (Minimax Density Guarantees for Finite Collections with Limited Memory). The following hold. 1. No memory; see Theorem 4.1. Fix k ∈ N. For every finite collection L of size k there exists a generator that generates from L in the limit and for infinitely many time steps the set it outputs has density at least 1/µ(k−1) in the target language. Conversely, there is a finite collection of size k for which this bound cannot be improved. 2. Sliding window of W examples; see Theorem 4.10. Fix k, W ∈ N. For every finite collection L of size k there exists a generator that generates from L in the limit and for infinitely many time steps the set it outputs has density at least 1/µ(k−1) in the target language. Conversely, there is a finite collection of size k for which this bound cannot be improved. 3. b chosen examples; see Theorem 4.15. Fix k, b ∈ N. For every finite collection L of size k there exists a generator that generates from L in the limit and for infinitely many time steps the set it outputs has density at least 1 , 0 ≤ b ≤ k −3, µ ( k − b − 1) 1 , b ≥ k −2. The three results together give an interesting picture: The first establishes the baseline: memoryless generators can guarantee density 1/µ(k − 1) and this is the optimal in a minimax sense. The second shows that a sliding window does not help: the worst-case minimax density remains 1/µ(k − 1), even with access to the last W examples for any finite W. The third shows that adaptively chosen examples do help: each stored example effectively removes one language from the collection, so the memoryless bound applies to a residual collection of size k − b instead of k. The contrast between the sliding window and the adaptive buffer has a simple explanation. With a sliding window, the adversary can insert long blocks of uninformative examples between informative ones, so that the window never holds more than one informative example at a time. With an adaptive buffer, this is not an obstacle as the learner can keep each informative example once it appears, regardless of what later. 5
We remark that the result in the sliding-window model holds even if the enumeration does not contain any repetitions. We give an overview of the proof of Informal Theorem 1.2 in Section 1.2; formal details of this setting are in Section 4. 1.1.5
Approximate Identification with Last-Guess Memory
Finally, we turn to identification, the strongest task in the hierarchy. As outlined above, we focus on the simplest memory setting: the learner forgets all observed examples and remembers only its most recent guess. Starting from Lange and Zeugmann [LZ96a], a long line of work has studied this problem, with largely negative results. As we show in Proposition 5.1, exact identification can fail even for collections of just three languages. Motivated by this obstruction, we consider a mild relaxation: approximate identification, where the learner may converge to a hypothesis that differs from K on at most finitely many elements. While close variants of this notion have been considered in the literature, to our best knowledge approximate identification itself has not been studied. Surprisingly, we show that approximate identification is possible for all finite collections: Theorem 1.3 (Incremental Approximate Identification). All finite collections are approximately identifiable by a learner that is only allowed to remember its most recent output. The formal details of this result appear in Section 5.
1.2
Proof Overviews
In this section we explain the main ideas behind our proofs. Proof overview of Theorem 1.1. Perhaps the most natural idea is to try to “reduce” the memory consumption of algorithms that work in the full-memory setting, like the one from Kleinberg and Mullainathan [KM24]. In a nutshell, at every time step t, this algorithm keeps track of the “version space,” i.e., the set of all languages consistent with St , and extracts a descending chain of languages from the version space, which they term “critical” languages. Their main insight is that, for large enough t, if one descends sufficiently far down this chain, the algorithm can output some language Lit ⊆ K. Unfortunately, in the memoryless setting we consider, it is prohibitive to estimate the version space, since it requires knowledge of every past example. In fact, it is not hard to see that this is not merely an artifact of the completely memoryless setting; other reasonable settings of bounded memory also face the same obstacle, since approximating the version space requires continuously increasing memory. Another complication is that in order to figure out how far down the chain one needs to descend, it is important to use information about the current round of the game. For instance, a simple rule is to say that in round t one descends down t levels of the chain. Notice that learners in our setting do not have this information, as they are not even aware of the round of the game! Our approach to circumvent these issues is the following: when the learner sees an example x it computes the quantity Jn ( x ) :=
\
L j : j ≤ n and x ∈ L j 6
for n ≤ x,
i.e., the intersection of appropriately long prefixes that are consistent with the singleton element x.1 Then, it outputs Jn(x) ( x ) where n( x ) ≤ x is the largest number for which Jn(x) ( x ) = ∞. Our main insight is that for every Lz ∈ L there are only finitely many x for which n( x ) < z. To see that, notice that there are finitely many languages that appear before Lz . Let Uz be the union of all intersections ∩F such that F ⊆ { L1 , . . . , Lz } and ∩F is finite; since there are only finitely many such F, it follows that Uz is finite. Moreover, we can show that if n( x ) < z for infinitely many x, then Uz needs to be infinite, leading to a contradiction. The formal details appear in Section 3. Proof overview of Informal Theorem 1.2. These results are the most technically involved components of our work. Our proofs all follow the same high-level principle: with limited memory, the generator can only output sets that are simultaneously “safe” for the languages still consistent with the information currently visible, so the problem reduces to understanding how large those safe regions can be. In the memoryless model this leads to an exact Sperner-type minimax value; in the sliding-window model a modified construction shows that a finite window does not enlarge the worst-case safe region; finally, in the model where the generator can store b examples of its choice, each stored example permanently shrinks the “ambiguity,” and by choosing which examples to store the generator can, essentially, reduce the level of uncertainty to one corresponding to a collection of smaller size. We now explain each of the three parts of the result in more detail. Memoryless upper density. For the upper-bound construction in Lemma 4.7, we build a worstcase family using the “middle” layer of the Boolean lattice. Set n n := k − 1 and N := . ⌊n/2⌋ We partition the target language K into N pairwise disjoint infinite sets K = A1 ∪ · · · ∪ A N with µup ( Ai ; K ) = 1/N for all i ∈ [ N ]. We then index these pieces by the N subsets S1 , . . . , S N ⊆ [n] of cardinality exactly ⌊n/2⌋, so that {S1 , . . . , S N } is an antichain by Fact 4.5. For each j ∈ [n], we define [ L j := Ai . i: j∈Si
Now fix any memoryless generator that succeeds on the resulting collection. Outside finitely many bad points, if the current example lies in Ai , then the output must be contained in every L j with j ∈ Si . By the antichain property, we can show that the corresponding intersection reduces back to Ai . Hence, every sufficiently late output has upper density at most 1/N inside K, which gives the desired upper bound. The matching lower bound in Lemma 4.8 is achieved by the canonical memoryless intersection generator: on input x, it outputs the intersection of all languages containing x whenever that intersection is infinite. Fix a target language K ∈ L. For each subset B ⊆ L \ {K } , we consider the relative region R′B := { x ∈ K : SK ( x ) = B} . These regions partition K. We then apply the symmetric chain decomposition from Fact 4.6 to the Boolean lattice on L \ {K }, obtaining exactly N chains. Since the corresponding chain-unions 1 Here, we assume that x can be mapped to a natural number so the comparison with the index n is meaningful.
7
partition K, finite subadditivity of µup implies that some chain-union has upper density at least 1/N. Along that chain, once we pass the finitely many finite regions, the remaining union is contained in a single intersection IB′ that, therefore, also has upper density at least 1/N. Because the corresponding region R′B is infinite, every finitely repeating enumeration of K visits it infinitely often, and at each such time the generator outputs exactly IB′ . This proves the matching lower bound and yields Theorem 4.1. Sliding-window. The upper bound in Lemma 4.12 is obtained by modifying the previous Sperner construction. We again start from the pieces A1 , . . . , A N of upper density 1/N, but now we add a S separator set Z with µup ( Z; K ) = 0 and define L j = Z ∪ i: j∈Si Ai . The target is then enumerated in stages, alternating one point from each Ai with a long block from Z. Once the finite bad sets are exhausted and the separator blocks are longer than the window, every late window either lies entirely inside Z or intersects points from at most one set Ai . In the first case the generator is forced into K∩
n \
Lj = Z ,
j =1
which has upper density 0. In the second case the generator is forced into K∩
\
L j = Ai ∪ Z ,
j ∈ Si
whose upper density is at most 1/N. Thus no finite sliding window can beat the memoryless Sperner bound. The matching lower bound in Theorem 4.10 is immediate from Lemma 4.8: the window-W generator simply ignores the first W − 1 entries of the window and applies the memoryless rule to the most recent example. Adaptive buffer. The proof of Theorem 4.15 uses a greedy residual-version-space algorithm. Given a buffer state M = (u1 , . . . , us ), we define the residual collection L( M ) := L ∈ L : u j ∈ L for every j ∈ [s] . The update rule stores the current example exactly when the buffer is not full and the current example strictly shrinks this residual collection. The output rule is the canonical memoryless intersection generator applied to the current residual collection L( Mt−1 ). Because each insertion removes at least one language from the residual collection and the buffer has size at most b, the buffer stabilizes after finitely many rounds at some final state M∗ . If the final buffer is not full, then every language in L( M∗ ) must contain the target K; otherwise the first witness in K \ L would force one more insertion, contradicting stabilization. Since K ∈ L( M∗ ) as well, the residual intersection is exactly K, and from that point onward the generator outputs K itself, achieving upper density 1. If the final buffer is full, then each insertion has eliminated at least one language, so |L( M∗ )| ≤ k − b. From the stabilization time onward, the learner is exactly the canonical memoryless intersection generator on this smaller residual family. Applying Lemma 4.8 to the residual collection yields the lower bound 1 . k − b −1 (⌊(k−b−1)/2⌋) Conceptually, each stored example removes one language from the effective ambiguity budget, and the memoryless Sperner bound is then applied to the reduced residual problem. 8
The formal details of this result appear in Section 4. Proof overview of Theorem 1.3. Recall that in this setting the learning algorithm cannot remember any of the past examples, but it can remember its most recent output (in the form of an index it of a language Lit ∈ L.). The goal is that, after some finite time step t⋆ , the algorithm outputs only languages that have finite symmetric difference with the target K. We write A ⪯F B to denote that A is an “approximate” subset of B, i.e., it contains finitely many elements outside of B. The first step of our algorithm is to create a topological ordering of the languages based on the ⪯F ordering so that “smaller” languages appear earlier in the ordering. (Since the collection is finite, such an ordering can be found.) This prevents the overgeneralization failure in which the learner gets stuck on a strict superset of K and can never see evidence (in form of samples) that rules out this superset. The algorithm now proceeds as follows: in the first round, it outputs the first language that is consistent with the input. In subsequent rounds, if the previously guessed language is consistent with the current input, the algorithm keeps the same guess. Otherwise, it moves one step forward in the topological ordering. To get the result, we first observe that if some language that the algorithm is currently guessing contains infinitely many elements outside of K, then after some finitely many timesteps the algorithm will move on from this language as it will see an element that contradicts it. On the other hand, if the algorithm is currently guessing K it will never move on. Combining these two observations, along with some technical care, gives the formal result. The details appear in Section 5.
1.3
Discussion and Open Questions
In this work we study variants of memory-bounded language generation in the limit. Our results show a rich landscape. When the learner is permitted to remember past examples but not its past outputs, generation in the limit is always possible, even under the most severe memory restriction. Obtaining non-trivial density bounds, however, forces us to focus on finite collections. Conversely, when the learner forgets past examples but remembers only its last guess, approximate identification – a mild relaxation of identification – remains achievable for all finite collections, circumventing the classical impossibility [LZ96a]. These results reinforce one of the main themes of the paper: memory of past examples and memory of past outputs are different resources, and bounded memory does not make all tasks uniformly harder. Rather, the actual effect of these two resources is subtle and depends both on the learning objective and on the type of information retained. There are several natural questions that arise from our work. The most immediate one concerns approximate identification with bounded memory. Without memory restrictions, approximate identification is achievable if and only if L satisfies the weak Angluin condition [CP25; KMV26]. Does the same condition characterize approximate identification when the learner can only remember its previous guess, or does the memory restriction impose a stronger barrier? We also view our results as a step toward relaxing some of the unrealistic aspects of the language generation model, by showing that it is surprisingly robust to memory restrictions (Theorem 1.1). It would be interesting to understand which other natural restrictions on memory, computation, or access to past data still permit generation for all countable collections.
9
1.4
Related Work
Our work is most directly related to two lines of research: recent work on language generation in the limit, and the older literature on language identification in the limit under bounded-memory restrictions. The first line provides the generation frameworks that our paper builds on, while the second motivates the memory-restricted viewpoint that is central here. Language generation in the limit. We work in the language generation in the limit framework introduced by Kleinberg and Mullainathan [KM24]. Since then, a growing body of work has explored many nearby questions and variants, including uniform and non-uniform notions of generation, models with additional feedback, stronger notions of breadth or density, noisy or incomplete presentations, and partial identification [ABCK25; CP25; CPT25; HKMV25; KMV25; KMSV25; KW25; PRR25; RR25; RLT25; AAK26; BPZ26; CP26; KMV26; KW26; MVYZ26]. Our emphasis is different. Rather than strengthening the feedback model or studying broader, noisier, or more robust variants of generation, we focus on how much memory a learner must retain in order to generate. Language generation in the limit with breadth or density. A particularly relevant subline of this literature studies stronger notions of generation that require the learner not just to produce valid unseen strings, but to do so with some notion of breadth or coverage. This direction is motivated by a basic feature of the original result of Kleinberg and Mullainathan [KM24]: while their generator eventually stops producing strings outside the target language, it may do so by generating from an increasingly thin subset of the target. Several subsequent works therefore introduced stronger requirements that ask the learner to generate more representative, denser, or otherwise broader subsets of the language. These strengthened notions turn out to be substantially harder than basic generation, in many cases bringing the task close to identification [CP25; KMV25; KW25; PRR25; KMV26; KW26]. Our work is orthogonal to this direction. We keep the basic notion of generation fixed and instead study how the picture changes when the learner’s memory is severely restricted. Language identification in the limit with bounded memory. The closest prior line of work studies incremental, or iterative, learning in the limit, where the learner forms its next guess using only its previous guess and the newest example [CJLZ99]. In our framing, the learner forgets all past examples and retains only what is encoded in its current guess. This line of work has grown into a broader literature on bounded-memory identification, studying variants such as bounded example memory and feedback learning [CJLZ99], limited long-term memory [KS95], set-driven and rearrangement-independent restrictions [LZ96b], and temporary or ordinal-bounded memory [JLMZ10; CJS12]. In contrast with the full-memory setting, prior work gives only limited positive results for identification under these bounded-memory models [KS95; LZ96b; CJLZ99]. Indeed, as we show in Proposition 5.1, there is a collection of just three languages that cannot be identified in this model. Surprisingly, however, this impossibility largely stems from the strictness of the definition: as Theorem 5.2 shows, approximate identification, where the learner need only converge to a language differing from the target K in finitely many elements, is achievable for every finite collection by an incremental learner. Language identification in the limit with bounded memory. The incremental learning model has been extensively studied in the literature on language identification in the limit: here, the 10
learner forms its next guess using only its previous guess and the newest example [LZ96a; CJLZ99]. Several variants of this model have also been studied. These include bounded-memory-state learners, where the learner updates from the current example and an auxiliary state that can encode the previous guess together with other finite information [KS21]; counter variants, which keep the incremental learning model but also give the learner a numerical signal such as the current round number, in addition to the current example and previous guess [CM08; Köt14]; and models that retain past examples in restricted ways, including temporary example memory, where stored examples must eventually be forgotten if they are not seen again [JLMZ10], ordinal-bounded example memory, where extensions of stored examples are controlled by an ordinal-valued budget [CJS12], and related restrictions such as limited long-term memory and set-driven or rearrangementindependent learning [KS95; LZ96b]. Much of this literature compares these models to one another, establishing which are stronger than which and which are incomparable. Our work asks a different question: how do bounded-memory restrictions affect the hierarchy of generation, density, and identification? Our work asks a different question: how do bounded-memory restrictions affect the hierarchy of generation, density, and identification? A central theme is that past examples and past outputs behave as different resources: For a fixed amount of past-example memory, our density results show that the best minimax guarantee for finite collections deteriorates as the collection grows. By contrast, in the last-guess setting, Theorem 5.2 shows that every finite collection can be approximately identified; the eventual guess differs from the target on only finitely many elements, and therefore has density one in the target. Concurrent and independent work: space-efficient generation [FPP+26]. Concurrently and independently, Flammarion et al. [FPP+26] also study language generation in the limit under resource constraints. Their work is incomparable with ours: They measure memory as the number of bits used by a streaming learner, and focus on target and hypothesis languages recognized by deterministic finite automata (DFA) with a bounded number of states over a finite alphabet. In that setting, they characterize tradeoffs between space used by the learner and the “amount” of the target hypothesis learned by the learner. We avoid automata-theoretic restrictions on the collection of languages, but model memory in a different and coarser way: we allow the learner to only retain a bounded number of past examples, or only its previous guess. Thus, the two papers ask the same broad question under different resource models.
2
Preliminaries
In this section, we present the necessary background on language generation in the limit. Notation. Let Σ be a finite alphabet and let Σ⋆ denote the set of all finite strings over Σ. We use X to denote an arbitrary countable universe of strings; typically X = Σ⋆ . We fix an arbitrary canonical ordering of the domain X and denote it by ( x1 , x2 , . . . ). A language is an infinite subset L ⊆ X. We denote a collection of languages using L and restrict our attention to collections with finite or countably many elements. For a set A, write [ A]∞ for the collection of infinite subsets of A. For W ∈ N, write AW for the set of ordered W-tuples of A and ( AW )̸= ⊆ AW for the subset of ones with distinct elements. An enumeration of a language K is an infinite sequence x1 , x2 , . . . (possibly
11
with repeats) such that each xt ∈ K and every element of K appears at some time. We use Sn to denote the set of the first n elements in the adversary’s enumeration, Sn := { x1 , . . . , xn }. Generating algorithms (with unbounded memory). A generating algorithm (or simply a generator) is a function G that maps a finite-length history of observed examples from X to a set of “outputs.” The generators are divided into different types by output type: • Element-Based Generators: If G outputs elements of X, we say it is an element-based generator. • Set-Based Generators: If G outputs infinite sets, we say it is a set-based generator. • Index-Based Generators: Index-based generators are set-based generators that always output some language Li from the collection L. Often it is convenient to say index-based generators output an index i ∈ N, meaning that they output Li . Note that each of the above types of generators retains an arbitrarily large number of examples it has observed in the past. Later in this paper, we define more restricted types of generators with bounded memory. Remark 2.1 (Types of Generators). In the original formulation of Kleinberg and Mullainathan [KM24], the generator outputs a single string each round; later work [CP25; KW25; RLT25; KMV26] allows the generator to output a set (or, equivalently, a sampling procedure) once sufficient training data have been observed. We now formally define language generation in the limit. Definition 5 (Language Generation in the Limit [KM24]). Fix some K from the language collection L and a generating algorithm G = (Gn ). At each step n, let Sn ⊆ K be the set of all strings that the algorithm G has seen so far. The algorithm G is said to generate from K in the limit if, for all enumerations of K, there is some n⋆ ∈ N such that for all steps n ≥ n⋆ , 1. if G is element-based, then Gn (Sn ) ∈ K \ Sn ; 2. if G is set-based (including index-based generators), then Gn (Sn ) is infinite and Gn (Sn ) ⊆ K. The collection L allows for generation in the limit (or is generable) if there is an algorithm G that generates from K in the limit for every K ∈ L. To gain some intuition, consider the following example. Example 2.2 (Length-threshold languages). Fix a finite alphabet Σ and consider the countable collection of length-threshold languages L = { L1 , L2 , . . .} where, for each ℓ, Lℓ := { x ∈ Σ⋆ : | x | ≥ ℓ} . Suppose the target is K = Lℓ⋆ and the adversary selects the enumeration x1 , x2 , . . .. After observing Sn , we know that ℓ⋆ ≤ minx∈Sn | x |. Hence any string of length at least mn := minx∈Sn | x | belongs to every language consistent with Sn , and therefore belongs to K. One valid element-based generator outputs the first element in the canonical enumeration of X that has length at least mn and does not appear in Sn . However, this is not a valid set-based generator because it outputs only a single element rather than an infinite set. A valid set-based generator outputs all elements of X of length at least mn that do not appear in Sn .
12
3
Generators with No Memory
In this section, we study generation when the generator carries no state from one round to the next and the current example is its only source of information. Definition 3 (Memoryless generator). Fix an output space Ω. A generator with output space Ω is memoryless if it is specified by a deterministic function G : X → Ω. On round t, after observing the current example xt , the generator outputs G ( xt ). The generator is therefore not aware of the round number and retains no information about earlier examples. Depending on the output model, the output space Ω takes different forms: Ω = X for element-based generators, Ω = X∞ for set-based generators (where X∞ denotes the set of all infinite subsets of X), and for index-based generators, Ω = {1, . . . , N } when L = { L1 , . . . , L N } is finite, and Ω = N when L = { L1 , L2 , . . .} is countably infinite (where output i is interpreted as the language Li ). A memoryless generator succeeds if its outputs satisfy the generation requirement of the corresponding output model (element, set, or index-based) on all sufficiently large rounds of every enumeration of the target language. To build some intuition, fix a collection L and a target language K ∈ L. Suppose that on round t the adversary reveals xt ∈ K and asks the generator to output a fresh element of K, meaning one outside { x1 , . . . , xt−1 , xt }. A memoryless generator cannot in general do this: from the single input xt , it has no way to tell which elements have already been shown. This is why the set-based model is the natural one in the memoryless setting. If the generator outputs an infinite subset of K, then because only finitely many examples have been shown so far, at least one element of this set is unseen. In the classical model of language identification in the limit [Gol67], an enumeration of K is any infinite sequence in which every element of K appears at least once, and the adversary may repeat an element infinitely often. Under this regime, a memoryless generator is highly constrained. Once the current input x is fixed, the generator must always produce the same response. For a set-based memoryless generator G and a target K, call x ∈ K bad if G ( x ) ̸⊆ K. If even one bad point exists, the adversary can repeat it every other round and use the remaining rounds to enumerate the rest of K. A single mistake can therefore be amplified into infinitely many by the adversary. This leads to the following natural restriction. Definition 6 (Finitely repeating enumerations). An enumeration ( xn )n∈N of an infinite language K ⊆ X is finitely repeating if for every x ∈ X, the set {n ∈ N : xn = x } is finite. For convenience, we restate our main result below Theorem 1.1. Every countable collection of infinite languages admits a memoryless set-based generator under finitely repeating enumerations. Theorem 1.1 significantly generalizes the main result of Kleinberg and Mullainathan [KM24], which shows that arbitrary countable collections are generable in the limit when the generator has unrestricted memory. Theorem 1.1 shows that the full countable-collection generality survives even after removing memory altogether, provided the adversary is subject to Definition 6. The proof appears in Section 3.1.
13
The next result shows that Definition 6 is essentially the weakest assumption one could hope for in the memoryless set-based model. Once arbitrary repetitions are allowed, memoryless set-based generation is possible only for very special collections. Theorem 3.1 (Characterization with arbitrary repetitions). Under arbitrary enumerations, a countable collection L of infinite languages admits a memoryless set-based generator if and only if, in the unrestricted (full-memory) set-based model, every language in L can already be generated after any single observed S T example. Equivalently, for every x ∈ L∈L L, { L ∈ L : x ∈ L} is infinite. The condition in Theorem 3.1 requires that each example x by itself certify an infinite subset that is safe for every language containing it. Few natural collections satisfy this requirement. Thus Definition 6 marks the point at which the universal countable-collection guarantee in Theorem 1.1 can hold in the memoryless model. The proof of Theorem 3.1 appears in Section 3.2. The positive result in Theorem 1.1 also relies on set-based output in an essential way. Theorem 3.2. The set-based output in Theorem 1.1 is necessary. Under finitely repeating enumerations, no infinite language is generable by a memoryless element-based generator, and there exists a collection of two infinite languages that is not generable by any memoryless index-based generator. The proof of Theorem 3.2 appears in Section 3.3.
3.1
Proof of Theorem 1.1
Proof. Since X is countable, we may identify it with the positive integers without loss of generality. Fix a sequence L1 , L2 , . . . whose range is L and in which every language in L appears at least once; if L is finite, repeat its finite list to obtain such a sequence. For n, x ∈ N, let Jn ( x ) :=
\
L j : j ≤ n and x ∈ L j ,
with the convention that the intersection of an empty family is N. Then J1 ( x ) is always infinite, so n( x ) := max {n ≤ x : Jn ( x ) is infinite} is well-defined. Define the memoryless set-based generator by G ( x ) := Jn(x) ( x ). Fix a target language K = Lz , and let BK := { x ∈ K : G ( x ) ̸⊆ K }. To show that G succeeds, T it is enough to prove that BK is finite. Let Uz be the union of all sets F := ∩ L∈F L such that T F ⊆ { L1 , . . . , Lz } and F is finite; since there are only finitely many such subfamilies, Uz is finite. Now take x ∈ BK . If n( x ) ≥ z, then because x ∈ Lz , the language Lz appears in the intersection defining Jn(x) ( x ), and hence G ( x ) = Jn(x) ( x ) ⊆ Lz = K, a contradiction. Thus n( x ) < z. If also x ≥ z, then Jz ( x ) must be finite, since otherwise z would be admissible in the definition of n( x ); because x ∈ Lz , we have x ∈ Jz ( x ), and therefore x ∈ Uz . Hence BK ⊆ { x ∈ N : x < z} ∪ Uz , so BK is finite. If EK = ( xt )t∈N is a finitely repeating enumeration of K, then each point of the finite set BK appears only finitely many times in EK . Therefore after some finite stage no bad point ever appears again, and from then on G ( xt ) ⊆ K at every round. Thus G generates from K in the limit.
14
3.2
Proof of Theorem 3.1
Proof. For each x ∈
S
L∈L L, write
Ix :=
\
{ L ∈ L : x ∈ L} .
We first note that the two formulations in the theorem are equivalent. Indeed, in the unrestricted set-based model, after observing the single example x, a generator succeeds simultaneously for every target language containing x if and only if it can output some infinite set A x with A x ⊆ K for every K ∈ L containing x. This is possible if and only if there exists an infinite subset of Ix , which is equivalent to Ix itself being infinite. Thus it is enough to prove the theorem using the condition that Ix is infinite for every x. We now prove the two directions. • Necessity. Assume that L admits a memoryless set-based generator G under arbitrary S enumerations. Suppose toward a contradiction that Ix is finite for some x ∈ L∈L L. Since G ( x ) must be infinite, we have G ( x ) ̸⊆ Ix . Hence there is some K ∗ ∈ L with x ∈ K ∗ but G ( x ) ̸⊆ K ∗ . Now let the adversary choose K ∗ and enumerate it by repeating x infinitely often, say as x, y1 , x, y2 , . . . , where (yi )i∈N lists the rest of K ∗ . Every time the current example is x, the generator outputs the same invalid set G ( x ) ̸⊆ K ∗ . Therefore it fails infinitely many times, contradicting generation in the limit. • Sufficiency. Now assume that Ix is infinite for every x ∈ L∈L L. Define the memoryless S generator by choosing G ( x ) to be any infinite subset of Ix for each such x; for x ∈ / L∈L L, define G ( x ) arbitrarily. If the target language is K ∈ L and the adversary presents an example xt ∈ K, then by definition Ixt ⊆ K, so G ( xt ) ⊆ K. Hence the generator is correct on every round of every enumeration, and in particular generates from K in the limit. S
This proves the theorem.
3.3
Proof of Theorem 3.2
Proof. We treat the two output models separately. Element-based generators. Let G : X → X be memoryless and fix any infinite language K ⊆ X. We show that some finitely repeating enumeration of K makes G fail infinitely often. Let B := / K or G ( x ) = x }. If B is infinite, choose distinct b1 , b2 , . . . ∈ B and a repetition-free {x ∈ K : G (x) ∈ enumeration (zi )i∈N of K; then b1 , z1 , b2 , z2 , . . . is a finitely repeating enumeration of K, and every round with current example bi is a failure. So assume B is finite and set G := K \ B. Then G is infinite and G ( x ) ∈ K \ { x } for every x ∈ G. If some y ∈ K has infinite fiber { x ∈ G : G ( x ) = y}, choose distinct a1 , a2 , . . . from that fiber and a repetition-free enumeration (zi )i∈N of K; then y, a1 , z1 , a2 , z2 , . . . is finitely repeating, and every round with current example ai fails because G ( ai ) = y ∈ Sn . Otherwise every fiber is finite, so G ( G ) is infinite; choose distinct a1 , a2 , . . . ∈ G with distinct images G ( a1 ), G ( a2 ), . . ., and let (zi )i∈N be a repetition-free enumeration of K. Then G ( a1 ), a1 , z1 , G ( a2 ), a2 , z2 , . . . is finitely repeating, and again every round with current example ai fails because G ( ai ) ∈ Sn . Thus no infinite language is generable by a memoryless element-based generator. 15
Index-based generators. For the index-based part, it suffices to give a two-language counterexample. Let L1 := {n ∈ N : n ≡ 0 or 1
(mod 4)}
and
L2 := {n ∈ N : n ≡ 0 or 2
(mod 4)} .
Their intersection C := L1 ∩ L2 = {n ∈ N : n ≡ 0 (mod 4)} is infinite, while neither language contains the other. Let G be any memoryless index-based generator for { L1 , L2 }. On each x ∈ C, the generator must output one of the two allowed hypotheses, L1 or L2 , so one of the sets A1 := { x ∈ C : G ( x ) = L1 } and A2 := { x ∈ C : G ( x ) = L2 } is infinite. If A1 is infinite, choose distinct a1 , a2 , . . . ∈ A1 and a repetition-free enumeration (zi )i∈N of L2 ; then a1 , z1 , a2 , z2 , . . . is a finitely repeating enumeration of L2 , and every round with current example ai fails because the generator outputs L1 ̸⊆ L2 . If A2 is infinite, the symmetric construction with target L1 gives infinitely many failures. Hence this two-language collection is not generable by any memoryless index-based generator.
4
Density Bounds for Generators with Limited Memory
In this section we study density guarantees for generators with bounded memory. Generation in the limit asks only that outputs eventually lie in the target language; density additionally asks what fraction of the target language those outputs cover. We work throughout with set-based generators, and unless stated otherwise we continue to assume finitely repeating enumerations in the sense of Definition 6. The first question is what information about past examples the generator is allowed to retain. We compare three models: the memoryless model (which was also studied in the previous section), a sliding window of recent examples, and an adaptive buffer of examples chosen by the learner. Definition 7 (Limited-memory set-based generators). A set-based generator is said to be of one of the following types. 1. Memoryless: If it is memoryless in the sense of Definition 3. 2. Sliding window of width W: If, for each round t, the generator’s output depends only on the block of the most recent W examples seen so far: namely x1 , . . . , xt when t < W, and xt−W +1 , . . . , xt when t ≥ W. 3. Adaptive buffer of size b: If the generator maintains a buffer Bt ⊆ St with | Bt | ≤ b, initialized with B0 = ∅. On round t, both the output Gt and the updated buffer Bt depend only on the current example xt and the previous buffer Bt−1 . Here, crucially, the sliding window keeps the most recent examples, informative or not, while the adaptive buffer can keep an informative example once it appears, regardless of what arrives later. In particular, a sliding window of width 1 is just the memoryless model, while the adaptive buffer of size 1 is (weakly) more powerful than the memoryless model. Density of outputs. We use the same notions of density as Kleinberg and Wei [KW25]. We compute all densities with respect to the fixed canonical ordering of X from Section 2. Because every target language is infinite, a single output element has density 0 in the target, so density questions are only meaningful for set-based outputs. 16
Definition 8 (Upper and lower density). Let K ⊆ X be infinite, and list its elements in the canonical order inherited from X as K = {ℓ1 , ℓ2 , . . .}. For n ∈ N, write K≤n := {ℓ1 , . . . , ℓn }. For any S ⊆ X, define µup (S; K ) := lim sup n→∞
| S ∩ K≤n | n
and
µlow (S; K ) := lim inf n→∞
| S ∩ K≤n | . n
We use lim sup and lim inf in the standard sense; in particular, µlow (S; K ) ≤ µup (S; K ) for every S and K. The two can nevertheless be as far apart as possible. For example, if K = N and S=
[
{n ∈ N : (2r )! < n ≤ (2r + 1)!} ,
r ≥1
then S consists of alternating blocks whose lengths grow very quickly. Along the subsequence n = (2r )!, only earlier blocks contribute, and their total size is negligible compared with (2r )!, so |S ∩ K≤n | /n → 0. Along n = (2r + 1)!, the omitted part consists only of earlier gaps, which are negligible compared with (2r + 1)!, so the same ratio tends to 1. Hence µlow (S; N) = 0 and µup (S; N) = 1, so the gap between lower and upper density is as large as possible. If a generator produces outputs G1 , G2 , . . . for a target language K, there are four natural ways to aggregate density over time: lim inf µlow ( Gt ; K ) , t→∞
lim sup µlow ( Gt ; K ) , t→∞
lim inf µup ( Gt ; K ) , t→∞
and
lim sup µup ( Gt ; K ) . t→∞
The lim inft quantities require that outputs be dense from some point onward, whereas the lim supt quantities only require that dense outputs appear infinitely often. As we will show, three of these four notions collapse to zero in the bounded-memory models we consider, even for small finite collections. We therefore focus on the weakest: lim sup µup ( Gt ; K ) . t→∞
Further, with bounded memory, there exist countable collections on which no generator achieves a positive lim supt µup ( Gt ; K ) for every target K. We therefore restrict attention to finite collections and ask for the best density guarantee a generator can achieve uniformly over all collections of a given size k. For a particular collection L of size k, we are allowed to tailor a generator to L; the adversary then chooses the hardest target language in L and the hardest finitely repeating enumeration of it. The minimax upper density is the largest value that the generator can still guarantee in this game: Definition 9 (Minimax upper density). Fix a memory model M from Definition 7, where for slidingwindow and adaptive-buffer generators the parameter W or b is fixed as part of the model. For k ≥ 1, define M ( k ) to be the supremum over all σ ∈ [0, 1] with the following property: ρup For every collection L of k infinite languages, there exists a set-based generator G in model M that generates from every language in L in the limit and such that, for every target language K ∈ L and every finitely repeating enumeration of K, if G1 , G2 , . . . are the outputs of G, then lim sup µup ( Gt ; K ) ≥ σ . t→∞
17
(Minimax Upper Density)
M ( k ) ≤ σ means that there is some collection L of k infinite Equivalently, an upper bound ρup languages such that every generator in model M can be forced, by a suitable choice of target language and finitely repeating enumeration, to have
lim sup µup ( Gt ; K ) ≤ σ . t→∞
win buf For the three models above, we write ρmem up ( k ), ρup ( k, W ), and ρup ( k, b ); when no ambiguity can arise, we abbreviate these to ρup (k ), ρup (k, W ), and ρup (k, b), respectively. The next sections determine these minimax densities for each of the three memory models.
4.1
Density Bounds for Memoryless Generators
We begin with memoryless generators. With no memory of past examples, such a generator cannot distinguish target languages that share the current example. Therefore, except for finitely many inputs, its output on x must lie inside every language in the collection that contains x. The density is then controlled by how large these intersections can be inside the target language, and the answer is governed by the width of the Boolean lattice. Theorem 4.1 (Memoryless Minimax Upper Density for Finite Collections). In the memoryless generation setting, for every finite number k ∈ N it holds that ρup (k ) =
1 k −1 (⌊(k− 1)/2⌋)
.
This result characterizes the minimax upper density in the memoryless setting. For lower density, we show the following strong negative result. Theorem 4.2 (No uniform positive lower-density guarantee for size-k collections). Fix any integer k ≥ 3. There exists a size-k collection L of infinite languages and a target K ∈ L such that every memoryless set-based generator that generates from all languages in L in the limit (under finitely repeating enumerations) fails to achieve lower density σ infinitely often on K for every σ > 0. In particular„ for any repetition-free enumeration EK = ( x1 , x2 , . . . ) of K, there is t∗ such that for all t > t∗ , µlow (G ( xt ); K ) = 0 . Together, these two theorems separate the two density notions. Upper density admits a positive minimax guarantee for every finite collection size, although the guarantee decays quickly with k: at √ rate k/2k−1 . Lower density admits no positive uniform guarantee once k ≥ 3. The remainder of the section proves both theorems, with most of the work devoted to the upper-density minimax. 4.1.1
No Positive Lower-Density Guarantee
We first prove Theorem 4.2. The proof uses a simple partition argument. Definition 10 (Partition inside a collection). A language K ∈ L is partitioned inside L by L1 , . . . , Lk if S L1 , . . . , Lk ∈ L are pairwise disjoint and K = ik=1 Li .
18
Lemma 4.3 (Lower-density bound from partitions). Let L be a countable collection and G : X → [X]∞ be a memoryless set-based generator that generates from every L ∈ L in the limit under repetition-free enumerations. If K ∈ L is partitioned by L1 , . . . , Lk ∈ L, then for any repetition-free enumeration of K, there exists a time t⋆ such that for all t > t⋆ : µlow (G ( xt ), K ) ≤ maxi∈[k] µlow ( Li , K ) . In particular, if the partition is uniform (i.e., µlow ( Li , K ) = 1/k for all i), the generator cannot infinitely often output a set with density greater than 1/k. Proof. For each i ∈ {1, . . . , k }, let Bi := { x ∈ Li | G ( x ) ̸⊆ Li } be the set of elements where G fails to be consistent with language Li . By the success condition of Definition 5, each Bi must be finite: if some Bi were infinite, any repetition-free enumeration of Li would encounter infinitely many points from Bi , contradicting generation in the limit. S Define the “total error budget” B := ik=1 Bi . Since B is a finite union of finite sets, B is finite. Now, consider any x ∈ K \ B. Because { Li }ik=1 partitions K, there exists a unique j ∈ {1, . . . , k } such that x ∈ L j . Since x ∈ / B, it follows that x ∈ / Bj , which implies: G (x) ⊆ L j . By the monotonicity of the density and G ( x ) ⊆ L j , µlow (G ( x ), K ) ≤ µlow ( L j , K ) ≤ maxi µlow ( Li , K ). Finally, since the enumeration EK = ( x1 , x2 , . . . ) is repetition-free, the finite set B can only appear in the stream for a finite number of rounds. Let t⋆ = max{t | xt ∈ B}. For all t > t⋆ , the example xt is in K \ B, and the density bound holds. Next we need a partition lemma for countable sets. Lemma 4.4 (Zero-lower-density partitions of countable sets). Let K be any countably infinite set with a canonical enumeration K = { x1 , x2 , . . . }, and let m ≥ 2 be an integer. Then there exist pairwise disjoint S infinite subsets A1 , . . . , Am ⊆ K with im=1 Ai = K such that for every i ∈ [m], µlow ( Ai ; K ) = 0 ,
where
µlow ( Ai ; K ) := lim inf n→∞
| Ai ∩ K n | , K n := { x1 , . . . , xn } . n
Proof. We define a set of “rapidly” growing blocks. Let s0 := 0. For each t ≥ 1, define
ℓt := t2 (1 + st−1 ) ,
Bt := {st−1 + 1, . . . , st } ⊆ N .
st := st−1 + ℓt ,
Then { Bt }t≥1 is a partition of N into consecutive nonempty blocks, where the t-th block has length ℓt . Observe that: 1 + st = 1 + t2 (1 + st−1 ) for all t ≥ 1 , (1) Next, for each i ∈ [m] let Ii := {t ∈ N : t ≡ i
(mod m)}
and
Ai :=
[
x j : j ∈ Bt .
t∈ Ii
Because the blocks Bt partition N, the sets A1 , . . . , Am are pairwise disjoint and satisfy im=1 Ai = K. A ∩K n Moreover each Ai is infinite. It remains to show that for each i ∈ [m], lim infn→∞ | i n | = 0. Fix S
19
any i ∈ [m]. Consider any block index t ≥ 2 with t ∈ / Ii (there are infinitely many such t because Ii contains exactly one residue class modulo m). Set n := st . Then K st = { x1 , . . . , xst } consists of S exactly those enumerated elements whose indices lie in r≤t Br . Since t ∈ / Ii , among the blocks { B1 , . . . , Bt }, the ones assigned to bin i are contained in { B1 , . . . , Bt−1 }. Therefore [ x j : j ∈ Br ∩ { x1 , . . . , xst } | Ai ∩ K st | = r ∈ Ii [ = x j : j ∈ Br r ∈ Ii , r ≤t [ ≤ x j : j ∈ Br r ≤ t −1
= s t −1 . Dividing by st gives s t −1 s s t −1 s t −1 1 | Ai ∩ K st | ≤ , ≤ t −1 = = = 2 2 st st s t −1 + ℓ t s t −1 + t (1 + s t −1 ) 1 + t2 (1 + t ) s t −1
(2)
where we used st−1 ≥ 1 for t ≥ 2 and ℓt = t2 (1 + st−1 ). Since there are infinitely many t ∈ / Ii , inequality (2) holds along an infinite subsequence n = st → ∞, and thus lim inf n→∞
1 | Ai ∩ K n | | Ai ∩ K st | ≤ lim ≤ lim = 0. t → ∞ 1 + t2 n st t→∞, t/ ∈ Ii
Because the ratio | Ai ∩ K n | /n is always nonnegative, the lim inf cannot be negative, hence it equals 0. This shows µlow ( Ai ; K ) = 0 for every 1 ≤ i ≤ m. Having shown Lemma 4.4, we are now ready to prove Theorem 4.2. Proof of Theorem 4.2. Fix k ≥ 3 and let K be any countably infinite language (for concreteness, K = N). Apply Lemma 4.4 with m = k − 1 to obtain a partition K = A1 ∪ · · · ∪ Ak−1 into infinite sets with µlow ( Ai ; K ) = 0 for all i. Let L := {K, A1 , . . . , Ak−1 } . Now let G be any memoryless set-based generator that generates from every language in L in the limit under finitely repeating enumerations. By Lemma 4.3 (applied to the partition of K by A1 , . . . , Ak−1 inside L), for any repetition-free enumeration of K there exists t∗ such that for all t > t∗ , µlow (G ( xt ); K ) ≤ max µlow ( Ai ; K ) = 0 . i ∈[k −1]
Hence µlow (G ( xt ); K ) = 0 for all sufficiently large t, so G cannot achieve density σ infinitely often on K for any σ > 0.
20
4.1.2
Minimax Upper Set-Density for Finite Collections
To establish the sharp density bounds for memoryless generators on finite collections, we rely on two foundational results from order theory regarding the Boolean lattice of subsets. Fact 4.5 (Sperner’s Theorem). Let S be a finite set of size n, and let P(S) be its power set. An antichain is a subcollection A ⊆ P(S) such that for any A, B ∈ A with A ̸= B, neither A ⊆ B nor B ⊆ A holds. The n maximum possible size of an antichain in P(S) is exactly (⌊n/2 ⌋ ). Fact 4.6 (Symmetric Chain Decomposition [Eng97]). Let S be a finite set of size n. A chain in P(S) is a sequence of strictly increasing subsets C1 ⊂ C2 ⊂ · · · ⊂ Cm . The Boolean lattice P(S) can be partitioned n into exactly (⌊n/2 ⌋) disjoint symmetric chains, such that every subset in P( S ) belongs to exactly one chain. We now show that for memoryless set-based generators, the achievable upper density on finite collections is entirely governed by the Sperner bound. We first prove that an adversary can always force the upper density to drop to this bound. Lemma 4.7 (Density Bound for Memoryless Generators). Fix any integer k ≥ 2. There exists a collection L of size k and a target language K ∈ L such that the following holds: for every memoryless set-based generator G that generates from L in the limit (under finitely repeating enumerations), and for any repetition-free enumeration EK = ( x1 , x2 , . . . ) of K, there exists a time t∗ such that for all t > t∗ : µup (G ( xt ); K ) ≤
1 k −1 (⌊(k− 1)/2⌋)
.
Proof. For k = 2, the upper density bound evaluates to 1/(10) = 1. Because the upper density of any set cannot exceed 1, the theorem holds trivially for any target in any collection of size 2. Therefore, we may assume without loss of generality that k ≥ 3. n Let n = k − 1 ≥ 2, and define N := (⌊n/2 ⌋). Let the target language K be a countably infinite universe. We partition K into N pairwise disjoint infinite sets, A1 , A2 , . . . , A N , such that the asymptotic upper density of each set within K is exactly uniform, i.e., for each i ∈ [ N ]: µup ( Ai ; K ) = 1 N . (Such a partition can be constructed easily, for instance, by assigning elements in a round-robin fashion according to K’s canonical enumeration, meaning the m-th element belongs to partition Ai where i ≡ m (mod N )). Let S1 , S2 , . . . , S N be the N distinct subsets of {1, 2, . . . , n} that have a cardinality of exactly ⌊n/2⌋. By Fact 4.5, this collection of subsets forms an antichain. Furthermore, since n ≥ 2, we have ⌊n/2⌋ ≥ 1, which guarantees that each subset Si is non-empty. We now construct the remaining n languages in our collection. For each j ∈ [n], define: L j :=
[
Ai .
i: j∈Si
Set r := ⌊n/2⌋. Since we have already reduced to the case k ≥ 3, we have n ≥ 2 and hence r ≥ 1. Fix any j ∈ [n]. Among the r-subsets of [n], the number that contain j is n−1 > 0. r−1 21
Because S1 , . . . , S N enumerate all r-subsets of [n], there exists some i ∈ [ N ] such that j ∈ Si . For this index i, we have Ai ⊆ L j . Since Ai is infinite, it follows that L j is infinite. Moreover, by construction, the L j ’s are distinct. Let our finite collection be L := {K, L1 , . . . , Ln }. Notice that |L| = n + 1 = k. Let G be any memoryless set-based generator that successfully generates from L. By the definition of generation in the limit under finitely repeating enumerations, for every L ∈ L, the set of errors BL := { x ∈ L | G ( x ) ̸⊆ L} is finite: otherwise any repetition-free enumeration of L would S induce infinitely many errors. Because L is a finite collection, the “total error budget” B := L∈L BL is also finite. Consider any element x ∈ K \ B. Because A1 , . . . , A N partition K, there is a unique index i ∈ [ N ] such that x ∈ Ai . By our language construction, x ∈ L j if and only if Ai ⊆ L j , which occurs if and only if j ∈ Si . Because x ∈ / B, the generator must output a set consistent with all languages containing x. Thus: G (x) ⊆ K ∩
\
Lj .
j ∈ Si
Expanding the intersection, we have: \ j ∈ Si
Lj =
\
[
j ∈ Si
Ar .
r: j∈Sr
Because the sets Ar are pairwise disjoint, an element in this intersection must belong to a single partition Ar that is present in the union for every j ∈ Si . This requires j ∈ Sr for all j ∈ Si , meaning Si ⊆ Sr . Because S1 , . . . , S N form an antichain, Si ⊆ Sr implies Si = Sr , and thus i = r. Therefore, the intersection reduces to Ai . For any x ∈ K \ B where x ∈ Ai , we have G ( x ) ⊆ Ai . Finally, let EK = ( x1 , x2 , . . . ) be a repetition-free enumeration of K. Because B is finite, there exists t∗ such that for all t > t∗ , xt ∈ / B. For all such t, the generator is forced to output G ( xt ) ⊆ Ai for some i. Therefore, by the monotonicity of the upper density operator µup (G ( xt ); K ) ≤ µup ( Ai ; K ) =
1 . N
k −1 Substituting N = (⌊(k− 1)/2⌋) completes the proof.
We now show that this bound is tight. Using a symmetric chain decomposition, a generator can always guarantee this upper density infinitely often. Lemma 4.8 (Achievability of the Sperner Bound). For any collection L of k ≥ 2 infinite languages, there k −1 exists a memoryless set-based generator that guarantees an upper density of at least 1/(⌊(k− 1)/2⌋) infinitely often on any target K ∈ L and any finitely repeating enumeration of K. Proof. We first define a modified canonical memoryless set-based generator. For any x ∈ X, define T its signature as S( x ) := { L ∈ L | x ∈ L}, and let Ix := L∈S(x) L be the intersection of all languages in L that contain x. If Ix is infinite, we set G ( x ) := Ix . If Ix is finite, we set G ( x ) := X (or any arbitrary infinite subset of X) to ensure the output remains an infinite set. 22
Let us verify that this generator successfully generates from L in the limit. For any target L ∈ L, an error (G ( x ) ̸⊆ L) can only occur if the finite-intersection fallback is triggered. For any subcollection B ⊆ L, define the exact region R B := { x ∈ X | S( x ) = B}. By definition, any x ∈ R B T satisfies x ∈ IB := L∈ B L, meaning R B ⊆ IB . Thus, if a signature B yields a finite intersection IB , its corresponding exact region R B must also be finite. Since a finite collection L has only finitely many distinct signatures, the union of all exact regions corresponding to finite intersections is a finite set. Therefore, the generator makes only finitely many errors globally, and each of these error-causing inputs can appear only finitely many times under finitely repeating enumerations. Now, fix a target language K ∈ L. There are n = k − 1 other languages in the collection. For any element x ∈ K, we define its relative signature restricted to the other languages: SK ( x ) := { L ∈ L \ { K } | x ∈ L }. For every subset B ⊆ L \ {K }, define the relative region R′B := { x ∈ K | SK ( x ) = B}. These regions are pairwise disjoint and partition K. For any x ∈ R′B , the intersection of all consistent languages in L (including K) is exactly T IB′ := K ∩ L∈ B L. Because any element y ∈ IB′ belongs to K and to all languages in B, its relative signature SK (y) must be a superset of B. Conversely, any element in K with a relative signature C ⊇ B clearly belongs to IB′ . Therefore, we have the equality: [
RC′ = IB′ .
C⊇B n By Fact 4.6, the Boolean lattice of subsets of L \ {K } can be partitioned into exactly N = (⌊n/2 ⌋) chains, which we denote C1 , C2 , . . . , C N . Because these chains partition the power set of L \ {K }, their corresponding families of relative regions partition K. Let Um be the union of all relative regions associated with the subsets in chain Cm : [ Um := R′B . B ∈ Cm
Since
SN
m=1 Um = K, and the limit superior is finitely subadditive, we have: N
1 = µup (K; K ) ≤ ∑ µup (Um ; K ) . m =1
By the Pigeonhole Principle, there must exist at least one chain C∗ such that: µup (U ∗ ; K ) ≥
1 . N
Let the chain C∗ be defined by the sequence of subsets B1 ⊂ B2 ⊂ · · · ⊂ Bh . Let Bj be the smallest subset in this chain such that its relative region R′Bj is infinite. (Such a Bj must exist, because if all regions in the chain were finite, U ∗ would be finite, yielding an upper density of 0, which contradicts 1/N > 0). Because the regions R′B1 , . . . , R′Bj−1 are finite, their upper density is exactly 0. By the finite subadditivity of the upper density, dropping these finite regions does not decrease the density of the rest of the chain. Thus, the upper density of the entire chain U ∗ is carried exclusively by the remaining regions: [ 1 µup R′Bi ; K ≥ µup (U ∗ ; K ) ≥ . i≥ j N 23
Because Bj ⊆ Bi for all i ≥ j, the union of these is precisely a subset of the exact intersection IB′ j : [ i≥ j
R′Bi ⊆
[
RC′ = IB′ j .
C ⊇ Bj
By monotonicity, the upper density of the intersection is at least 1/N: µup ( IB′ j ; K ) ≥
1 . N
Finally, because µup ( IB′ j ; K ) ≥ 1/N > 0, the intersection IB′ j is infinite. Thus, for any element xt ∈ R′Bj , the finite-intersection fallback is not triggered; it outputs exactly the infinite set IB′ j (since Ixt = IB′ j ). Furthermore, because the relative region R′Bj is infinite, any valid finitely repeating enumeration of K must present elements xt ∈ R′Bj infinitely many times. At each of these infinitely many time steps, the generator outputs IB′ j , achieving an upper density of at least 1/N. Equipped with the previous results, the proof of Theorem 4.1 follows as a direct corollary: Proof of Theorem 4.1. If k = 1, then for the unique target language K the generator can output K on every round, so the minimax value is 1 = 1/(00). Hence assume k ≥ 2. From Lemma 4.7, we get that 1 1 ρup (k ) ≤ . Then, Lemma 4.8 shows that ρup (k ) ≥ . This concludes the proof. k −1 k −1 (⌊(k−1)/2⌋)
(⌊(k−1)/2⌋)
Remark 4.9 (Density Bounds for Countable Collections). The finite-collection bounds also imply that no positive uniform upper-density guarantee can hold over all countable collections. One way to see this is to take a disjoint union of the finite hard collections for all k ∈ N; any positive guarantee would contradict the finite bound for sufficiently large k.
4.2
Density Bounds for Generators with a Sliding Window
We next study the sliding-window model, in which the generator can inspect the last W examples in the stream. Throughout this subsection, we restrict attention to repetition-free enumerations. We first give the formal definition of generation in the limit in this model. Definition 11 (Window-W set-based generator). Fix an integer W ≥ 1. A window-W set-based generator is a deterministic function n o G : (XW )̸= → [X]∞ , where (XW )̸= := (y1 , . . . , yW ) ∈ XW : y a ̸= yb for all a ̸= b . Here, (XW )̸= the set of ordered W-tuples of distinct elements of X, and [X]∞ is the family of infinite subsets of X. Given a repetition-free enumeration EK = ( x1 , x2 , . . . ) of a target language K, the output at time t ≥ W is Gt := G ( xt−W +1 , . . . , xt ) . Note that, the first W − 1 rounds may be assigned arbitrary infinite outputs, since all guarantees below are eventual. We say that G generates from K in the limit under repetition-free enumerations if for every repetition-free enumeration EK there exists t∗ such that for all t ≥ max{W, t∗ }, we have Gt ⊆ K. We say that G generates in the limit from a collection of languages L if it generates in the limit from every K ∈ L. 24
We ask the natural sliding-window analogue of the memoryless minimax question: how large an upper-density guarantee can a window-W generator achieve uniformly over all collections of size k? We show that a longer window does not improve over the memoryless setting for any finite W. Recall that ρup (k, W ) denotes the size-k minimax upper-density value in the window-W model (the natural analogue of Definition 9). Our main result in this section is as follows: Theorem 4.10 (Minimax upper-density value for sliding windows). For every k ≥ 1 and W ≥ 1, ρup (k, W ) =
1 k −1 (⌊(k− 1)/2⌋)
.
In particular, increasing the window length does not improve the worst-case upper-density guarantee for finite collections. The rest of this subsection proves the Theorem 4.10. The first step is the following lemma, which is a sliding-window analogue of a basic observation from the memoryless setting. Lemma 4.11 (Finite exceptional set for bad windows). Let W ≥ 1, let L ⊆ X be an infinite language, and let G : (XW )̸= → [X]∞ be a window-W set-based generator that generates from L in the limit under repetition-free enumerations. Then there exists a finite set BL ⊆ L such that for every ordered W-tuple (y1 , . . . , yW ) of distinct elements of L \ BL , G ( y 1 , . . . , yW ) ⊆ L . Proof. Assume for contradiction that no such finite set BL exists. Then for every finite set F ⊆ L there exists an ordered W-tuple of distinct elements F (y1F , . . . , yW ) ∈ ( L \ F )W ̸=
for which
F G (y1F , . . . , yW ) ̸⊆ L .
Fix any repetition-free enumeration z1 , z2 , . . . of L. We construct another repetition-free enumeration of L in stages. Let U0 := ∅. At stage s ≥ 1, let us be the first element of the sequence z1 , z2 , . . . that does not belong to Us−1 , and append us to the output sequence. Now apply the assumption above with F := Us−1 ∪ {us } to obtain an ordered W-tuple τs = (ys,1 , . . . , ys,W ) of distinct elements of L \ F such that G (ys,1 , . . . , ys,W ) ̸⊆ L. Append the W entries of τs immediately after us , and let Us be the set of all elements that have been written so far. By construction, every newly appended element lies outside the previously used set, so the resulting sequence is repetition-free. It is also an enumeration of L: each zr either appears earlier inside one of the tuples τs , or else, once all z1 , . . . , zr−1 have been used, it becomes the selected element us at some later stage. Thus every element of L appears exactly once. Finally, at the last position of the block τs , the current window is exactly
(ys,1 , . . . , ys,W ) , so the generator outputs a set not contained in L. This happens for every stage s, contradicting the assumption that G generates from L in the limit. The next result is the main technical component needed for Theorem 4.10. In fact, it shows something stronger than what is needed for the minimax bound: there is a single collection L and target K ∈ L, together with a single adversarial repetition-free enumeration of K, that witnesses the upper bound for every finite window length W. 25
Lemma 4.12 (A single hard instance for all finite sliding windows). Fix an integer k ≥ 2. There exists a collection L of size k, a target language K ∈ L, and a fixed repetition-free enumeration EK of K such that the following holds. For every integer W ≥ 1 and every window-W set-based generator G that generates from L in the limit under repetition-free enumerations, there exists a time t∗ such that for all t ≥ t∗ , µup ( Gt ; K ) ≤
1 k −1 (⌊(k− 1)/2⌋)
,
where Gt denotes the output of G on the fixed enumeration EK at time t. Proof. For k = 2, the claimed bound is 1, and the statement is trivial since every upper density is at most 1. Hence we may assume k ≥ 3. Set n n := k − 1 and N := . ⌊n/2⌋ Let S1 , . . . , S N be the N subsets of [n] of size exactly ⌊n/2⌋. Thus S1 , . . . , S N form the middle layer of the Boolean lattice on [n]. Choose any countably infinite subset of the domain K, and write its canonical ordering as K = { x1 , x2 , . . . } . We partition K into pairwise disjoint infinite sets K = A1 ∪ · · · ∪ A N ∪ Z with the properties µup ( Ai ; K ) =
1 N
for every i ∈ [ N ] ,
and
µup ( Z; K ) = 0 .
One concrete construction is the following. Place x2m into Z for every m ≥ 1. Let r1 < r2 < r3 < · · · be the positive integers that are not powers of two, and place xrq into Ai whenever q ≡ i (mod N ) (with residues taken in [ N ]). Then each Ai is infinite and the sets are pairwise disjoint. Moreover,
| Z ∩ K m | ≤ 1 + ⌊log2 m⌋ = o (m) , so µup ( Z; K ) = 0, and for every i ∈ [ N ],
| Ai ∩ K m | −
m − |Z ∩ Km | ≤ 1, N
which implies µup ( Ai ; K ) = 1/N. For each j ∈ [ N ], define L j := Z ∪
[
Ai ,
L := {K, L1 , . . . , Ln } .
and
i: j∈Si
As in the memoryless construction, the L j ’s are distinct and infinite. Thus |L| = n + 1 = k. Now fix, once and for all, enumerations: for each 1 ≤ i ≤ N (1)
(2)
Ai = { ai , ai , . . . } ,
26
and partition Z into pairwise disjoint finite sets (for r ≥ 1 and 1 ≤ i ≤ N) define Zr,i ⊆ Z such that
∀r≥1 and 1≤i≤ N ,
| Zr,i | = r
and
Z=
N [ [
Zr,i .
r ≥1 i =1
Let EK be the repetition-free enumeration of K obtained by listing these blocks stage by stage: (1)
(1)
(1)
a1 , Z1,1 , a2 , Z1,2 , . . . , a N , Z1,N
(2)
(2)
(2)
a1 , Z2,1 , a2 , Z2,2 , . . . , a N , Z2,N ,
and
and so on, with each finite block written in an arbitrary order. This is the fixed enumeration promised by the lemma. Now let W ≥ 1, and let G be any window-W set-based generator that generates from every language in L in the limit under repetition-free enumerations. For each language L ∈ L, apply Lemma 4.11 to obtain a finite set BL ⊆ L such that every ordered W-tuple of distinct elements from L \ BL are contained in L. Let [ B := BL . L ∈L
Since L is finite, the set B is finite. Choose r0 ≥ W so large that every element of B ∩ K appears before stage r0 of the fixed enumeration EK . Let t∗ be large enough that for every t ≥ t∗ , the current window ( xt−W +1 , . . . , xt ) lies entirely inside stages r ≥ r0 of EK . Then every point in the current window belongs to K \ B. Moreover, every separator block Zr,i occurring in stages r ≥ r0 has length at least W. Consequently, a window of length W can intersect at most one of the positive-density pieces A1 , . . . , A N . Hence for every t ≥ t∗ , exactly one of the following two cases holds. Case 1 (The current window contains only elements of Z). Since Z ⊆ L j for every j ∈ [ N ], the entire window is contained in each of the languages K, L1 , . . . , Ln . Every element of the window also lies outside the corresponding bad set for each of these languages. Therefore, by the definition of B and Lemma 4.11, Gt ⊆ K ∩
n \
Lj .
j =1
By construction, no set Si equals [ N ], so no point of any Ai belongs to all L j simultaneously. On the other hand, every point of Z belongs to all L j . Thus K∩
n \
Lj = Z ,
and, hence,
µup ( Gt ; K ) ≤ µup ( Z; K ) = 0 .
j =1
Case 2 (The current window contains points from exactly one set Ai , and possibly also points from Z). Every point of Ai belongs exactly to the side languages L j with j ∈ Si , while every point of Z belongs to all side languages. Hence the side languages that contain the entire window are precisely the languages L j with j ∈ Si . As above, the window lies outside the relevant bad sets, so Gt ⊆ K ∩
\ j ∈ Si
27
Lj .
We now compute this intersection. Certainly Ai ∪ Z ⊆ K ∩ j∈Si L j . Conversely, let x ∈ K ∩ j∈Si L j . If x ∈ Z, there is nothing to prove. If x ∈ Ar for some r ∈ [ N ], then x ∈ L j holds exactly when j ∈ Sr . Since x lies in every L j with j ∈ Si , we obtain Si ⊆ Sr . But both Si and Sr have cardinality ⌊n/2⌋, so Si = Sr , hence r = i. Therefore T
K∩
\
T
L j = Ai ∪ Z .
j ∈ Si
It follows that µup ( Gt ; K ) ≤ µup ( Ai ∪ Z; K ) ≤ µup ( Ai ; K ) + µup ( Z; K ) =
1 . N
In both cases, for every t ≥ t∗ we have µup ( Gt ; K ) ≤
1 = N (
1 k −1 ⌊(k−1)/2⌋)
.
Remark 4.13. Note that the order of quantifiers in Lemma 4.12 is stronger than the minimax theorem needs. To show the minimax density bound, it suffices to have a result of the form
∀ sliding-window sizes W ∃ collection L, and K ∈ L ∀ generators G ∃ “hard” enumeration EK , so the hard collection and the adversarial repetition-free enumeration are allowed to depend on the window length. By contrast, Lemma 4.12 proves the stronger statement
∃ collection L, K ∈ L and “hard enumeration EK ∀ sliding-window sizes W ∀ generators G . Thus the hard collection, target, and the adversarial enumeration do not depend on W. A single fixed instance simultaneously works against every finite sliding-window generator. In particular, the obstruction is not merely that each memory size W has its own tailored counterexample; rather, there is one robust finite collection on which no finite sliding window improves on the memoryless Sperner bound. The previous result gives the upper bound. The matching lower bound is immediate from the memoryless result by ignoring all but the most recent example. We now have all the ingredients we need to prove Theorem 4.10. k −1 Proof of Theorem 4.10. Let N := (⌊(k− 1)/2⌋). If k = 1, the unique target language K can be output on every round, so ρup (1, W ) = 1 = 1/N. Hence assume k ≥ 2. The lower bound ρup (k, W ) ≥ 1/N follows from Lemma 4.8: for any collection L of size k, let Gmem : X → [X]∞ be the memoryless generator guaranteed by that theorem, and define the window-W generator Gwin (y1 , . . . , yW ) := Gmem (yW ). Thus Gwin simply ignores the first W − 1 entries of the window and applies the memoryless rule to the most recent example. On every repetition-free enumeration, the outputs of Gwin from time W onward are exactly the outputs of Gmem on the same current examples, so the same infinite set of good times witnesses upper density at least 1/N. The reverse inequality ρup (k, W ) ≤ 1/N is exactly Lemma 4.12. Combining the two bounds proves the claim.
28
Remark 4.14. The proof of Lemma 4.12 shows why the sliding window fails to help: the adversary inserts long blocks of uninformative examples between the informative ones, so that every window contains at most one informative example. This, then allows us to apply the Sperner bound from the memoryless case.
4.3
Density Bounds for Generators with Adaptive Buffers
Finally, we consider the adaptive-buffer model, where the generator can store up to b past examples of its choice. Throughout this section, we write b for the buffer size and reserve k for the size of the finite collection. We also restrict to repetition-free enumerations. Definition 12 (b-buffer set-based generator). Fix an integer b ≥ 0, and let Mb := set-based generator consists of two deterministic functions out : Mb × X → [X]∞
and
r r =0 X . A b-buffer
Sb
upd : Mb × X → Mb ,
such that, for every M = (u1 , . . . , ur ) ∈ Mb and every x ∈ X, each entry of upd( M, x ) lies in {u1 , . . . , ur , x }. Given an enumeration EK = ( x1 , x2 , . . . ) of a target language K, the buffer state Mt ∈ Mb evolves from the empty tuple () by M0 := () ,
Gt := out( Mt−1 , xt ) ,
Mt := upd( Mt−1 , xt ) .
In other words, the generator may keep, discard, reorder, or replace stored examples, but cannot synthesize new buffer contents that did not appear in the interaction. The buffer is the generator’s only persistent state. Similar as before, ρup (k, b) denotes the minimax upper density achievable by set-based generators with adaptive buffers of size b against collections of size k. The main result in this section proves a lower bound on this quantity. Theorem 4.15 (Lower bound for adaptive buffers). Let k ∈ N denote the size of a collection of languages and b ≥ 0 be the size of a memory buffer. Then, 1 , 0 ≤ b ≤ k −3, k − b −1 ρup (k, b) ≥ (⌊(k−b−1)/2⌋) 1, b ≥ k −2. Proof. Fix an arbitrary finite collection L of size k. We describe a b-buffer generator G buf . For an example x ∈ X, let S( x ) := { L ∈ L : x ∈ L} denote the set of languages in L that contain x, which we sometimes refer to as the “global signature” of x. Given a buffer M = (u1 , . . . , us ), define its induced version space by L( M ) := L ∈ L : u j ∈ L for every j ∈ [s] . Thus L(()) = L. We sometimes refer to the induced version space as the residual collection. 29
The update rule is greedy: when the current example is xt , if the buffer is not yet full and L ( Mt − 1 ) ∩ S ( x t ) ⊊ L ( Mt − 1 ) , then append xt to the buffer; otherwise leave the buffer unchanged. Formally, ( ( Mt−1 , xt ) , if | Mt−1 | < b and L( Mt−1 ) ∩ S( xt ) ⊊ L( Mt−1 ) , upd( Mt−1 , xt ) := Mt − 1 , otherwise. The output rule is the canonical intersection generator on the current residual collection: if G∩A ( x ) denotes the canonical memoryless intersection generator from the proof of Lemma 4.8, applied L( M ) to a finite collection A, then at time t we output Gt := G∩ t−1 ( xt ). This defines a valid b-buffer generator. Fix a target language K ∈ L and a repetition-free enumeration EK = ( x1 , x2 , . . . ) of K. Every time the buffer changes, the residual collection L( Mt ) shrinks strictly. Because L is finite and the buffer has size at most b, the buffer stabilizes after finitely many rounds to some final state M∗ = ( u 1 , . . . , u s ) ,
s ≤ b.
We distinguish two cases. Case 1 (The final buffer is not full): Assume s < b. We claim that every language in L( M∗ ) contains K. Suppose not; then there exists some L ∈ L( M∗ ) with K ⊈ L. Choose a witness y ∈ K \ L, and let ty be the unique stage at which y appears in the repetition-free enumeration of K. Since the residual collections only shrink and L survives in the final residual collection, we have L ∈ L( Mty −1 ). Because y ∈ / L, it follows that L( Mty −1 ) ∩ S(y) ⊊ L( Mty −1 ). Also, since the construction never removes stored examples and the final buffer has size s < b, the buffer is not full at stage ty . Hence the update rule would append y at time ty , which would remove L from all subsequent residual collections. This contradicts L ∈ L( M∗ ). Therefore every language in L( M∗ ) contains K. T Since K ∈ L( M∗ ) as well, we have L∈L( M∗ ) L = K. Moreover, for every future current point xt ∈ K, every language in L( M∗ ) contains xt , so the canonical intersection generator on L( M∗ ) outputs exactly K. Thus from the stabilization time onward the generator outputs K on every round, and in particular it achieves upper density 1. Case 2 (The final buffer is full): Assume now that s = b. Every insertion removed at least one language from the residual collection, so |L( M∗ )| ≤ |L| − b. From the stabilization time onward, the generator is exactly the canonical memoryless intersection generator on the fixed residual collection L( M∗ ). If |L( M∗ )| ≥ 3, then by Lemma 4.8 this generator achieves upper density at least 1 ( M∗ )|−1 (⌊(|L|L( M ) ∗ )|−1) /2⌋
infinitely often on the target K, and because (⌊(mm−−1)1/2⌋) is nondecreasing in m and |L( M∗ )| ≤ |L| − b, this is at least 1 . |L|−b−1 (⌊(|L|−b−1)/2⌋) 30
If |L( M∗ )| ≤ 2, then the canonical memoryless intersection generator achieves upper density 1 infinitely often: if the residual collection has size 1, it outputs K exactly from then on; if the residual collection has size 2, say {K, L}, then on each current point x ∈ K it outputs either K or K ∩ L, and either K \ L is infinite (so K is output infinitely often) or K ∩ L is cofinite in K (hence has upper density 1 in K). So in this case the achieved upper density is again at least the claimed bound. Remark 4.16 (The proof does not use evictions). Although Definition 12 allows arbitrary evictions and replacements, the algorithm in the proof of Theorem 4.15 never uses them: it only appends a new example when doing so strictly shrinks the current residual collection, and once the buffer is full it keeps the stored tuple fixed forever. The lower bound therefore holds even for buffers that cannot evict stored examples. Remark 4.17 (Comparison with the memoryless bound). When b = 0, Definition 12 reduces to the memoryless model, and 1 ρup (k, 0) = k −1 (⌊(k−1)/2⌋) by Lemmas 4.7 and 4.8. For general b, the lower bound from Theorem 4.15 is exactly the memoryless Sperner bound with the collection size reduced from k to k − b. Equivalently, for 0 ≤ b ≤ k − 3, ρup (k, b) ≥
k −1 (⌊(k− 1)/2⌋) k − b −1 (⌊(k− b−1)/2⌋)
· ρup (k, 0) .
Thus, each stored example improves the universal guarantee by reducing the effective collection size by one.
5
Identification with Last Guess: Incremental Learning
In this section we study identification under last-guess memory. Here, the learner forgets all past examples and retains only its previous output. This is the classical incremental learning from positive data model introduced by Lange and Zeugmann [LZ96a]. It isolates the second memory resource from the introduction: past outputs rather than past examples. The previous sections studied what generation and density guarantees remain when a generator can retain only limited information about past examples. Here we ask what generation and identification guarantees remain when the learner retains only its most recent guess. Definition 13 (Incremental learner). Fix an output space Ω and an initial output ω0 ∈ Ω. An incremental learner with output space Ω is a deterministic update function A : Ω × X → Ω. Given an enumeration EK = ( xt : t ∈ N), its outputs are defined recursively by for every t ≥ 1 .
ω t = A ( ω t −1 , x t )
As in the earlier sections, the choice of output space determines the kind of model we obtain. We focus here on the index-based identification setting: Ω = {1, . . . , N } for a finite collection L = { L1 , . . . , L N }, or Ω = N for a countable collection, with output it interpreted as the hypothesis 31
language Lit . For finite collections, this means the learner has no extra internal states, synonym indices, or hypotheses outside the collection; its only persistent state is the previous output in {1, . . . , N }. Conceptually, the incremental model is more restricted than the (full-information) identification model of Gold [Gol67], which inspects the entire sample history. At the same time, it is stronger than a memoryless learner: an incremental learner can react differently to the same current example depending on its previous output. Given this strength, one might ask if identification becomes possible in this model. Our first observation is that exact identification remains fragile in the incremental model, even for very small collections. Proposition 5.1 (No exact identification even for three languages). There exists a collection of three infinite languages that is not identifiable in the limit by any incremental index-based learner under arbitrary positive enumerations; indeed, the impossibility already holds for finitely repeating enumerations. The proof appears in Section 5.1. Given this impossibility result, we turn to a natural relaxation of language identification in the limit: instead of requiring the learner to converge to the exact identity of the target language, we ask only that it converge to a language that differs from the target on at most finitely many elements. Since every language in the collection is infinite, two languages that differ on finitely many elements agree on all but a vanishing fraction of their elements. The learner has therefore captured essentially all of the target language, even if it has not pinpointed it exactly. In particular, approximate identification guarantees that all notions of density studied in the previous section (Section 4) take the optimal value 1, and, hence, it is significantly stronger than lower bounding the generator’s density. We formalize approximate identification through the following notion of almost-containment. Definition 14 (Almost-containment). For A, B ⊆ X, write A ⪯F B if A \ B is finite, and write A ∼F B if both A ⪯F B and B ⪯F A hold. Equivalently, A ∼F B if A△ B is finite.
Definition 15 (Approximate identification in the limit). Let L = { L1 , . . . , L N }, let K ∈ L, and let (it )t∈N be the outputs of an incremental index-based learner on an enumeration of K. We say that the learner approximately identifies K in the limit if there exists t∗ such that for every t ≥ t∗ , L i t ∼F K . We say that L is approximately identifiable in the limit by incremental learners if some incremental indexbased learner approximately identifies every K ∈ L on every enumeration of K. As a concrete analogy, imagine learning a mature programming language such as C from examples. Eventually one knows how to write ordinary C programs and all certain obsolete or exceptional corner cases. Such a learner has not identified the language exactly, but has learned almost all of it. This is precisely the kind of the learners the above definition of approximate identification intends to capture. Our main result for the incremental setting shows that this relaxed goal is always achievable for finite collections. 32
Theorem 5.2 (Approximate identification for finite collections). Every finite collection of infinite languages is approximately identifiable in the limit by an incremental index-based learner. Theorem 5.2 stands in sharp contrast to Proposition 5.1: while Proposition 5.1 shows that exact identification can fail already for a collection of size three, Theorem 5.2 shows that approximate identification succeeds for every finite collection. This result also gives one formal version of the contrast between the power of remembering past examples and past outputs. As shown in Section 4, with memory of past examples, the best minimax density guarantee for finite collections deteriorates with the collection size no matter the number of examples the generator remembers. In contrast, with memory of even the last guess, already suffices for enabling approximate identification of every finite collection and, hence, also for aching the optimal density regardless of the finite collection’s size. It is also natural to ask which collections beyond the finite case admit approximate identification by incremental learners. The same argument extends to many countable families, provided the strict almost-containment relation admits a suitable topological ordering in which every target language has only finitely many predecessors. At the opposite extreme, if a collection violates the weak Angluin condition introduced by [CP25; KMV26], then it is not approximately identifiable even by a full-information learner, and hence not by an incremental one either.
5.1
Proof of Proposition 5.1
Proof. Let C := {3n : n ∈ N} and consider the collection L1 := C ∪ {1} ,
L2 := C ∪ {2} ,
L3 := C ∪ {1, 2} .
Suppose toward a contradiction that some incremental index-based learner identifies this collection in the limit. Since the collection has exactly three languages, the learner has only three possible outputs, namely the indices 1, 2, 3, and no additional states. For a finite text σ, let q (σ ) denote the learner’s output after reading σ. Set σ0 := ε ,
σ1 := (1) ,
σ2 := (2) ,
σ12 := (1, 2) ,
and let TC be any repetition-free enumeration of C. The suffixes used below repeat one of the symbols 1, 2 at most once, so all resulting hard texts are still finitely repeating. We claim that the four outputs q (σ0 ) , q (σ1 ) , q (σ2 ) , q (σ12 ) must be pairwise distinct. We use the following observation: if two finite prefixes leave the learner in the same output state, then appending the same suffix produces identical future outputs, because the previous output is the learner’s only persistent state. Indeed, if q (σ1 ) = q (σ2 ), then appending the same suffix TC yields identical future behavior on texts for L1 and L2 , impossible. The same suffix TC shows that q (σ1 ) ̸= q (σ12 ) and q (σ2 ) ̸= q (σ12 ), since the corresponding full texts are texts for L1 and L3 , and for L2 and L3 , respectively. If q (σ0 ) = q (σ1 ), then appending the common suffix consisting of 2 followed by TC yields identical future behavior on texts for L2 and L3 , again impossible. Similarly, q (σ0 ) ̸= q (σ2 ) by appending 1 followed by TC , and q (σ0 ) ̸= q (σ12 ) by appending 1 followed by TC . 33
Thus the learner would need at least four distinct outputs after these four finite texts, but only three outputs are available. This contradiction proves the proposition.
5.2
Proof of Theorem 5.2
Proof. Fix a finite collection L = { L1 , . . . , L N }, and define the strict almost-containment relation by A ≺F B
if and only if
A ⪯F B and B ̸⪯F A .
The relation ≺F is a strict partial order. Indeed, transitivity follows because if A ≺F B and B ≺F C, then A \ C ⊆ ( A \ B) ∪ ( B \ C ) is finite, while C \ A is infinite since all but finitely many elements of the infinite set C \ B lie outside A. Since L is finite, choose a topological ordering and relabel so that Li ≺F L j =⇒ i < j . We consider the incremental learner with initial index i0 := 1 and update rule i t −1 , if xt ∈ Lit−1 , it := min {i / L i t −1 . t−1 + 1, N } , if xt ∈ We will show that this learner approximately identifies every target language in L. So fix a target language K ∈ L, let z be the least index such that Lz = K, and let EK = ( xt )t∈N be any enumeration of K. By construction, the sequence (it )t∈N is nondecreasing and takes values in the finite set {1, . . . , N }. Hence it stabilizes: there exist t0 and i∞ such that it = i∞
for every t ≥ t0 .
We first record a basic observation. Observation 5.3. If it = z for some t ≥ 0, then is = z for every s ≥ t. Proof. Once the learner outputs the index z, its current hypothesis is exactly Lz = K. Every later example belongs to K, and hence belongs to Lz , so the update rule never increments the index again. Thus is = z for all s ≥ t. We now prove the two almost-containment relations separately. Claim 5.4. It holds that K ⪯F Li∞ . Proof. We divide the proof into two cases. Case 1: i∞ = N. We claim that then necessarily z = N. Indeed, if z < N, then since the index sequence starts at i0 = 1 and increases only by steps of size one, in order to reach N it must pass through the value z at some earlier time. But by Observation 5.3, once the sequence reaches z, it can never move again. This contradicts i∞ = N > z. Hence z = N, and therefore Li∞ = L N = K , so in this case K ⪯F Li∞ holds trivially. 34
Case 2: i∞ < N. Take any element y ∈ K \ Li∞ . Let t be the first time at which the enumeration presents y, so xt = y. If t > t0 , then it−1 = i∞ and xt ∈ / Li∞ , so the update rule would force it = min {i∞ + 1, N } > i∞ , contradicting the definition of t0 . Therefore every element of K \ Li∞ must appear by time t0 . Since only finitely many examples appear by time t0 , the set K \ Li∞ is finite. Hence K ⪯F Li∞ . Claim 5.5. It holds that Li∞ ⪯F K. Proof. Suppose for contradiction that Li∞ ̸⪯F K. By Claim 5.4, we already know that K ⪯F Li∞ . Thus the failure of the reverse containment implies that the containment is strict, namely K ≺F Li∞ . By the choice of the topological ordering of L, this forces z < i∞ . But now the monotonicity of the index sequence gives a contradiction. Since i0 = 1 ≤ z and the sequence increases only by one at a time, in order to end at the value i∞ > z, it must pass through the value z at some intermediate stage. By Observation 5.3, once the sequence reaches z, it can never move beyond z. This is impossible. Therefore our assumption was false, and we conclude that Li∞ ⪯F K. Combining Claims 5.4 and 5.5, we obtain Li∞ ∼F K. Since it = i∞ for every t ≥ t0 , it follows that L i t ∼F K
for every t ≥ t0 .
Thus the learner approximately identifies K in the limit. Since K ∈ L and its enumeration were arbitrary, the theorem follows.
6
Conclusion
In this paper, we study how bounded memory changes the hierarchy of generation, density, and identification in the limit. We show that the basic generation guarantee is surprisingly robust to memory restrictions. Theorem 1.1 extends the guarantees of Kleinberg and Mullainathan [KM24] to the memoryless setting: under the mild assumption of finitely-repeating enumerations, every countable collection admits a memoryless set-based generator. Moreover, requiring finite repetitions is necessary with bounded memory (Theorem 3.1), though it is immaterial when the learner has unbounded memory. Next, we turn to the stronger requirement of achieving density. Here the picture is more nuanced: memoryless generators admit a positive minimax upper density (Theorem 4.1) but no positive lower density once the collection has at least three languages (Theorem 4.2). We then ask whether giving the generator more memory of past examples improves the picture. The improvement is limited: a sliding window of any finite length gives no improvement at all (Theorem 4.10), while an adaptive buffer does help by preserving informative examples once they appear (Theorem 4.15). The memory models we have considered so far all involve past examples — keeping none of them, the most recent few, or a self-chosen subset. In the final part of the paper, we turn to a different resource: rather than past examples, the learner remembers only its previous output. Here 35
the picture changes substantially. Although Proposition 5.1 shows that exact identification can fail even for a collection of three languages, Theorem 5.2 shows that a learner remembering only its most recent guess can approximately identify any finite collection. Since approximate identification gives density 1 in the target under all the density notions considered here, remembering only the previous guess suffices for density 1 on every finite collection (Theorem 4.15) — something no fixed amount of sliding-window memory can do. Hence, the type of memory used can matter more than the amount. These results leave several directions open. One is to characterize the countable collections that are approximately identifiable with last-guess memory. Another is to understand what access to the collection is needed to implement bounded-memory generators: our constructions assume the algorithm has full access to the collection, and it remains unclear which oracle, computational, or representation assumptions preserve the same guarantees.
References [AAK26]
Antonios Anastasopoulos, Giuseppe Ateniese, and Evgenios M. Kornaropoulos. Safe Language Generation in the Limit. 2026. arXiv: 2601.08648 [cs.CL]. URL: https://arxiv.org/abs/2601. 08648 (cit. on p. 10).
[ABCK25]
Marcelo Arenas, Pablo Barceló, Luis Cofré, and Alexander Kozachinskiy. Language Generation: Complexity Barriers and Implications for Learning. 2025. arXiv: 2511.05759 [cs.CL]. URL: https: //arxiv.org/abs/2511.05759 (cit. on p. 10).
[Ang79]
Dana Angluin. “Finding Patterns Common to a Set of Strings (Extended Abstract)”. In: Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing. STOC ’79. Atlanta, Georgia, USA: Association for Computing Machinery, 1979, pp. 130–141. ISBN: 9781450374385. DOI: 10.1145/800135.804406. URL: https://doi.org/10.1145/800135.804406 (cit. on p. 1).
[Ang80]
Dana Angluin. “Inductive Inference of Formal Languages From Positive Data”. In: Information and Control 45.2 (1980), pp. 117–135. ISSN: 0019-9958. DOI: https : / / doi . org / 10 . 1016 / S0019-9958(80)90285-5. URL: https://www.sciencedirect.com/science/article/pii/ S0019995880902855 (cit. on pp. 1, 3).
[BPZ26]
Yannan Bai, Debmalya Panigrahi, and Ian Zhang. “Language Generation in the Limit: Noise, Loss, and Feedback”. In: Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2026, pp. 794–816. DOI: 10.1137/1.9781611978971.31. eprint: https: //epubs.siam.org/doi/pdf/10.1137/1.9781611978971.31. URL: https://epubs.siam. org/doi/abs/10.1137/1.9781611978971.31 (cit. on p. 10).
[CJLZ99]
John Case, Sanjay Jain, Steffen Lange, and Thomas Zeugmann. “Incremental Concept Learning for Bounded Data Mining”. In: Information and Computation 152.1 (1999), pp. 74–110. DOI: 10.1006/inco.1998.2784 (cit. on pp. 1, 3, 10, 11).
[CJS12]
Lorenzo Carlucci, Sanjay Jain, and Frank Stephan. “Learning with Ordinal-Bounded Memory from Positive Data”. In: Journal of Computer and System Sciences 78.5 (2012), pp. 1623–1636. DOI: 10.1016/j.jcss.2012.03.002 (cit. on pp. 10, 11).
[CM08]
John Case and Samuel E. Moelius. “U-Shaped, Iterative, and Iterative-with-Counter Learning”. In: Machine Learning 72.1–2 (2008), pp. 63–88. DOI: 10.1007/s10994-008-5057-9 (cit. on p. 11).
36
[CP25]
Moses Charikar and Chirag Pabbaraju. “Exploring Facets of Language Generation in the Limit”. In: Proceedings of Thirty Eighth Conference on Learning Theory (June 30–July 4, 2025). Ed. by Nika Haghtalab and Ankur Moitra. Vol. 291. Proceedings of Machine Learning Research. PMLR, 2025, pp. 854–887. URL: https://proceedings.mlr.press/v291/charikar25a.html (cit. on pp. 1, 2, 9, 10, 12, 33).
[CP26]
Moses Charikar and Chirag Pabbaraju. “Pareto-optimal Non-uniform Language Generation”. In: Proceedings of the 37th International Conference on Algorithmic Learning Theory. ALT 2026. 2026. URL: https://arxiv.org/abs/2510.02795 (cit. on p. 10).
[CPT25]
Moses Charikar, Chirag Pabbaraju, and Ambuj Tewari. “A Characterization of List Language Identification in the Limit”. In: arXiv preprint arXiv:2511.04103 (2025) (cit. on p. 10).
[Eng97]
Konrad Engel. Sperner theory. Vol. 65. Cambridge University Press, 1997 (cit. on p. 21).
[FPP+26]
Nicolas Flammarion, Chirag Pabbaraju, Hristo Papazov, Miltiadis Stouras, and Ola Svensson. “Space-Efficient Language Generation in the Limit”. In: Proceedings of the 39th Annual Conference on Learning Theory. Ed. by Steve Hanneke and Tor Lattimore. Proceedings of Machine Learning Research. To appear. San Diego, CA, USA: PMLR, 2026. URL: https://learningtheory.org/ colt2026/accepted.html (cit. on p. 11).
[Gol67]
E. Mark Gold. “Language Identification in the Limit”. In: Information and Control 10.5 (1967), pp. 447–474. DOI: 10.1016/S0019-9958(67)91165-5 (cit. on pp. 1, 3, 13, 32).
[HKLM21]
Max Hopkins, Daniel Kane, Shachar Lovett, and Michal Moshkovitz. “Bounded Memory Active Learning through Enriched Queries”. In: Proceedings of Thirty Fourth Conference on Learning Theory. Ed. by Mikhail Belkin and Samory Kpotufe. Vol. 134. Proceedings of Machine Learning Research. PMLR, 2021, pp. 2358–2387 (cit. on p. 1).
[HKMV25]
Steve Hanneke, Amin Karbasi, Anay Mehrotra, and Grigoris Velegkas. “On Union-Closedness of Language Generation”. In: Advances in Neural Information Processing Systems. Vol. 38. 2025. URL: https://openreview.net/forum?id=6h7HLx1kbH (cit. on p. 10).
[JLMZ10]
Sanjay Jain, Steffen Lange, Samuel E. Moelius, and Sandra Zilles. “Incremental Learning with Temporary Memory”. In: Theoretical Computer Science 411.31–33 (2010), pp. 2757–2772. DOI: 10.1016/j.tcs.2010.03.029 (cit. on pp. 10, 11).
[KM24]
Jon Kleinberg and Sendhil Mullainathan. “Language Generation in the Limit”. In: Advances in Neural Information Processing Systems. Vol. 37. 2024. URL: https://arxiv.org/abs/2404.06757 (cit. on pp. 1, 2, 4, 6, 10, 12, 13, 35).
[KMSV25]
Amin Karbasi, Omar Montasser, John Sous, and Grigoris Velegkas. “(Im)possibility of Automated Hallucination Detection in Large Language Models”. In: Second Conference on Language Modeling. 2025. URL: https://openreview.net/forum?id=e5jWdZIX0Q (cit. on p. 10).
[KMV25]
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 (STOC’25). Prague, Czech Republic: Association for Computing Machinery, 2025. URL: https://arxiv.org/abs/2411.09642 (cit. on pp. 2, 10).
[KMV26]
Alkis Kalavasis, Anay Mehrotra, and Grigoris Velegkas. “On Characterizations for Language Generation: Interplay of Hallucinations, Breadth, and Stability”. In: Proceedings of the 37th International Conference on Algorithmic Learning Theory. ALT 2026. 2026. URL: https://arxiv. org/abs/2412.18530 (cit. on pp. 1, 2, 9, 10, 12, 33).
[Köt14]
Timo Kötzing. “Iterative Learning from Positive Data and Counters”. In: Theoretical Computer Science 519 (2014), pp. 155–169. DOI: 10.1016/j.tcs.2013.09.023 (cit. on p. 11).
37
[KS21]
Timo Kötzing and Karen Seidel. “Learning Languages in the Limit from Positive Information with Finitely Many Memory Changes”. In: Connecting with Computability. Vol. 12813. Lecture Notes in Computer Science. Springer, 2021, pp. 318–329. DOI: 10.1007/978-3-030-800499_30 (cit. on p. 11).
[KS95]
Efim B. Kinber and Frank Stephan. “Language Learning from Texts: Mind Changes, Limited Memory and Monotonicity (Extended Abstract)”. In: Proceedings of the Eighth Annual Conference on Computational Learning Theory. ACM, 1995, pp. 182–189. DOI: 10.1145/225298.225321 (cit. on pp. 10, 11).
[KW25]
Jon M. Kleinberg and Fan Wei. “Density Measures for Language Generation”. In: 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2025, pp. 620–658. DOI: 10.1109/FOCS63196.2025.00034 (cit. on pp. 1, 2, 10, 12, 16).
[KW26]
Jon M. 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 ’26. To appear. 2026. URL: https: //arxiv.org/abs/2511.05295 (cit. on pp. 1, 2, 10).
[LZ96a]
Steffen Lange and Thomas Zeugmann. “Incremental Learning from Positive Data”. In: Journal of Computer and System Sciences 53.1 (1996), pp. 88–103. DOI: 10.1006/jcss.1996.0051 (cit. on pp. 1, 3, 6, 9, 11, 31).
[LZ96b]
Steffen Lange and Thomas Zeugmann. “Set-Driven and Rearrangement-Independent Learning of Recursive Languages”. In: Mathematical Systems Theory 29.6 (1996), pp. 599–634. DOI: 10. 1007/BF01301968 (cit. on pp. 10, 11).
[MVYZ26]
Anay Mehrotra, Grigoris Velegkas, Xifan Yu, and Felix Zhou. “Language Generation with Infinite Contamination”. In: Proceedings of the 39th Annual Conference on Learning Theory. Ed. by Steve Hanneke and Tor Lattimore. Proceedings of Machine Learning Research. To appear. San Diego, CA, USA: PMLR, 2026. arXiv: 2511.07417 [stat.ML]. URL: https://arxiv.org/abs/ 2511.07417 (cit. on pp. 2, 10).
[PR23]
Binghui Peng and Aviad Rubinstein. “Near Optimal Memory-Regret Tradeoff for Online Learning”. In: Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 2023, pp. 1171–1194. DOI: 10.1109/FOCS57990.2023.00069 (cit. on p. 1).
[PRR25]
Charlotte Peale, Vinod Raman, and Omer Reingold. “Representative Language Generation”. In: Proceedings of the 42nd International Conference on Machine Learning (July 13–19, 2025). Ed. by Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste-Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu. Vol. 267. Proceedings of Machine Learning Research. PMLR, 2025, pp. 48518–48541. URL: https://proceedings.mlr.press/v267/peale25a.html (cit. on p. 10).
[Raz16]
Ran Raz. “Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning”. In: Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 2016, pp. 266–275. DOI: 10.1109/FOCS.2016.36 (cit. on p. 1).
[Raz17]
Ran Raz. “A time-space lower bound for a large class of learning problems”. In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE. 2017, pp. 732–742 (cit. on p. 1).
[RLT25]
Vinod Raman, Jiaxun Li, and Ambuj Tewari. “Generation through the lens of learning theory”. In: Proceedings of Thirty Eighth Conference on Learning Theory (June 30–July 4, 2025). Ed. by Nika Haghtalab and Ankur Moitra. Vol. 291. Proceedings of Machine Learning Research. PMLR, 2025, pp. 4740–4776. URL: https://proceedings.mlr.press/v291/raman25a.html (cit. on pp. 10, 12).
38
[RR25]
Ananth Raman and Vinod Raman. “Generation from Noisy Examples”. In: Proceedings of the 42nd International Conference on Machine Learning (July 13–19, 2025). Ed. by Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste-Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu. Vol. 267. Proceedings of Machine Learning Research. PMLR, 2025, pp. 51079–51093. URL: https://proceedings.mlr.press/v267/raman25a.html (cit. on p. 10).
[SSV19]
Vatsal Sharan, Aaron Sidford, and Gregory Valiant. “Memory-Sample Tradeoffs for Linear Regression with Small Error”. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. 2019, pp. 890–901. DOI: 10.1145/3313276.3316403 (cit. on p. 1).
[SVW16]
Jacob Steinhardt, Gregory Valiant, and Stefan Wager. “Memory, Communication, and Statistical Queries”. In: 29th Annual Conference on Learning Theory. Ed. by Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir. Vol. 49. Proceedings of Machine Learning Research. PMLR, 2016, pp. 1490–1516 (cit. on p. 1).
[SWXZ22]
Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, and Samson Zhou. “Memory Bounds for the Experts Problem”. In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. 2022, pp. 1158–1171. DOI: 10.1145/3519935.3520069 (cit. on p. 1).
39
A
Further Results on Incremental Generation
In this section, we continue our discussion of the incremental model. We first show that exact identification and exact index-based generation can both fail for a collection of just three languages (Section A.1). We then show that this limitation is specific to index-based output: once the generator is allowed to output elements of the domain, the previous output can serve as a codeword that encodes the entire interaction history, effectively reducing the incremental model back to the fullinformation setting (Section A.2). Combining these ideas, we obtain a positive result for incremental element-based generation of every finite collection (Section A.3).
A.1
Three Languages Already Prevent Exact Identification
We begin by showing that exact identification in the incremental model can fail even for very small collections. Theorem A.1. There exists a collection of three infinite languages that is not identifiable in the limit by any incremental index-based learner. Note that any incremental index-based learner that eventually stabilizes to the correct index also succeeds as an incremental index-based generator for the same collection, so an impossibility for generation implies an impossibility for identification. We prove the following stronger result about generation. Proposition A.2. Fix distinct elements a, b, c ∈ X and an infinite set T ⊆ X \ { a, b, c}. Define L1 := T ∪ { a, b} ,
L2 := T ∪ { a, c} ,
L3 := T ∪ {b, c} .
Then the collection L := { L1 , L2 , L3 } is not generable in the limit by any incremental index-based generator. In fact, the impossibility already holds under finitely repeating enumerations. Proof. Suppose toward a contradiction that G : [3] × X → [3] is an incremental index-based generator for L, with initial state i0 ∈ [3]. For a finite sequence σ, let q(σ ) denote the state reached after reading σ, and let R be an injective enumeration of T. The three languages are pairwise incomparable under inclusion. Therefore, if the target language is Lr and the generator succeeds, then from some point onward it must output the index r itself: no other language in the family is a subset of Lr . Hence whenever two finite prefixes can be followed by the same tail to produce valid enumerations for two different target languages, those two prefixes must lead to different states. Set A := q( a), B := q(b), and C := q(c). Comparing the pairs of texts ( a, c, R) and (b, c, R), ( a, b, R) and (c, b, R), and (b, a, R) and (c, a, R), we obtain that A, B, C are pairwise distinct. Since there are exactly three states, this gives
{ A, B, C } = [3] . Call a finite sequence completed for L1 if every distinguished symbol it contains lies in { a, b} and both a and b appear; define completed sequences for L2 and L3 analogously. Appending the common tail R to any completed sequence for Lr yields a valid enumeration for Lr . Since completed 40
prefixes for different target languages must land in different states and there are only three states altogether, there exist distinct states p1 , p2 , p3 such that every completed prefix for Lr lands in pr . In particular, q( a, b) = q(b, a) = p1 ,
q( a, c) = q(c, a) = p2 ,
q(b, c) = q(c, b) = p3 ,
and also q( a, b, a) = q( a, b, b) = p1 ,
q( a, c, a) = q( a, c, c) = p2 ,
q(b, c, b) = q(c, b, c) = p3 .
Next, q( a, a) cannot equal B, since then the texts ( a, a, c, R) and (b, c, R) would reach the same state before the common tail (c, R), even though they are enumerations for L2 and L3 . Similarly, q( a, a) ̸= C, so q( a, a) = A. By symmetry, q(b, b) = B and q(c, c) = C. Therefore G ( A, a) = A ,
G ( B, b) = B ,
G (C, c) = C ,
while the two-element completed prefixes give G ( A, b) = p1 ,
G ( A, c) = p2 ,
G ( B, a) = p1 ,
G ( B, c) = p3 ,
G (C, a) = p2 ,
G (C, b) = p3 ,
and the three-element completed prefixes give G ( p1 , a ) = G ( p1 , b ) = p1 ,
G ( p2 , a ) = G ( p2 , c ) = p2 ,
G ( p3 , b ) = G ( p3 , c ) = p3 .
Now p1 ̸= C: otherwise the last display gives G (C, a) = C = G (C, b), while the previous display gives G (C, a) = p2 and G (C, b) = p3 , forcing p2 = p3 = C, a contradiction since p2 and p3 are distinct. By the same argument, p2 ̸= B and p3 ̸= A. Since { p1 , p2 , p3 } = { A, B, C }, only two cases remain: or ( p1 , p2 , p3 ) = ( A, C, B) ( p1 , p2 , p3 ) = ( B, A, C ) . In the first case, the transition table entries for A, B, C on inputs ( a, b, c) are A : ( A, A, C ) ,
B : ( A, B, B) ,
C : (C, B, C ) ,
B : ( B, B, C ) ,
C : ( A, C, C ) .
while in the second case they are A : ( A, B, A) ,
On the other hand, by definition of A, B, C, the transition entry of the initial state i0 must be ( A, B, C ) , since G (i0 , a) = A, G (i0 , b) = B, and G (i0 , c) = C. Because i0 ∈ [3] = { A, B, C }, its entry must match one of the three entries listed above, but in neither case does any entry equal ( A, B, C ). This contradiction completes the proof. Finally, every enumeration used in the proof repeats each distinguished symbol at most twice and enumerates T injectively, so the same impossibility holds under finitely repeating enumerations. This also proves Theorem A.1: if an incremental index-based learner identified the displayed collection, then, because the three languages are pairwise incomparable, its eventual correct index would be a valid eventual index-based generator output for each target, contradicting Proposition A.2. 41
A.2
Element-Based Generation Can Simulate Infinite Memory via Coding
The impossibility in Proposition A.2 relies crucially on the fact that the output is an index from a finite set [ N ]. An index carries at most log N bits, so after each round the generator retains only a bounded amount of information about the past. (Note that, as we showed in Theorem 5.2, if one relaxes the requirement of identification slightly to allow for a finite number of “errors,” then surprisingly the log N bits retained from the indices are sufficient.) The situation changes completely once the generator is allowed to output an element of the domain X. The key observation is that the previous output is fed back to the generator at the next round, and an element of X can encode an arbitrarily long string. The generator can therefore use its output as a codeword: it embeds a description of the entire observed prefix into the identity of the output element, and at the next round it decodes this description before choosing a new codeword. In this way, a single output element can carry enough information to simulate a full-information learner, and the bounded-memory restriction effectively collapses. From the perspective of bounded-memory learning, this is undesirable: the model no longer limits how much information is retained across rounds, but only hides that information inside the representation of the last output. The apparent “memory bound” is therefore largely an artifact of the output format rather than a genuine restriction on the learner, which is why we do not study this model further. We make this precise using a construction of subsets below. For each language Li in the collection, we select an infinite subset Ci ⊆ Li such that the subsets are pairwise disjoint and each Ci is cofinal2 in the canonical ordering of X. The identity of the subset encodes the current hypothesis or hidden state, while the position of the output within that subset encodes any additional finite information, including the entire observed prefix. Thus the previous output serves as an unbounded storage device for the past (which is, as we mentioned, undesirable). Lemma A.3 (Disjoint infinite cofinal subsets). For every finite collection L = { L1 , . . . , L N } of infinite languages, there exist sets C1 , . . . , CN ⊆ X such that, for every i ∈ [ N ], the set Ci is an infinite subset of Li , the sets C1 , . . . , CN are pairwise disjoint, and for every x ∈ X there exists y ∈ Ci with x ≺ y. Proof. Write the canonical ordering of X as ( x1 , x2 , . . . ). For each t ≥ 1 and i ∈ [ N ], choose an element ci,t ∈ Li recursively as follows. Let Ut,i := c j,r : 1 ≤ r ≤ t − 1, j ∈ [ N ] ∪ c j,t : 1 ≤ j ≤ i − 1 . Since only finitely many elements of X lie at or before x t in the canonical ordering, the infinite set Li contains infinitely many elements above x t ; removing the finite set Ut,i still leaves some y ∈ Li \ Ut,i with x t ≺ y. Let ci,t be the first such y in the canonical ordering. After making these choices for all t and i, set Ci := {ci,t : t ∈ N}. Then each Ci is an infinite subset of Li , the sets C1 , . . . , CN are pairwise disjoint by construction, and for any x ∈ X, taking t with x = x t gives x ≺ ci,t ∈ Ci . Write each Ci in increasing order as Ci = {di,1 ≺ di,2 ≺ di,3 ≺ · · · } . Since the sets are pairwise S disjoint, every element of i∈[ N ] Ci uniquely determines both its language index i and its position within Ci . This is the mechanism that enables coding: the generator can read off both the current hypothesis and the encoded history from a single output element. In this section, an incremental 2A subset C ⊆ X is cofinal (with respect to an ordering ≺) if for every x ∈ X there exists y ∈ C such that x ≺ y.
42
element-based generator means an incremental learner with output space X: it has an initial memory state s0 ∈ X, updates by st = G (st−1 , xt ), and succeeds on a target K if, for all sufficiently large t ≥ 1, st ∈ K \ St , where St = { x1 , . . . , xt }. The initial state s0 is not itself required to be a valid generated element. Theorem A.4 (Coding compilation). Let L = { L1 , . . . , L N } be a finite collection of infinite languages. Suppose M is an index-based learner in the unrestricted full-information model with the following property: for every target language K ∈ L and every enumeration ( xt )t∈N of K, if it denotes the index output by M after seeing ( x1 , . . . , xt ), then there exists t0 such that L i t ⪯F K
for all t ≥ t0 .
Then L admits an incremental element-based generator. Proof. Fix an encoding code : X<ω → N of finite sequences by natural numbers, and a bijection ⟨·, ·⟩ : N × N → N such that, for every fixed u ∈ N, the set {⟨u, n⟩ : n ∈ N} is unbounded. We define an incremental element-based generator whose previous output stores the entire observed prefix. Initialize with s0 := d1,⟨code(ε),1⟩ . On round t ≥ 1, suppose the previous output is st−1 . The update rule is defined arbitrarily S on previous outputs outside i∈[ N ] Ci . Along the intended run, the previous output is always a codeword. If st−1 = di,m , the disjointness of the Ci and the displayed ordering of each Ci determine a unique pair (i, m); the update rule unpairs m = ⟨u, n⟩ and decodes u to recover the previously seen prefix σt−1 = ( x1 , . . . , xt−1 ) . It then appends the new datum xt to form σt = ( x1 , . . . , xt ), runs the full-information learner on this prefix to obtain it := M (σt ), and lets nt be the least n ∈ N such that st := dit ,⟨code(σt ),n⟩ lies after both st−1 and xt in the canonical ordering. Such an nt exists because, for fixed u = code(σt ), the positions {⟨u, n⟩ : n ∈ N} are unbounded, so the corresponding subsequence of the increasing enumeration of Cit is cofinal in Cit , and Cit is cofinal in X. By construction, st again determines σt , so the process can continue inductively. Also, st ≻ st−1 and st ≻ xt for every t ≥ 1. Hence (st )t∈N is strictly increasing in the canonical order, and an induction on t shows that st ∈ / St for every t ≥ 1 , where St = { x1 , . . . , xt }. Now fix a target language K ∈ L and an enumeration ( xt )t∈N of K. By hypothesis, there is t0 such that Lit ⪯F K for all t ≥ t0 . Since L is finite, the set B :=
[
{ L i \ K : L i ⪯F K }
is finite. For every t ≥ t0 , we have st ∈ Cit ⊆ Lit ⊆ K ∪ B. Because the outputs are strictly increasing in the canonical order, they eventually lie beyond every element of B, and in particular there is
43
t∗ ≥ t0 such that st ∈ / B for all t ≥ t∗ . For those t we therefore have st ∈ K, and since also st ∈ / St , it follows that s t ∈ K \ St for all t ≥ t∗ . Thus the incremental element-based generator succeeds on K. Since K was arbitrary, the theorem follows. To summarize, Theorem A.4 shows that any full-information learner whose hypotheses are eventually almost contained in the target can be compiled into an incremental element-based generator. The compilation works because each output element encodes the full interaction history, allowing the incremental generator to simulate the full-information learner step by step.
A.3
A Positive Result for Generation
We now combine the coding compilation of Theorem A.4 with the approximate-identification theorem from Section 5 to obtain an incremental element-based generator for finite collections. This result should be interpreted with caution: it is possible only because element-based generators can encode arbitrarily large amounts of information in their last action. Thus, while the result is positive, it does not meaningfully reflect the strength of bounded-memory algorithms, and for this reason we do not explore element-based generators which have access to their last guess further. Theorem A.5. Every finite collection of infinite languages admits an incremental element-based generator. Proof. By Theorem 5.2, every finite collection of infinite languages admits an incremental learner whose hypotheses eventually differ from the target language on only finitely many elements. In particular, writing it for the learner’s output, eventually Lit ∼F K, and hence Lit ⪯F K, which is the one-sided hypothesis needed in Theorem A.4. Since any incremental learner is also a fullinformation learner, Theorem A.4 applies and yields an incremental element-based generator for the same collection.
44