Space-Efficient Language Generation in the Limit

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Space-Efficient Language Generation in the Limit

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

Space-Efficient Language Generation in the Limit Nicolas Flammarion

NICOLAS . FLAMMARION @ EPFL . CH

EPFL, Switzerland

Chirag Pabbaraju

CPABBARA @ STANFORD . EDU

Stanford University, USA

Hristo Papazov

HRISTO . PAPAZOV @ EPFL . CH

arXiv:2606.25777v1 [cs.DS] 24 Jun 2026

EPFL, Switzerland

Miltiadis Stouras

MILTIADIS . STOURAS @ EPFL . CH

EPFL, Switzerland

Ola Svensson

OLA . SVENSSON @ EPFL . CH

EPFL, Switzerland

Abstract We initiate a resource-aware theory of language generation in the limit under the minimal constraint of space efficiency. In our framework, a learner observes an adversarial positive stream from a target language K and must eventually output a hallucination-free hypothesis language L ⊆ K while omitting at most ∆ strings of K. We focus on Cs,k , the collection of languages recognized by DFAs with at most s states over an alphabet of size k, as the natural hypothesis class for memory-bounded learners. In the exponential-space regime, we prove that a learner can exactly identify the target K. Under a stricter memory budget, we characterize the strongest possible generation guarantees. In particular, we present a streaming algorithm using poly(s, k) space that converges to a hypothesis with generation gap ∆ = O(k 2s−2 ). Moreover, the learned hypothesis captures every string in K of length at least 2s − 1. We complement this result with a near-matching lower bound through a reduction from a standard communication complexity problem. Specifically, achieving generation gap ∆ ≤ k (1−ε)s requires k Ω(εs) memory. Together, these results reveal a sharp transition between polynomial-space generation and exponential-space exact identification. Keywords: Language Generation in the Limit, Finite-State Automata, Computational Efficiency

1. Introduction Large language models (LLMs) have been shown to generate novel and grammatically well-formed text even after training on exclusively positive natural-language examples (Radford et al., 2019; Brown et al., 2020; Mahowald et al., 2024). This remarkable empirical success revives a classical question from computational learning theory: What kind of language acquisition becomes possible when a learner only observes valid strings from the target language with no explicit negative feedback? Identification in the Limit. A canonical formalization of this positive-only setting comes from Gold’s work on learning in the limit. Motivated by the now-contentious1 claim from psycholinguistics that infants learn the grammar of a language solely from positive examples, Gold (1967) developed the learning-in-the-limit framework as a minimalist formalization of language learning from positive data. Gold’s model fixes (i) a representation system for languages, (ii) a target language, and (iii) an 1. Consider (Marcus, 1993) for arguments in favor of language acquisition solely from positive examples and see (Chouinard and Clark, 2003) for arguments for the presence of negative examples in parent-infant communication.

F LAMMARION PABBARAJU PAPAZOV S TOURAS S VENSSON

infinite stream that eventually lists every string in the target language. After each received valid string from this language presentation, a learner outputs a hypothesis language. Gold defined a language family as identifiable in the limit when a learner eventually stabilizes on a hypothesis that matches the ground-truth exactly, regardless of the target language and the presentation order. Unfortunately, under this learning criterion, Gold (1967) proved that only highly restricted2 language collections are learnable. In particular, one cannot even learn the class of regular languages. These impossibility results largely redirected mainstream learning theory toward distributional, sample-complexity, and efficiency guarantees, crystallized in PAC learning (Valiant, 1984; Kearns and Vazirani, 1994). Generation in the Limit. Only recently, Kleinberg and Mullainathan (2024) revitalized Gold’s positive presentation framework by proposing a different language-acquisition criterion that fits language modeling more closely. Specifically, the learner still receives an arbitrary enumeration of the target language, but success no longer requires eventual equality between hypothesis and target. Instead, after some finite time, the learner must begin to generate infinitely many unseen strings from the target language. Put informally, sufficient exposure to positive data should make hallucinations disappear while preserving an infinite learned subset of the target language. This shift replaces identification with generation by relaxing the objective from equality to containment. Surprisingly, the relaxed objective substantially alters the theory: Now, under oracle access to membership queries for the enumerated language family, generation in the limit becomes achievable for every countable collection of languages.3 Kleinberg and Mullainathan (2024)’s positive result has since inspired a growing line of follow-up work examining different aspects of generation/learning in the limit (Kalavasis et al., 2024; Li et al., 2024; Charikar and Pabbaraju, 2024; Papazov and Flammarion, 2025; Charikar and Pabbaraju, 2025; Peale et al., 2025; Raman and Raman, 2025; Hanneke et al., 2025; Charikar et al., 2025). Interestingly, the current generation-in-the-limit literature largely treats computation as free. As a result, generation guarantees rest on models that place no bounds on computation and, in particular, allow unbounded memory. Such assumptions diverge from practice, where human learners operate without external storage and language models train and run under explicit memory budgets. Space-Efficient Generation. Motivated by this explanatory gap, our paper initiates a resourceaware study of generation in the limit by imposing the minimal computational restriction of space efficiency. Under our proposed framework, (i) the learner receives a stream of positive examples through an online interface, (ii) processes each target string symbol-by-symbol while operating within a strict memory budget, and (iii) after each processed example, outputs a hypothesis representation that must eventually generate a subset of the target language. Now, the requirement of bounded memory implies that our learning algorithms can only occupy finitely many internal configurations. Therefore, membership verification for the streamed examples can only range over regular languages, and only over a finite set of such languages. Accordingly, space-efficient generation only admits a meaningful formulation over finite collections of regular languages. Despite this restriction, regularlanguage generation remains practically significant. Specifically, in Appendix A, we argue that the collection of communicative languages, which arise from the interaction of space-bounded agents such as humans (Miller and Chomsky, 1963), forms a strict subset of regular languages. Concurrently and independently, Kleinberg et al. (2026) also study generation in the limit under bounded-memory restrictions. Their results are incomparable to ours: they consider broader language collections with coarser memory models, where the learner can only retain a limited window or 2. See (Angluin, 1980, Theorem 1) for a precise characterization of identifiable collections in the limit. 3. Of course, if we insist on computable membership queries, then the scope of the generatable collections decreases.

S PACE -E FFICIENT L ANGUAGE G ENERATION IN THE L IMIT

buffer of past examples. In contrast, we impose an explicit bit-space budget on the learners and focus on regular languages (Cs,k ). This lets us prove quantitative space–breadth tradeoffs, including tight bounds on the generation gap achievable with polynomial space. Overview and Contributions. The regularity arguments above justify restricting attention to regular hypothesis spaces parameterized by automaton complexity. For a fixed alphabet Σ with |Σ| = k and a state bound s, let Cs,k denote the collection of languages recognizable by deterministic finite automata (DFAs) over Σ with at most s states. The remainder of the paper characterizes space-efficient generation within Cs,k . Upper bounds give explicit streaming learners operating in poly(s, k) space, while lower bounds show that stronger generation guarantees require exponential memory. These results expose a sharp tradeoff between memory and generative breadth, yielding a resource-sensitive theory of generation in the limit. Roadmap. Section 2 formalizes the space-efficient generation model and describes our main results. Section 3 presents a space-efficient generation algorithm for Cs,k . Section 4 proves matching lower bounds via communication complexity reductions. Section 5 concludes with implications for resource-bounded language acquisition and open directions.

2. Space-Efficiency Framework and Main Results As described in Section 1, we study the problem of space-efficient generation in the limit where an adversary enumerates w1 , w2 , w3 , . . . and presents a target language K ∈ Σ∗ in a streaming fashion. Each string wt arrives one symbol at a time, with a designated delimiter separating consecutive strings. After each symbol, the learning algorithm A performs computation under a polynomial space budget, and after each processed string wt ∈ K, A outputs a hypothesis representation of a regular language. Concretely, for the rest of the paper, we fix an alphabet Σ of size k and let Cs,k denote the collection of all regular languages over Σ recognizable by DFAs of at most s states. As a quick reminder, we recall the textbook definition of a DFA (Sipser, 1996; Hopcroft et al., 2001). Definition 1 (Deterministic Finite-State Automaton) A DFA A over the finite alphabet Σ is a 5-tuple A = (Q, Σ, δ, q0 , F ), where Q is a finite set of states, δ : Q × Σ → Q is a transition function, q0 ∈ Q is the initial state, and F ⊆ Q is a set of accepting (final) states. We extend the transition function δ to act on Σ∗ by setting δ(q, ε) = q (where ε is the empty string) and recursively defining δ(q, σw) := δ(δ(q, σ), w), for every q ∈ Q, σ ∈ Σ and w ∈ Σ∗ . We use the notation L(A) to denote the regular language accepted by the DFA A, i.e., L(A) = {w ∈ Σ∗ : δ(q0 , w) ∈ F }, and we define the size of the DFA A as |A| = |Q|. We now state our main definition of space-efficient language generation in the limit. Definition 2 (Space-Efficient Generation in the Limit) A space-efficient algorithm A generates in the limit from Cs,k with a generation gap ∆A (s, k) if (i) A uses at most poly(s, k) bits of working memory, and (ii) for any target regular language K ∈ Cs,k and any surjective enumeration w : N↠K presented to A in a streaming fashion, there exists a finite time t⋆ such that for all t ≥ t⋆ , A outputs a representation of a DFA A(t)4 satisfying L(A(t)) ⊆ K 5 and |K \ L(A(t))| ≤ ∆A (s, k). 4. We use A(t) as a shorthand for A(w1 , . . . , wt ). 5. One can also formulate the objective without the hard no-hallucination requirement by asking directly for a bounded symmetric difference |L(A(t))△K| ≤ ∆A (s, k). The upper and lower bounds in this paper remain the same under that relaxed formulation as we show in Sections 3 and 4.

F LAMMARION PABBARAJU PAPAZOV S TOURAS S VENSSON

The literature refers to the requirement of outputting a language representation satisfying L(A(t)) ⊆ K as index-based generation in the limit (Kleinberg and Wei, 2025). While index-based generation with an unbounded generation gap admits a trivial solution, for example by repeatedly outputting the singleton language w for some short string w ∈ K, such a strategy fails to approximate K in any rich or informative sense. In particular, constructing an infinite sublanguage of K already poses a nontrivial challenge. This paper studies a substantially stronger objective: generation in the limit under a bounded generation gap, where the output language differs from K on only finitely many strings, thereby capturing almost the entire target language. Without an a priori bound s on the size of a DFA recognizing the target language, boundedgap generation in the limit remains impossible, even without memory constraints. More formally, Kalavasis et al. (2024, Theorem 3.10) show that any collection admitting bounded-gap6 generation in the limit must satisfy the so-called Weak Angluin’s Condition. In particular, regular languages violate the weak Angluin’s condition. Consequently, bounded-gap generation in the limit fails over the full class of regular languages (without any a priori state bound), even with unlimited memory. Interestingly, Angluin (1980) proved that any finite collection of languages allows identification in the limit. Hence, without the polynomial-space requirement, we can completely remove the generation gap and identify Cs,k in the limit. We describe such an algorithm in Section 3; here, we simply note that identification crucially relies on using exponential space. Then, how does the picture change with polynomial space constraints? Perhaps surprisingly, our first result shows that there exists a space-efficient algorithm that generates from Cs,k in the limit with a bounded generation gap. Theorem 3 (Space-Efficient Generation in the Limit) There exists a space-efficient learning algorithm A that generates in the limit from Cs,k with a generation gap ∆A (s, k) ≤ O(k 2s−2 ). In fact, the algorithm satisfies a stronger guarantee: The output language omits only target strings of length at most 2s − 2. At a high-level, our algorithm traverses Cs,k according to a predefined topological order and outputs the first language not proven inconsistent with the most recently observed input string. At the next input, the learner continues traversing Cs,k starting from the previously outputted language. The topological order ensures that the algorithm converges to a language with a finite symmetric difference with the target language. We make the traversal spaceefficient by using a recursion technique inspired by Savitch’s famous theorem in complexity theory (Savitch, 1970). Finally, to achieve generation in the limit while minimizing the generation gap, we invoke results from the automata-minimization literature (Gawrychowski et al., 2011) that bound the size of the finite symmetric difference between the learner’s hypothesis and the target. Our space-efficient algorithm nonetheless incurs a nonzero generation gap of O(k 2s−2 ). This bound raises a natural question: Does polynomial-space learning permit a zero generation gap, or, equivalently, identification in the limit over Cs,k ? The next theorem rules out this possibility. In fact, we prove something much stronger: Any learner that operates with sub-exponential space must incur an exponential generation gap. Theorem 4 (Space–Breadth Tradeoff) For any ε > 0, any algorithm A generating in the limit from Cs,k with a generation gap ∆A (s, k) ≤ k (1−ε)s must use k Ω(εs) memory bits. Moreover, any algorithm A achieving the relaxed condition |L(A(t⋆ ))△K| ≤ k (1−ε)s must still use k Ω(εs) bits. Most existing lower bounds in the identification/generation-in-the-limit literature involve some form of a diagonalization argument: The adversary constructs an enumeration of a problematic language 6. Kalavasis et al. (2024) refer to this notion as generation with “approximate breadth”.

S PACE -E FFICIENT L ANGUAGE G ENERATION IN THE L IMIT

by endlessly switching back-and-forth between enumerating different languages and causing the algorithm to fail at the objective at each switch in the process. These diagonalization arguments crucially rely on a special nesting structure present among the languages in the collection. In contrast, our lower bound follows from a reduction to the Index problem from communication complexity: a standard route to space lower bounds for streaming algorithms. The Index problem defines a one-way communication game between Alice and Bob: Alice receives a length-n vector x ∈ [k]n , Bob receives an index i ∈ {1, . . . , n}, and Bob must output xi after receiving a single message from Alice. A standard pigeonhole-principle bound implies that any protocol deterministically solving Index requires communication of n log2 k bits from Alice to Bob7 . To prove the streaming lower bound, we show that a space-efficient learner using only poly(s, k) bits of memory and achieving sufficiently small generation gap induces a one-way protocol for Index with communication strictly below n log2 k bits, yielding a contradiction. The lower bound also shows that the generation gap achieved by the algorithm matches the optimal rate up to constant factors in the exponent. Together, Theorem 3 and Theorem 4 establish that the classical separation between identification and generation in the limit persists under polynomial space bounds. This separation vanishes once the space budget increases from poly(s, k) to exp(s, k). Under exp(s, k) space, an algorithm can identify Cs,k in the limit. Space-bounded generation in the limit therefore exhibits a sharp phase transition: Sub-exponential space forces an exponential generation gap, while exponential space permits exact identification.

3. Upper Bounds In this section, we derive our space-efficient algorithm A, which, for all sufficiently large t, outputs a DFA A(t) that satisfies L(A(t)) ⊆ K, where K denotes the unknown target language assumed to require a DFA of size at most s for recognition. Furthermore, A(t) satisfies that |K \ L(A(t))| ≤ O(k 2s−2 ). In particular, L(A(t)) contains all strings in K that have length at least 2s − 1. Before describing our learning procedure, we first recall Angluin’s algorithm for identification in the limit to illustrate the challenges for achieving space-efficiency. Recalling Angluin’s identification algorithm for finite collections. Let us arbitrarily enumerate the finitely many DFAs of size at most s as A1 , A2 , . . . , AN .8 Here, N ≤ 2s · sks (2s ways of selecting an accepting subset of at most s states, followed by specifying the transition on each symbol for every state). By assumption, there exists some index i⋆ for which L(Ai⋆ ) = K. As established by Angluin (1980), all finite collections are identifiable in the limit (without space constraints). The algorithm operates as follows: It first topologically sorts the DFAs A1 , A2 , . . . , AN according to the strict partial order ≺1 induced by strict inclusion: A ≺1 A′ ⇐⇒ L(A) ⊂ L(A′ ).

(1)

Namely, if L(A) is a strict subset of L(A′ ), then A appears before A′ in the topological sort.9 Indeed, since the collection is finite, a topological sort corresponding to any partial order exists, and can be constructed by a standard depth-first search over a directed graph whose nodes correspond to 7. Related strong lower bounds, with quantitatively similar rates, also hold for randomized one-way communication protocols; see, for example, Bar-Yossef et al. (2002); Jayram et al. (2008). 8. Our enumeration will contain many isomorphic DFAs recognizing the same language. This redundancy is harmless. We only require that each regular language in Cs,k receives some representation in the enumeration. 9. It can be readily verified that the relation in (1) is a strict partial order: It is irreflexive, asymmetric and transitive.

F LAMMARION PABBARAJU PAPAZOV S TOURAS S VENSSON

the DFAs Ai . So, abusing notation slightly, suppose that the DFAs A1 , . . . , AN are already ordered according to the topological sort induced by ≺1 . At time step t, after having seen input w1 , . . . , wt , the algorithm outputs the DFA Ai(t) , where i(t) is the smallest index of a DFA that accepts each of w1 , . . . , wt 10 . Concretely, for every j < i(t), it holds that {w1 , . . . , wt } ⊈ L(Aj ). Let i⋆ be the index of the DFA that recognizes K. Note that {w1 , . . . , wt } ⊆ L(Ai⋆ ) for every t. Therefore, i(t) ≤ i⋆ for every t; since i(t) is non-decreasing in t, i(t) must eventually converge. Furthermore, the DFA Ai(t) at which the algorithm converges must satisfy L(Ai⋆ ) ⊆ L(Ai(t) ), since otherwise, there exists some w ∈ L(Ai⋆ ) \ L(Ai(t) ), which is guaranteed to show up eventually in the input, causing Ai(t) to be invalidated. Finally, since i(t) ≤ i⋆ , and L(Ai⋆ ) ⊆ L(Ai(t) ), it must necessarily be the case that L(Ai⋆ ) = L(Ai(t) ), by the definition of ≺1 . An important feature of the algorithm above is that it keeps track of the entire history of inputs seen so far at every time step. This is not feasible in our framework of space efficiency where we insist on maintaining only poly(s, k) bits of working memory across time steps. As we shall see later, it is actually sufficient to remember only those input strings that have length at most O(s) for exact identification; however, even this requires exp(s, k) memory. There is also the separate issue of traversing the DFAs A1 , . . . , AN in an order topologically sorted according to ≺1 in a space-efficient manner. We address this latter issue first. For any automata C, D, checking C ≺1 D amounts to testing L(C) \ L(D) = ∅ and L(D) \ L(C) ̸= ∅. Both conditions can be checked via the standard product constructions (see Appendix B) of DFAs (on at most s2 states) that recognize L(C) \ L(D) and L(D) \ L(C), which can be done in poly(s, k) time (and hence also space). Thereafter, testing whether the product automaton recognizes an empty language amounts to checking if there exists a directed path beginning from the initial state and reaching an accepting state, which can again be done in poly(s, k) time (and hence space). Thus, one can verify C ≺1 D in poly(s, k) time. However, implementing the full topological sort of the exponentially many DFAs using only polynomial space requires further attention. 3.1. A space-efficient topological sort Recall that the standard algorithm for topological sorting performs a depth-first search over a directed graph whose nodes consists of the DFAs in the collection Cs,k . In the worst case, this approach requires maintaining a history of exponentially many already-enumerated DFAs, which clashes with our memory constraints. To remedy this, we consider a Rank Iteration Strategy for enumerating Cs,k in a space-efficient manner. Concretely, given an arbitrary strict partial order ≺, for any DFA A in the collection Cs,k = {A1 , . . . , AN }, define its rank with respect to ≺, denoted rank(A, ≺), as follows: rank(A, ≺) := max{ℓ : ∃Ai1 , . . . , Aiℓ ∈ Cs,k such that Ai1 ≺ · · · ≺ Aiℓ ≺ A}.

(2)

Here, rank(A, ≺) = 0 if there does not exist Ai1 ∈ Cs,k satisfying Ai1 ≺ A. The rank of any A ∈ Cs,k can range from 0 to N − 1. The following elementary observation relates rank to the partial order ≺: Observation 5 (Relating rank to ≺) If A′ ≺ A, then rank(A, ≺) ≥ rank(A′ , ≺) + 1. This observation implies that, in order to traverse the DFAs topologically sorted according to ≺, it suffices to iterate through them in increasing order of their rank. This gives rise to the Rank Iteration 10. Such an i(t) always exists, since the target language K is recognized by some DFA in the collection.

S PACE -E FFICIENT L ANGUAGE G ENERATION IN THE L IMIT

Algorithm 1 Rank Iteration Strategy (recursive doubling for rank) Input: DFA size s, strict partial order ≺, Input: DFA D, strict partial order ≺ position j ≤ N Output: rank(D, ≺) as in (2) Output: DFA Aj that is j th in a topological sorting of Procedure computeRank(D, ≺): all DFAs of size ≤ s under ≺ for ℓ = N − 1, N − 2, . . . , 1 do Let B1 , . . . , BN be any enumeration of all Procedure rankIteration(s, ≺, j): Initialize count ← 0 DFAs of size at most s for r = 0, . . . , N − 1 do for i = 1, . . . , N do Let B1 , . . . , BN be any enumeration of all if path(Bi , D, ℓ, ≺) then return ℓ; DFAs of size at most s return 0 for i = 1, . . . , N do if computeRank(Bi , ≺) = r then count ← count + 1 if count = j then return Bi ; Input: DFAs C, D, path length ℓ ≥ 1, strict partial order ≺ Output: True iff there exists a ≺-chain of length ℓ from C to D Procedure path(C, D, ℓ, ≺): if ℓ = 1 and C ≺ D then return True; Let B1 , . . . , BN be any enumeration of all DFAs of size at most s; let m ← ⌈ℓ/2⌉ for i = 1, . . . , N do if path(C, Bi , m, ≺) and path(Bi , D, ℓ − m, ≺) then return True return False

Strategy encapsulated in Algorithm 1. The strategy processes DFAs in increasing order of their ranks. The rank of each DFA is computed space-efficiently using a technique inspired by the “middle-first search” approach used in Savitch’s theorem (Savitch, 1970). Savitch’s theorem gives a space-efficient algorithm for checking if two nodes are connected by a path of length ℓ in a directed graph, by recursively checking for the existence of a “middle node” that lies at distance ℓ/2 from each of the nodes. The crucial point is that these recursive checks can reuse space. A similar idea applies for our purpose of computing rank, where a path of length ℓ between two DFAs C and D corresponds to a chain C ≺ B1 ≺ · · · ≺ Bℓ−1 ≺ D in the partial order. In this case, if the relation ≺ can be checked using polynomial space, then the entire Rank Iteration Strategy uses only polynomial space. This leads to the following proposition, whose proof is given in Appendix C. Proposition 6 (Rank Iteration Space Complexity) rankIteration(s, ≺, j) given in Algorithm 1 requires poly(s, k) bits of memory, provided one can check “C ≺ D?” using poly(s, k) space for any two DFAs C and D with at most s states. 3.2. A natural space-efficient modification and the main challenge We now tackle the issue of storing input history. The subroutine SpaceEfficientTraversal(≺) below modifies Angluin’s algorithm to avoid storing the full input history {w1 , . . . , wt } up to time t. However, this modification will necessitate changing the partial order ≺1 considered by Angluin’s algorithm, as the proceeding analysis reveals.

F LAMMARION PABBARAJU PAPAZOV S TOURAS S VENSSON

SpaceEfficientTraversal(≺): Let A1 , . . . , AN denote all the DFAs of size at most s topologically sorted according to ≺. The previous analysis shows that we can traverse the DFAs in this order space-efficiently. Let i(0) = 1. At any time step t ≥ 1, the algorithm first initializes i(t) = i(t − 1). After receiving the streamed input string wt , the algorithm checks if wt ∈ L(Ai(t) ), which only requires tracing wt through the DFA Ai(t) , and hence requires constant memory. Here, Ai(t) is retrieved by invoking rankIteration(s, ≺, i(t)). If this check does not pass, the algorithm increments i(t) ← i(t) + 1 and outputs the DFA Ai(t) . Note that the outputted Ai(t) might not accept wt . Indeed, requiring the algorithm to retest membership of wt in L(Ai(t) ) could necessitate remembering a prohibitively long string wt .

We can instantiate SpaceEfficientTraversal with the partial order ≺1 , and by the preceding discussion, this procedure uses only poly(s, k) memory. The remaining question is whether it identifies K in the limit; i.e., whether it eventually outputs Ai(t) with L(Ai(t) ) = K for all t ≥ t⋆ . Recall that there exists an index i⋆ such that L(Ai⋆ ) = K. Now, if the algorithm ever arrives at index i⋆ , it never proceeds beyond it, since every wt ∈ K. Thus, in the limit, the algorithm converges to some index i(t) ≤ i⋆ . Then, it must be the case that |K \ L(Ai(t) )| < ∞; otherwise, we are guaranteed to see some string w ∈ K \ L(Ai(t) ) in the future, contradicting convergence at i(t). If i(t) = i⋆ , then we identify K. Otherwise, i(t) < i⋆ . We already argued above that |K \ L(Ai(t) )| < ∞. If |K \ L(Ai(t) )| = 0, then K ⊆ L(Ai(t) ). In that case, we are guaranteed that K = L(Ai(t) ). Indeed, K ⊂ L(Ai(t) ) would contradict the definition of ≺1 . So, we achieve the desired objective in this case as well. The only case that remains is when i(t) < i⋆ and |K \ L(Ai(t) )| < ∞ ̸= 0. Unfortunately, in this case, it is possible that L(Ai(t) ) \ K is non-empty as well. In fact, L(Ai(t) ) could even contain infinitely many strings outside K. So, in this case, not only do we fail to achieve the desired objective of identification, but the language that we converge to may contain infinitely many hallucinations. This unwanted case is a direct consequence of the memory constraint. Indeed, when K \ L(Ai(t) ) is nonempty, and if we were to store the entire history of inputs at every time step (as Angluin’s algorithm does), the history would eventually contain some string in K \ L(Ai(t) ), causing us to proceed beyond Ai(t) . However, consider the possibility where K \ L(Ai(t) ) has very few strings which all appeared in the distant past without showing up again. Since we do not store past inputs in memory, and only make our decisions based on the most recent string, we never see any evidence again that would cause us to move beyond Ai(t) . As a final remark, note that SpaceEfficientTraversal(≺1 ) does succeed with exact identification under the additional assumption that every string in K appears infinitely often in the input stream. In this setting, any missing string w ∈ K \ L(Ai(t) ) would eventually reappear and invalidate the currently wrong hypothesis. 3.3. A slightly more robust partial order The analysis above isolates the main limitation of the partial order ≺1 : If there exist two DFAs A and A′ such that |L(A) \ L(A′ )| < ∞ but |L(A′ ) \ L(A)| is huge, then topologically sorting according to ≺1 allows A′ to be placed before A. Consequently, if L(A) is the target language, we might 8

S PACE -E FFICIENT L ANGUAGE G ENERATION IN THE L IMIT

(3)

If this relation were a strict partial order, we could topologically sort the DFAs according to ≺2 and run the space-efficient algorithm described above on this ordering. As it turns out, the relation is indeed a strict partial order; the elementary proof appears in Appendix C. Proposition 7 (≺2 Strict Partial Order)

The relation ≺2 defined in (3) is a strict partial order.

Next, we observe that checking A ≺2 A′ can also be done with poly(s, k) space. For this, we once again construct the product automata that recognize L(A) \ L(A′ ) and L(A′ ) \ L(A), respectively (each of these have at most s2 states). Then, we use the fact that a regular language is infinite if and only if an automaton recognizing it has a cycle that can be reached from the initial state, and can then go on to reach an accepting state. We can check this using standard depth-first search on the directed graph underlying the automaton. For our purposes, this requires poly(s, k) time, and hence space. Finally, if both the languages L(A) \ L(A′ ) and L(A′ ) \ L(A) are determined to be finite, we require comparing their sizes. In this case, we observe that both languages must contain strings of length at most s2 . Otherwise, if either contained a string of length larger than s2 , this string would induce a cycle while traversing its product automaton, which could be pumped infinitely. So, the size of both languages can be computed exactly by iterating over all strings of length at most s2 , and checking membership in the automaton. This step can also be executed in poly(s, k) space. Using all the ingredients established so far, we can then show that SpaceEfficientTraversal, invoked with the partial order ≺2 , converges to a DFA that has a finite symmetric difference with the target language K — this notion has been referred to as hyper-equivalence in the automata literature (Badr et al., 2009; Gawrychowski et al., 2011; Maletti and Quernheim, 2011). Proposition 8 (≺2 Converges to Finite △) SpaceEfficientTraversal(≺2 ) converges to an index i(t) satisfying |L(Ai(t) )△K| < ∞, while using only poly(s, k) memory. Furthermore, if every string in K shows up infinitely often in the input stream, then L(Ai(t) ) = K in the limit. Proof Since it is guaranteed that K = L(Ai⋆ ) for some index i⋆ , the algorithm never proceeds beyond i⋆ , and hence, i(t) ≤ i⋆ in the limit. Furthermore, |K \ L(Ai(t) )| < ∞, since otherwise, the algorithm eventually sees a string that causes it to move past i(t). So, either i(t) = i⋆ , or i(t) < i⋆ . In the latter case, it must hold that |L(Ai(t) ) \ K| ≤ |K \ L(Ai(t) )| < ∞, since we topologically sorted according to ≺2 . Either way, |L(Ai(t) )△K| < ∞ holds. Since we argued above that checking ≺2 uses poly(s, k) space, by Proposition 6, the entire algorithm uses only poly(s, k) space. Finally, if every string in K shows up in the input infinitely often, then the algorithm converges to an i(t) satisfying L(Ai(t) ) ⊇ L(Ai⋆ ). Otherwise, a string in L(Ai⋆ ) \ L(Ai(t) ) is guaranteed to show up in the input, causing the algorithm to move beyond i(t). Now, suppose that L(Ai(t) ) ⊃ L(Ai⋆ ). Then, we have that |L(Ai⋆ ) \ L(Ai(t) )| = 0 < |L(Ai(t) ) \ L(Ai⋆ )|, which contradicts sorting according to ≺2 since i(t) < i⋆ . Thus, L(Ai(t) ) = L(Ai⋆ ) = K.

F LAMMARION PABBARAJU PAPAZOV S TOURAS S VENSSON

3.4. The final algorithm We now have all the ingredients necessary to state our final algorithm. By Proposition 8, we know that SpaceEfficientTraversal(≺2 ) converges to a DFA Ai(t) that satisfies |L(Ai(t) )△K| < ∞. If we can now output a DFA that accepts a large subset of L(Ai(t) ) but avoids the strings in the finite symmetric difference L(Ai(t) )△K, our objective of language generation with finite gap would be accomplished. Towards this, observe that L(Ai(t) )△K is yet another regular language. Moreover, the product DFA C recognizing L(Ai(t) )△K has at most s2 states. Hence, given that this language is finite, it must not include any string of length ≥ s2 ; otherwise, this string would visit some state in the DFA C twice before reaching an accepting state, yielding a cycle, which can be pumped arbitrarily often to generate infinitely many accepted strings. In fact, we can prove a stronger bound, using a prior result by Gawrychowski et al. (2011), which shows that L(Ai(t) )△K can only contain strings of length at most 2s − 2. The proof of this result appears in Appendix C. Lemma 9 (Symmetric Difference Contains Length-O(s) Strings) Let A = (QA , Σ, δA , q0A , FA ) and B = (QB , Σ, δB , q0B , FB ) denote DFAs having at most s states over a common alphabet Σ, such that |L(A)△L(B)| < ∞. Then, for any string w ∈ Σ∗ , if |w| ≥ 2s − 1, then w ∈ / L(A)△L(B). Thus, if we output a DFA A′ that only accepts strings of length at least 2s − 1 in L(Ai(t) ), we ensure that L(A′ ) ⊆ L(Ai(t) ) ∩ K ⊆ K as required. This leads to the following theorem, whose precise proof is given in Appendix C. Theorem 10 (Space-Efficient Language Generation) Let K denote the unknown target language recognized by a DFA of size at most s. There exists an algorithm A which, for all sufficiently large t, outputs a DFA A′ = A(t) that satisfies L(A′ ) ⊆ K, and uses only poly(s, k) space. Furthermore, the algorithm misses at most |K \ L(A′ )| ≤ O(k 2s−2 ) target strings. Let us also remark here that by the conclusion of Lemma 9, our learning algorithm A is guaranteed to output an automaton A′ such that every string in K \ L(A′ ) has length at most 2s − 2. Thus, if the algorithm additionally keeps track of all the inputs of length at most 2s − 2 (which requires exp(s, k) space), A can output a DFA that exactly recognizes K. In other words, with exp(s, k) memory, we can identify Cs,k in the limit. Finally, observe that our algorithm above ensures no hallucinations, but misses out on a finite amount of breadth (namely O(k 2s−2 ) strings) in the limit. Instead, we could have the algorithm output a different product DFA A′ (again on ≤ 2s2 states), which accepts L(Ai(t) )∪{w ∈ Σ∗ : |w| ≤ 2s − 2}. This would ensure full breadth (i.e., L(A′ ) ⊇ K), but a finite amount of hallucinations (again O(k 2s−2 ) strings). We thus have to necessarily incur a misspecification cost on O(k 2s−2 ) strings, either in hallucinations, or breadth. Our next result shows that this compromise is indeed unavoidable.

4. Lower Bounds In the previous section, we showed that polynomial space suffices to generate in the limit from Cs,k with a generation gap of O(k 2s−2 ). A natural question is whether this loss is merely an artifact of our algorithm, or whether it is fundamentally unavoidable under space constraints. In this section, we prove that the latter is actually the case. 10

S PACE -E FFICIENT L ANGUAGE G ENERATION IN THE L IMIT

Our result establishes that any algorithm that operates with sub-exponential memory must incur an exponential generation gap. Moreover, the same lower bound holds under the relaxed symmetric-difference objective from Definition 2, where hallucinations and missed strings are counted together through |L(A(t))△K|. Thus, hallucinations cannot be traded for substantially smaller missed breadth: Any sub-exponential-memory learner still incurs an exponential total error. This demonstrates a sharp transition between what is achievable with polynomial space versus exponential space: Exponential memory permits full identification, whereas any polynomial-space learner is fundamentally forced to miss an exponential number of strings. Our proof departs from the diagonalization-based arguments commonly used in the identificationin-the-limit literature. Instead, we adopt a communication-complexity perspective and reduce from the INDEXn problem. At a high level, we show that a space-efficient learner with a sufficiently small generation gap could be used to derive an efficient communication protocol for the INDEXn problem, which contradicts known lower bounds. We begin by recalling the relevant communication problem and its standard lower bound, and then we present the reduction that translates a small generation gap into an efficient Index protocol. Lemma 11 (Communication Lower Bound for INDEXn , Kushilevitz (1997)) Let INDEXn be the one-way communication problem where Alice is given a vector x ∈ [k]n , Bob is given an index i ∈ [n], and Bob must output xi after a single message from Alice. Any deterministic protocol for INDEXn requires at least n log2 k bits of communication. The proof of Lemma 11 is a standard pigeonhole argument; for completeness we include it in Appendix D. The next lemma connects INDEXn to generation in the limit over Cs, k, yielding a generation-gap lower bound in terms of the learner’s space. Lemma 12 Any algorithm A that uses m(s) bits of space and generates in the limit from Cs,k must incur a generation gap of ∆A (s, k) ≥ k s−2 logk ((m(s)+1)/ log2 k)−3 . Proof Fix s and let m(s) be the number of bits that algorithm A uses. As we discussed above our proof goes through the INDEXn problem. We will set n, i.e. the input size of INDEXn , later in the proof as a function of m(s) and k. Alphabet and building blocks. Let Σ := [k] be an alphabet of size k. Throughout the proof we use [k] = {0, 1, . . . , k − 1}. We define U to be the set of all strings that start with a 1 and continue with some finite number of symbols from Σ. We use the first, say p, symbols after 1 to encode a pair (i, q) for all i ∈ [n] and all q ∈ Σ, and we partition the universe U into subsets based on these p symbols. Then, every string will continue with some free symbols, say ℓ of them, which means that each of the subsets corresponding to a pair (i, q) has k ℓ strings. Since there are kn different pairs (i, q) and we are encoding in base-k, we need p := 1 + logk n symbols to encode them. Formally, for each j ∈ {0, 1, . . . , kn − 1}, let enck (j) ∈ Σp denote the base-k encoding of j with length p (allowing leading zeros). We define the languages L0 , . . . , Lkn−1 , which partition U , as Lj := {1 ◦ enck (j) ◦ u | u ∈ Σℓ }. Every language above has size k ℓ , as they have exactly one string for every member of Σℓ . We create a bijective mapping, map : [n] × [k] → [kn], that maps every combination of a dimension i ∈ [n] and symbol q ∈ [k] to a unique language in the above partition. Any such mapping can work for our reduction, for simplicity let map(i, q) := i · k + q. 11

F LAMMARION PABBARAJU PAPAZOV S TOURAS S VENSSON

Furthermore, for every i ∈ [n] and every q ∈ [k] we define the language Base(i, q) to contain all above partitions of U except for Lmap(i,q) . For technical reasons that will become clear later, we also make Base(i, q) include an infinite component, namely all strings that start with a 0. Formally, Base(i, q) := {0 ◦ u | u ∈ Σ∗ } ∪ {1 ◦ u | u ∈ Σp+ℓ } \ Lmap(i,q) . Notice that all partitions of U , i.e. L0 , . . . , Lkn−1 , can be recognized by a DFA with at most p + ℓ + 2 states, which simply recognizes the encoding bits and then counts ℓ more characters. Also, for each language Base(i, q), we can construct a DFA that recognizes it as follows: • If the first symbol is 0, transition to an accepting state that self-loops on all symbols in Σ (this branch accepts {0 ◦ u | u ∈ Σ∗ }). • If the first symbol is 1, the DFA needs to accept exactly U \ Lmap(i,q) . Equivalently, among strings of length 1 + p + ℓ that start with 1, it rejects exactly those whose next p symbols encode the number map(i, q), i.e. enck (map(i, q)). This can easily be done by 2 chains of length p that track whether or not the sequence encodes the target number. After this part, the chain that recognized this sequence leads to a rejecting state, while the chain that did not recognize the sequence reads ℓ more symbols and accepts. In Appendix D, we give a figure (Figure 1) that shows the above construction. Such a DFA uses at most 2p + ℓ + 5 states. We now set s := 2p + ℓ + 5 so that all above languages, i.e. all Lmap(i,q) and Base(i, q) for i ∈ [n] and q ∈ Σ, are recognized by DFAs of size at most s. Reduction from INDEXn . We now build a deterministic one-way protocol for INDEXn using algorithm A. As a reminder, Alice receives x = (x0 , x1 , . . . , xn−1 ) ∈ Σn , while Bob receives i ∈ [n] and must output xi . Alice simulates A on a finite input stream consisting of all the strings in the languages Lmap(j,q) for every coordinate j ∈ [n] and every symbol q ̸= xj . Conceptually, the only partitions of U that are not fed to the algorithm are exactly the combinations (j, xj ) of Alice’s input. Formally, she feeds A the set [ [ SA = Lmap(j,q) . j∈[n] q∈Σ\{xj }

Let σ be the internal memory state of A after reading this prefix. Alice sends the state σ to Bob, which by definition is at most m(s) bits. Bob resumes the execution of A from state σ and continues by feeding it all the strings in the languages Lmap(j,q) for j ̸= i, i.e., the set SB =

[ [

Lmap(j,q) .

j∈[n], q∈Σ j̸=i

Notice that at this point, the learner A has seen all partitions of U except for the one corresponding to (i, xi ). After feeding these strings, Bob continues running the algorithm A and gives it strings from {0 ◦ u | u ∈ Σ∗ }, via some surjective enumeration. This part is simply done so that the algorithm A can keep running until it converges to an answer. Consider now the union of the strings presented to A, i.e. SA ∪ SB ∪ {0 ◦ u | u ∈ Σ∗ }. For all j ̸= i, Bob has given A all the strings in the languages Lmap(j,q) . Furthermore, for the index j = i, Alice has given A all the strings in the languages Lmap(i,q) for all q ̸= xi . Thus, the algorithm has seen all languages Lmap(j,q) except for Lmap(i,xi ) . Formally, the stream is a surjective enumeration of SA ∪ SB ∪ {0 ◦ u | u ∈ Σ∗ } = {0 ◦ u | u ∈ Σ∗ } ∪ {1 ◦ u | u ∈ Σp+ℓ } \ Lmap(i,xi ) = Base(i, xi ). 12

S PACE -E FFICIENT L ANGUAGE G ENERATION IN THE L IMIT

Decoding xi from algorithm A. By the definition of generation in the limit, with gap ∆A (s, k), applied to L∗ = Base(i, xi ), the limiting output of A, let it be H, satisfies L(H) ⊆ Base(i, xi )

and

Base(i, xi ) \ L(H) ≤ ∆A (s, k).

Let’s assume at this point that the generation gap of the learner A is ∆A (s, k) < k ℓ . Then, for any q ̸= xi , if L(H) ∩ Lmap(i,q) = ∅, then A would miss all k ℓ strings in Lmap(i,q) ⊆ Base(i, xi ), which would mean that its generation gap is at least |Base(i, xi )\L(H)| ≥ k ℓ , contradicting our assumption. Therefore, for every q ̸= xi we must have L(H) ∩ Lmap(i,q) ̸= ∅. On the other hand, Lmap(i,xi ) is disjoint from Base(i, xi ), and since L(H) ⊆ Base(i, xi ), it holds that L(H) ∩ Lmap(i,xi ) = ∅. As a result, xi is the unique symbol q ∈ Σ such that L(H) ∩ Lmap(i,q) = ∅. Bob can, thus, determine xi by testing the emptiness of the intersection of L(H) with the languages Lmap(i,q) (e.g. by constructing the product DFAs and checking if there is any path from the starting state to an accepting state). Notice that Bob does not necessarily need to know when the learner A has converged. The reduction from INDEXn is purely information-theoretic and therefore it suffices that there exists a t∗ after which Bob could test the above conditions and recover xi . See Appendix D for further discussion. We have, therefore, constructed a deterministic one-way protocol for INDEXn in which Alice’s message σ has at most m(s) bits. Choosing m(s) = n log2 k − 1 leads to a contradiction of the INDEXn lower bound (Lemma 11), which means that our assumption of ∆A (s, k) < k ℓ is false in the case where m(s) = n log2 k − 1. Recall that we used s = 2p + ℓ + 5 and p = 1 + logk n, which yields ℓ = s − 2p − 5 and p = 1 + logk ((m(s) + 1)/ log2 k). The proof of the lemma is concluded by combining the former identities ∆A (s, k) ≥ k ℓ = k s−2 logk ((m(s)+1)/ log2 k)−3 . Finally, the main result of this section, Theorem 4, follows from Lemma 12, as in the case where ∆A (s, k) ≤ k (1−ϵ)s , we have that 2 logk ((m(s) + 1)/ log2 k) ≥ εs − 3, i.e. m(s) = k εs/2−3+logk (log2 k) = k Ω(εs) .

5. Conclusion This paper develops a space-efficient model of generation in the limit for the DFA family Cs,k and proves a tight memory–breadth tradeoff: poly(s, k) space guarantees hallucination-free generation up to an exponential gap, while achieving substantially smaller gaps (and, in particular, exact identification) forces exponential memory. Several directions remain open, including extending the framework to non-uniform learners, and developing analogous tradeoffs for other resources such as time and sample complexities.

F LAMMARION PABBARAJU PAPAZOV S TOURAS S VENSSON

Acknowledgments This work was partially funded by the Swiss National Science Foundation, grant number 212111. Chirag Pabbaraju is supported by Gregory Valiant’s and Moses Charikar’s Simons Investigator Awards, and a Google PhD Fellowship. Miltiadis Stouras and Ola Svensson are supported by the Swiss State Secretariat for Education, Research and Innovation (SERI) under contract number MB22.00054.

References Charu C Aggarwal. Data streams: models and algorithms, volume 31. Springer Science & Business Media, 2007. Dana Angluin. Inductive inference of formal languages from positive data. Information and control, 45(2):117–135, 1980. Andrew Badr, Viliam Geffert, and Ian Shipman. Hyper-minimizing minimized deterministic finite state automata. RAIRO-Theoretical Informatics and Applications, 43(1):69–94, 2009. Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. Information theory methods in communication complexity. In Proceedings of the 17th Annual IEEE Conference on Computational Complexity, pages 93–102. IEEE Computer Society, 2002. doi: 10.1109/CCC.2002.1004344. Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877–1901, 2020. Moses Charikar and Chirag Pabbaraju. Exploring facets of language generation in the limit. arXiv preprint arXiv:2411.15364, 2024. Moses Charikar and Chirag Pabbaraju. Pareto-optimal non-uniform language generation. arXiv preprint arXiv:2510.02795, 2025. Moses Charikar, Chirag Pabbaraju, and Ambuj Tewari. A characterization of list language identification in the limit. arXiv preprint arXiv:2511.04103, 2025. Noam Chomsky. Three models for the description of language. IRE Transactions on information theory, 2(3):113–124, 1956. Michelle M Chouinard and Eve V Clark. Adult reformulations of child errors as negative evidence. Journal of child language, 30(3):637–669, 2003. B. Jack Copeland. The Church-Turing Thesis. In Edward N. Zalta and Uri Nodelman, editors, The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University, Spring 2026 edition, 2026. Javier Esparza and Michael Blondin. Automata theory: An algorithmic approach. MIT Press, 2023. Pawel Gawrychowski, Artur Jez, and Andreas Maletti. On minimising automata with errors. In International Symposium on Mathematical Foundations of Computer Science, pages 327–338. Springer, 2011. 14

S PACE -E FFICIENT L ANGUAGE G ENERATION IN THE L IMIT

E Mark Gold. Language identification in the limit. Information and control, 10(5):447–474, 1967. David Gries. Describing an algorithm by hopcroft. Acta Informatica, 2(2):97–109, 1973. Steve Hanneke, Amin Karbasi, Anay Mehrotra, and Grigoris Velegkas. On union-closedness of language generation. arXiv preprint arXiv:2506.18642, 2025. John Hopcroft. An n log n algorithm for minimizing states in a finite automaton. In Theory of machines and computations, pages 189–196. Elsevier, 1971. John E Hopcroft, Rajeev Motwani, and Jeffrey D Ullman. Introduction to automata theory, languages, and computation. Acm Sigact News, 32(1):60–65, 2001. T. S. Jayram, Ravi Kumar, and D. Sivakumar. The one-way communication complexity of hamming distance. Theory Comput., 4(1):129–135, 2008. doi: 10.4086/TOC.2008.V004A006. Alkis Kalavasis, Anay Mehrotra, and Grigoris Velegkas. Characterizations of language generation with breadth. arXiv preprint arXiv:2412.18530, page 3, 2024. Michael J Kearns and Umesh Vazirani. An introduction to computational learning theory. MIT press, 1994. Jon Kleinberg and Sendhil Mullainathan. Language generation in the limit. Advances in Neural Information Processing Systems, 37:66058–66079, 2024. Jon Kleinberg and Fan Wei. arXiv:2504.14370, 2025.

Density measures for language generation.

arXiv preprint

Jon Kleinberg, Anay Mehrotra, Amin Saberi, and Grigoris Velegkas. On language generation in the limit with bounded memory, 2026. Eyal Kushilevitz. Communication complexity. In Advances in Computers, volume 44, pages 331–360. Elsevier, 1997. Jiaxun Li, Vinod Raman, and Ambuj Tewari. Generation through the lens of learning theory. arXiv preprint arXiv:2410.13714, 2024. Kyle Mahowald, Anna A Ivanova, Idan A Blank, Nancy Kanwisher, Joshua B Tenenbaum, and Evelina Fedorenko. Dissociating language and thought in large language models. Trends in cognitive sciences, 28(6):517–540, 2024. Andreas Maletti and Daniel Quernheim. Optimal hyper-minimization. International Journal of Foundations of Computer Science, 22(08):1877–1891, 2011. Gary F Marcus. Negative evidence in language acquisition. Cognition, 46(1):53–85, 1993. William Merrill, Jackson Petty, and Ashish Sabharwal. The illusion of state in state-space models. arXiv preprint arXiv:2404.08819, 2024. George A Miller and Noam Chomsky. Finitary models of language users. 1963. 15

F LAMMARION PABBARAJU PAPAZOV S TOURAS S VENSSON

Hristo Papazov and Nicolas Flammarion. Learning algorithms in the limit. arXiv preprint arXiv:2506.15543, 2025. Charlotte Peale, Vinod Raman, and Omer Reingold. Representative language generation. arXiv preprint arXiv:2505.21819, 2025. Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAI blog, 1(8):9, 2019. Ananth Raman and Vinod Raman. arXiv:2501.04179, 2025.

Generation from noisy examples.

arXiv preprint

Walter J Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of computer and system sciences, 4(2):177–192, 1970. Michael Sipser. Introduction to the theory of computation. ACM Sigact News, 27(1):27–29, 1996. Anej Svete and Ryan Cotterell. Recurrent neural language models as probabilistic finite-state automata. arXiv preprint arXiv:2310.05161, 2023. Anej Svete and Ryan Cotterell. Transformers can represent n-gram language models. arXiv preprint arXiv:2404.14994, 2024. Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, 1984.

S PACE -E FFICIENT L ANGUAGE G ENERATION IN THE L IMIT

Organization of the Appendix ➢ Appendix A motivates the focus on finite regular hypothesis spaces by developing the connection to communicative languages induced by interaction among space-bounded agents. ➢ Appendix B provides standard results on DFAs. ➢ Appendix C contains deferred proofs from Section 3. ➢ Appendix D contains deferred proofs from Section 4.

Appendix A. Resource-Bound Communication Here, we expand on our point from Section 1 that space-efficient learning in the limit admits a meaningful formulation only over finite hypothesis spaces of regular languages. We also argue that this language-acquisition regime captures the most relevant and informative setting. Space-Efficient Generation. Under our proposed framework, the learner A receives an adversarial enumeration w1 , w2 , w3 , . . . of a target language K through an online streaming interface. Each string wt ∈ K arrives one symbol at a time, with a designated delimiter separating consecutive strings. After each read symbol, the learning algorithm can perform computation and storage within a specified memory budget, dependent on the complexity of the target language. Furthermore, after processing each wt , the learner outputs a hypothesis representation. The generation objective requires that, after some finite time, every subsequent output of A must represent a language L ⊆ K. As a consequence of the Church-Turing Thesis (Copeland, 2026), we can model space-bounded learners as streaming Turing machines (STM) (Aggarwal, 2007) with bounded-size work tapes. An STM features a one-way read-only input and output tapes and several bidirectional work tapes. Clearly, a space-bounded STM admits only finitely many reachable configurations, so any decision procedure implemented by such a model necessarily recognizes a regular language. Now, the spacebounded learner A who searches for the target K within a hypothesis collection CA should have the ability to verify whether a given input stream w ∈ K belongs to the current hypothesis L ∈ CA . Hence, since the finite-memory STM A decides membership queries for every hypothesis language, CA must contain only regular languages. Moreover, since A can occupy finitely many internal configurations, A can only decide membership for finitely many languages, leading to |CA | < ∞. Thus, space-efficient generation in the limit naturally confines analysis to finite collections of regular hypotheses. Although the restriction to finite regular hypothesis spaces may appear limiting, this languageacquisition regime provides the central case for understanding realistic learners. In particular, we demonstrate that the collection K of communicative languages, which arise from the interaction of space-bounded agents such as humans (Miller and Chomsky, 1963), forms a strict subset of regular languages. Regularity of Communicative Languages. We now show from the dual perspectives of spacebounded language users and learners that the set of communicative languages K can only contain regular languages. First, we posit that a competent user U of a language K ∈ K has the ability to decide whether w ∈ K for any input stream w ∈ Σ∗ . Together with the finite memory assumption for U , this assertion implies the regularity of K. A potential objection arises from Chomsky’s classic observation that the possibility of unbounded center embedding makes English at least context-free (Chomsky, 17

F LAMMARION PABBARAJU PAPAZOV S TOURAS S VENSSON

1956). However, in practice, an English speaker will need access to a pen and paper to reliably judge the grammaticality of deeply center-embedded sentences such as “The mouse that the cat that the dog chased bit ran.” Indeed, for any input stream w ∈ Σ∗ , humans respond in one of three ways: (i) accept w as grammatical, (ii) reject w as ungrammatical, or (iii) determine that processing w requires additional resources and reject w as an unnatural conversational sentence. In this sense, the set of grammatically well-formed English strings K̄ might sit high in the Chomsky hierarchy, but the communicative English sub-language K ⊂ K̄ remains regular. Second, we posit that any communicative language K ∈ K admits learning by a space-bounded learner A. Indeed, human infants acquire grammar without external memory aids, just as large transformers successfully train with finite context windows. Hence, as argued above, the hypothesis space CA contains finitely many regular languages – a conclusion corroborated by the search spaces of LLMs.11 Therefore, due to the realizability assumption K ∈ CA , K becomes regular. Importantly, our arguments for regularity do not imply that communicative languages have finite size or strings of bounded length. Throughout, we model strings as concatenations of grammatically well-formed sentences similar to token sequences produced by LLMs, which may consist of many sentences terminated by an end-of-sequence marker. Under this interpretation, a communicative language may contain strings of unbounded length, provided that those strings remain locally parseable by a finite-memory process. As an analogy, a proficient human reader can judge an entire book as grammatically correct while using only bounded working memory. Finally, we emphasize that we treat languages purely as sets of grammatically well-formed strings and deliberately ignore semantic verification, which may require substantially greater resources.

Appendix B. Standard DFA Results In this section, we briefly state some foundational and some more recent results about DFAs. For a more detailed presentation, we refer the reader to the standard books on Automata Theory (Sipser, 1996; Hopcroft et al., 2001; Esparza and Blondin, 2023). For a DFA A = (Q, Σ, δ, q0 , F ), we denote by L(A) = {w ∈ Σ∗ : δ(q0 , w) ∈ F } the regular language accepted by A and let ∗ L− A (q) = {w ∈ Σ : δ(q0 , w) = q}

and

∗ L+ A (q) = {w ∈ Σ : δ(q, w) ∈ F }

stand for the left (or prefix) and right (or residual) languages of state q ∈ Q. Throughout the paper, we use the term automaton to refer to a DFA. Regular languages possess an interesting algebraic property described by the Myhill-Nerode theorem (Esparza and Blondin, 2023, Chapter 2.4). For a subset L ⊆ Σ∗ , we can define the Nerode equivalence ≡L between strings in Σ∗ such that u ≡L v ⇐⇒ {w ∈ Σ∗ : u · w ∈ L} = {w ∈ Σ∗ : u · w ∈ L}. Now, the theorem states that L is a regular language if and only if ≡L splits Σ∗ into a finite number of equivalence classes, indicated as |≡L|. Moreover, when |≡L| < ∞, there exists a unique minimum-state DFA for L with the following description: q0 = [ε]≡L , Q = {[w]≡L : w ∈ Σ∗ }, F = {[w]≡L : w ∈ L}, δ([w]≡L , σ) = [w · σ]≡L , ∀w ∈ Σ∗ , σ ∈ Σ. One can also consider equivalence of DFAs in terms of accepting languages: A ≡ B ⇐⇒ L(A) = L(B). This equivalence extends to automata states. Indeed, for a DFA A = (Q, Σ, δ, q0 , F ), 11. Transformers, RNNs, and related NTP architectures behave like large probabilistic deterministic finite-state automata (Svete and Cotterell, 2023, 2024; Merrill et al., 2024) and therefore generate from a regular support.

S PACE -E FFICIENT L ANGUAGE G ENERATION IN THE L IMIT

+ we define states p, q ∈ Q as equivalent (p ≡ q) if L+ A (p) = LA (q). Given the automaton A, Hopcroft’s algorithm (Hopcroft, 1971; Gries, 1973) allows us to find the minimal automaton for L(A) in O(|Σ||Q| log |Q|) time by cleverly merging equivalent states. As a consequence of Hopcroft’s + algorithm, if p ̸≡ q, then there exists a distinguishing string w ∈ L+ A (p)△LA (q) of length at most |Q| − 1. A relaxed variant of equivalence, referred to as hyper-equivalence (Badr et al., 2009; Gawrychowski et al., 2011; Maletti and Quernheim, 2011), underpins our results. We define two automata A and B as hyper-equivalent, denoted A ∼ B, if L(A) and L(B) disagree on finitely many strings: |L(A)△L(B)| < ∞. Clearly, ∼ is an equivalence relation, which we can again extend to automata + states by writing p ∼ q if and only if |L+ A (p)△LA (q)| < ∞. Now, we describe the standard product DFA constructions. In the notation of Definition 1, for two (1) (2) DFAs C = (Q1 , Σ, δ1 , q0 , F1 ) and D = (Q2 , Σ, δ2 , q0 , F2 ) accepting regular languages L(C) and L(D), the DFAs recognizing L(C) ∩ L(D), L(C) ∪ L(D) and L(D) \ L(C) can be realized as a suitable product automaton C × D. The state space in this automaton is Q1 × Q2 (so that the (1) (2) number of states is |Q1 | · |Q2 |), and the initial state is the pair (q0 , q0 ). The transition function δ1 × δ2 is defined as

(δ1 × δ2 )((q1 , q2 ), σ) = (δ1 (q1 , σ), δ2 (q2 , σ)). For L(C) ∩ L(D), the accepting states correspond to (q1 , q2 ) pairs such that both q1 ∈ F1 and q2 ∈ F2 . For L(C) ∪ L(D), the accepting states correspond to (q1 , q2 ) pairs such that either q1 ∈ F1 or q2 ∈ F2 . For L(D) \ L(C), the accepting states correspond to (q1 , q2 ) pairs such that q1 ∈ / F1 and q2 ∈ F2 .

Appendix C. Deferred Proofs from Section 3 Proposition 6 (Rank Iteration Space Complexity) rankIteration(s, ≺, j) given in Algorithm 1 requires poly(s, k) bits of memory, provided one can check “C ≺ D?” using poly(s, k) space for any two DFAs C and D with at most s states. Proof Within rankIteration(s, ≺, j), keeping track of count, and the current value of r in the outer for loop requires log(N ) = poly(s, k) space. The inner loop, which traverses the collection of DFAs, also requires keeping track of only poly(s, k) bits of memory. For example, this can be implemented by keeping track of s bits indicating the states present in the DFA and sk log s bits indicating the transitions at each state and alphabet symbol, followed by elementary checks to ensure that the implied DFA is valid. Thereafter, observe that we can reuse the space required by computeRank(·, ≺) in every iteration of the nested for loop. Thus, the total space complexity of Algorithm 1 is poly(s, k) plus the space required to implement computeRank(·, ≺). We now argue that computeRank(·, ≺) can be implemented efficiently. Again, the outer for loop requires keeping track of ℓ which requires log(N ) = poly(s, k) space, and the inner for loop which traverses the collection of DFAs also requires keeping track of poly(s, k) bits, as argued above. Thereafter, every iteration of the nested for loop can reuse the space required by path(·, ·, ℓ, ≺). It thus remains to argue that path(·, ·, ℓ, ≺) can be implemented using poly(s, k) space. Here, we realize that the recursive invocation to path(·, ·, ℓ − ⌈ℓ/2⌉ , ≺) can reuse the space used by the recursive invocation to path(·, ·, ⌈ℓ/2⌉ , ≺). Furthermore, each invocation needs to store only poly(s, k) bits corresponding to the values of C, D and ℓ it is invoked with before recursing. The 19

F LAMMARION PABBARAJU PAPAZOV S TOURAS S VENSSON

|L(A) \ L(C)| ≤ |L(A) \ L(B)| + |L(B) \ L(C)| < ∞.

(union bound)

|L(A) \ L(B)| = |L(A) \ (L(B) ∪ L(C))| + |(L(A) ∩ (L(C)) \ L(B)| .

Expressing all remaining pairwise set differences in this fashion, we have |L(B) \ L(A)| = |L(B) \ (L(A) ∪ L(C))| + |(L(B) ∩ (L(C)) \ L(A)| , |L(B) \ L(C)| = |L(B) \ (L(C) ∪ L(A))| + |(L(B) ∩ (L(A)) \ L(C)| , |L(C) \ L(B)| = |L(C) \ (L(B) ∪ L(A))| + |(L(C) ∩ (L(A)) \ L(B)| , |L(A) \ L(C)| = |L(A) \ (L(C) ∪ L(B))| + |(L(A) ∩ (L(B)) \ L(C)| , |L(C) \ L(A)| = |L(C) \ (L(A) ∪ L(B))| + |(L(C) ∩ (L(B)) \ L(A)| . Since A ≺2 B and B ≺2 C, we also have that |L(A) \ L(B)| < |L(B) \ L(A)| and |L(B) \ L(C)| < |L(C) \ L(B)|. Using the above identities, this means that |L(A) \ (L(B) ∪ L(C))| + |(L(A) ∩ (L(C)) \ L(B)| < |L(B) \ (L(A) ∪ L(C))| + |(L(B) ∩ (L(C)) \ L(A)| ,

(4)

|L(B) \ (L(C) ∪ L(A))| + |(L(B) ∩ (L(A)) \ L(C)| < |L(C) \ (L(B) ∪ L(A))| + |(L(C) ∩ (L(A)) \ L(B)| . 20

(5)

S PACE -E FFICIENT L ANGUAGE G ENERATION IN THE L IMIT

(6)

But then, using the identities above one final time, this means that |L(A) \ L(C)| < |L(C) \ L(A)|, which is the desired inequality. Thus, we have shown that A ≺2 C.

Lemma 9 (Symmetric Difference Contains Length-O(s) Strings) Let A = (QA , Σ, δA , q0A , FA ) and B = (QB , Σ, δB , q0B , FB ) denote DFAs having at most s states over a common alphabet Σ, such that |L(A)△L(B)| < ∞. Then, for any string w ∈ Σ∗ , if |w| ≥ 2s − 1, then w ∈ / L(A)△L(B). Proof The result essentially follows from Lemma 5 in Gawrychowski et al. (2011); we flesh out a detailed proof for completeness. Consider a “disjoint union automaton” M , whose state space QM = QA ⊔ QB , so that |QM | = |QA | + |QB | ≤ 2s. In M , we retain transitions originally within states in QA and QB , but there are no transitions across states in QA and QB . That is, for any alphabet σ ∈ Σ, for any q ∈ QA , we have δM (q, σ) = δA (q, σ), and for any q ∈ QB , we have δM (q, σ) = δB (q, σ). M has two distinct initial states q0A and q0B , and accepting states F = FA ⊔ FB . We note that M is not exactly a valid automaton, and we only construct it for the purpose of analysis. Let us the define the “right language” of a state q ∈ M as follows: ∗ L+ M (q) = {w ∈ Σ : δM (q, w) ∈ F } + A B We immediately have that L+ M (q0 ) = L(A) and LM (q0 ) = L(B). Now, for any p, q ∈ QM , define the following (pseudo)distance dM (p, q): ≥ℓ ≥ℓ dM (p, q) = min{ℓ ≥ 0 : L+ = L+ M (p) ∩ Σ M (q) ∩ Σ }.

(7)

where Σ≥ℓ = {w ∈ Σ∗ : |w| ≥ ℓ}. In words, dM (p, q) is the smallest ℓ, such that the right languages + L+ M (p) and LM (q), restricted to strings of length at least ℓ, are equal. We can verify that dM (p, q) satisfies the following recursive formula: ( + 0 if L+ M (p) = LM (q) dM (p, q) = (8) 1 + maxσ∈Σ {dM (δM (p, σ), δM (q, σ))} otherwise. 21

F LAMMARION PABBARAJU PAPAZOV S TOURAS S VENSSON

In fact, dM (p, q) is a so-called “ultrapseudometric” over the states in QM : we can immediately verify that dM (p, p) = 0, dM (p, q) ≥ 0 always and dM (p, q) = dM (q, p); more importantly, dM (p, q) also satisfies the strong triangle inequality: dM (p, q) ≤ max(dM (p, r), dM (r, q)).

(9)

To see this, note that the inequality holds immediately if either dM (p, r) = ∞ or dM (r, q) = ∞. Otherwise, let dM (p, r) = a < ∞ and dM (r, q) = b < ∞. By definition of dM (·, ·), we have that ≥a ≥a L+ = L+ M (p) ∩ Σ M (r) ∩ Σ

and

≥b ≥b L+ = L+ M (r) ∩ Σ M (q) ∩ Σ

=⇒

≥max(a,b) ≥max(a,b) L+ = L+ M (p) ∩ Σ M (q) ∩ Σ

=⇒

dM (p, q) ≤ max(a, b) = max(dM (p, r), dM (r, q)),

as required. We now claim that, for any two states p, q ∈ QM , if dM (p, q) < ∞, then dM (p, q) < |QM | ≤ 2s. Before we go ahead and prove this, let us first see how it implies the lemma. For this, con+ A B sider dM (q0A , q0B ). Recall that L+ M (q0 ) = L(A) and LM (q0 ) = L(B), and by assumption, |L(A)△L(B)| < ∞. But this necessarily means that dM (q0A , q0B ) < ∞ (otherwise, there would be arbitrarily long strings in the symmetric difference, making it an infinite set). So, by our claim, it holds that dM (q0A , q0B ) ≤ 2s. By definition of dM (·, ·), this implies that any string in Σ∗ of length at least 2s − 1 is either in both of L(A) and L(B) or in neither, and hence proves the lemma. We now proceed to proving the promised claim: if dM (p, q) < ∞, then dM (p, q) < |QM |. Towards this, for any i ≥ 0, consider the equivalence relation Di over the set QM defined as follows: (p, q) ∈ Di ⇐⇒ dM (p, q) ≤ i.

(10)

To see that this is an equivalence relation for every i, note that (p, p) ∈ Di always since dM (p, p) = 0 (reflexivity), and also, (p, q) ∈ Di =⇒ (q, p) ∈ Di since dM (p, q) = dM (q, p) (symmetry). For the transitive property, we use the strong triangle inequality (9) from above: if (p, r) ∈ Di and (r, q) ∈ Di , meaning that dM (p, r) ≤ i, dM (r, q) ≤ i, then dM (p, q) ≤ max(dM (p, r), dM (r, q)) ≤ i, meaning that (p, q) ∈ Di . Now, let ni be the number of equivalence classes that Di partitions QM into. We have that n0 ≤ |QM |, and every ni ≥ 1. Observe now that by definition of Di , it is also the case that D0 ⊆ D1 ⊆ D2 ⊆ . . . . This immediately implies that n0 ≥ n1 ≥ n2 . . . . Since n0 ≤ |QM | < ∞ and each ni ≥ 1, there must be some finite i for which ni = ni+1 . We now claim that if ni = ni+1 for any i ≥ 0, then both: (1) for any two states p, q ∈ QM , dM (p, q) > i =⇒ dM (p, q) = ∞ , and (2) nj = ni for every j > i. For (1), first note that ni = ni+1 implies that Di = Di+1 . This follows simply because Di ⊆ Di+1 , and both are equivalence relations on QM . Namely, if there is any pair (p, q) ∈ Di+1 which is not in Di , then this pair would merge two equivalence classes in Di , contradicting ni = ni+1 . 22

S PACE -E FFICIENT L ANGUAGE G ENERATION IN THE L IMIT

Now, fix p, q ∈ QM , and suppose that dM (p, q) > i. We will first argue that dM (p, q) ̸= i + 1. Suppose not, meaning that dM (p, q) = i + 1. Then, by definition, (p, q) ∈ Di+1 . But (p, q) ∈ / Di , contradicting that Di = Di+1 . Thus, dM (p, q) ̸= i + 1. Now, we argue that dM (p, q) ̸= j for every finite j > i + 1. Suppose not, meaning that dM (p, q) = j for some finite j > i + 1. Since j > i + 1 ≥ 1, by the recursive definition in (8), j = dM (p, q) = 1 + max{dM (δM (p, σ), δM (q, σ))}. σ∈Σ

This means that for σ ∈ Σ which is the maximizer above, dM (δM (p, σ), δM (q, σ)) = j − 1. Denoting δM (p, σ) := p1 and δM (q, σ) := q1 , we have that δM (p1 , q1 ) = j − 1. Let t = j − (i + 1). Since j is finite, t is finite; so repeating the argument above t times, we will obtain that δM (pt , qt ) = j − t = i + 1. But this means that dM (pt , qt ) > i, which, as we established above, necessarily means that δM (pt , qt ) ̸= i + 1. This is a contradiction, and hence dM (p, q) ̸= j. This proves (1). We now turn towards proving (2). Consider any j > i. For any two states p, q ∈ QM , if dM (p, q) ≤ j < ∞, then (1) above implies that dM (p, q) ≤ i. We also trivially have that dM (p, q) ≤ i =⇒ dM (p, q) ≤ j. That is, for any two states p, q ∈ QM , it holds that (p, q) ∈ Di ⇐⇒ dM (p, q) ≤ i ⇐⇒ dM (p, q) ≤ j ⇐⇒ (p, q) ∈ Dj . Thus, Di = Dj and hence nj = ni for every j > i, which proves (2). Finally, putting (2) together with the fact that |QM | ≥ n0 ≥ n1 ≥ . . . , where each ni ≥ 1, we necessarily have that by i = |QM | − 1, it holds that ni = ni+1 . But then the contrapositive of (1) above implies that for any p, q ∈ QM , dM (p, q) < ∞ =⇒ dM (p, q) ≤ |QM | − 1, which completes the entire proof. Theorem 10 (Space-Efficient Language Generation) Let K denote the unknown target language recognized by a DFA of size at most s. There exists an algorithm A which, for all sufficiently large t, outputs a DFA A′ = A(t) that satisfies L(A′ ) ⊆ K, and uses only poly(s, k) space. Furthermore, the algorithm misses at most |K \ L(A′ )| ≤ O(k 2s−2 ) target strings. Proof The algorithm A runs SpaceEfficientTraversal(≺2 ), which outputs, in the limit, a DFA Ai(t) that satisfies |L(Ai(t) )△K| < ∞ (by Proposition 8). Let B be a DFA that accepts all strings of length at least 2s − 1, and rejects all strings of smaller length; B can be constructed with 2s states q0 , . . . , q2s−1 where every qi always transitions to qi+1 for 0 ≤ i < 2s − 1. The initial state is q0 , every qi for 1 ≤ i < 2s − 1 is a rejecting sink state, and q2s−1 is the only accepting sink state. By Lemma 9, we have that any w ∈ L(B) is either in L(Ai(t) ) ∩ K or in Σ∗ \ (L(Ai(t) ) ∪ K). So, consider the DFA A′ which is the product DFA recognizing L(Ai(t) ) ∩ L(B). The DFA A′ has at most s · 2s = 2s2 states, and satisfies that L(A′ ) ⊆ L(Ai(t) ) ∩ K ⊆ K. Furthermore, since any w ∈ K \ Ai(t) must necessarily have length smaller than 2s − 1, K \ Ai(t) ⊆ K \ L(B), and hence K \ L(A′ ) ⊆ (K \ Ai(t) ) ∪ (K \ L(B)) = K \ L(B). 23

(11)

F LAMMARION PABBARAJU PAPAZOV S TOURAS S VENSSON

Thus, L(A′ ) is only deficient of the strings in K that have length at most 2s − 2. If |Σ| = k = 1, we can have the algorithm A additionally keep track of a set S of all the strings seen in the input that have length at most 2s − 2. Since there are at most 2s − 1 such strings (including the empty string), this requires only poly(s) memory. Furthermore, since all the strings in K are eventually revealed, the set S eventually contains all strings in K that have length at most 2s − 2. Finally, since S can be recognized by a DFA having at most 2s − 1 states, the algorithm can output A(t) to be the product DFA that recognizes L(A′ ) ∪ S, which has at most 2s2 · (2s − 1) = O(s3 ) states. In this case, we are guaranteed that L(A(t)) = K eventually. If k > 1, we simply have the algorithm output the DFA A(t) = A′ . In this case, (11) gives that 2s−1 |K \ L(A′ )| ≤ |K \ L(B)| = k k−1−1 = O(k 2s−2 ). Let us revisit the trick we used above for the case where |Σ| = 1; here, we had the algorithm keep track of the set S of input strings that had length at most 2s − 2. With a unary alphabet, S could have at most O(s) strings, and hence the algorithm could store all of these in its poly(s, k) memory budget. In fact, this allowed the algorithm to achieve the stronger guarantee that A(t) = K; i.e., A identified the target K in the limit! When k > 1, storing the set S requires exp(s, k) memory, which is why we simply returned A′ in this case. Nevertheless, we note that with exp(s, k) memory, we can use the same trick as in the |Σ| = 1 case, and achieve identification in the limit.

Appendix D. Deferred Proofs from Section 4 Proof [Proof of Lemma 11] Suppose that a deterministic protocol for INDEXn uses c < n log2 k bits of communication. Then, there are at most 2c < k n possible messages that the protocol can send, meaning that there exist two vectors x, y ∈ [k]n , with x ̸= y on which the protocol sends the same message. Let i be one coordinate in which x and y differ. In both instances of the problem (namely, (x, i) and (y, i)), Bob receives the same message and produces the same answer, even though xi ̸= yi , which contradicts the correctness of the protocol. Relaxed symmetric-difference lower bound. We also spell out the proof of the second part of Theorem 4, corresponding to the relaxed objective mentioned after Definition 2. In this formulation, the learner is not required to satisfy L(A(t)) ⊆ K; instead, for every target K ∈ Cs,k and every surjective enumeration of K, the limiting hypothesis must satisfy e A (s, k) |L(A(t))△K| ≤ ∆ for all sufficiently large t. We use exactly the same INDEXn reduction and the same languages as in the proof of Lemma 12. Fix Bob’s index i, and write Bq := Base(i, q) for q ∈ Σ. If Alice’s input is x, then after Alice’s prefix and Bob’s continuation, the target language presented to the learner is Bxi . Let H be the limiting DFA output by the learner on this stream. Assume for contradiction that e A (s, k) < k ℓ . ∆ Under the new definition, this means that |L(H)△Bxi | < k ℓ . 24

S PACE -E FFICIENT L ANGUAGE G ENERATION IN THE L IMIT

For any q ̸= xi , the two candidate target languages Bq and Bxi differ exactly on the two disjoint blocks Lmap(i,q) and Lmap(i,xi ) . Therefore, |Bq △Bxi | = 2k ℓ . By the triangle inequality for symmetric difference, |L(H)△Bq | ≥ |Bq △Bxi | − |L(H)△Bxi | > 2k ℓ − k ℓ = k ℓ . On the other hand, |L(H)△Bxi | < k ℓ . Hence q = xi is the unique minimizer of |L(H)△Base(i, q)| over q ∈ Σ. Bob can therefore decode xi by computing, for every q ∈ Σ, the size of the regular language L(H)△Base(i, q), and outputting the unique minimizer. Concretely, Bob constructs the product DFA for this symmetric difference and counts its accepted language when it is finite; an infinite value may be treated as +∞. Under the promise above, the true candidate is finite and uniquely smallest. This gives the same one-way INDEXn protocol as in Lemma 12 with Alice’s message equal to the memory state of the learner. The INDEXn lower bound is contradicted whenever that memory state e A (s, k) ≥ k ℓ , and substituting the same values of p, ℓ, n as in has fewer than n log2 k bits. Thus ∆ Lemma 12 gives the same quantitative lower bound. Further remarks for the Proof of Lemma 12. As we can see in the proof of INDEXn above, the lower bound is purely information-theoretic and contains no requirements about the computation power of Alice and Bob. This means that even the existence of two functions, an encoding function of x to ℓ < n log2 k bits, let it be f : [k]n → [2]ℓ , and a decoding function g : [n] × [2]ℓ → [k] such that for all x ∈ [k]n and all i ∈ [n] it holds that g(i, f (x)) = xi , violates the lower bound. In our construction, you can view f (x) as the memory state σ of the learner after Alice has given it her part of the input. Now, let t∗ (i, q) be the timestep after which the learner A has converged to its limiting DFA, on the enumeration of our construction when the target language is Base(i, q). Let also T ∗ be the maximum over t∗ (i, q) for all i ∈ [n] and q ∈ [k]. Then, the decoding function g can be defined as the output of Bob when he waits for (T ∗ + 1) time steps and then performs the corresponding finite DFA test. Of course, the existence of g contradicts the INDEXn lower bound.

F LAMMARION PABBARAJU PAPAZOV S TOURAS S VENSSON

[k]

⊥ 0 [k]

[k ] \ {0, 1}

[k] (j)

(j)

w1 (j)

[k] \ {w1 }

(j)

w2 (j)

[k] \ {w2 }

(j)

...

[k]

(j)

[k] \ {w3 } [k]

ℓ − 1 steps

... [k]

[k]

Figure 1: A Deterministic Finite Automaton (DFA) accepting Base(j, q) for some j ∈ [n] and q ∈ Σ. (j) (j) (j) (j) We use the notation enck (j) = w1 ◦ w2 ◦ w3 ◦ · · · ◦ wp

Record · ID 307030 · SHA-256 98e727c5ce2a9f87
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.