这篇论文为空间受限下的语言学习建立了严格理论框架，给出了指数和多项式空间下的精确界限，对理解计算资源与生成能力的关系很有启发。
该论文提出一种资源感知的语言生成极限理论框架，在空间效率约束下研究从对抗性正例流中学习目标语言。主要结果：当允许指数空间时，学习器能精确识别目标语言K；在多项式空间约束下，给出一种使用poly(s,k)空间的流式算法，其生成间隙Δ=O(k^{2s-2})，并能捕获K中所有长度≥2s-1的字符串。通过通信复杂度归约证明下界：要达到生成间隙Δ≤k^{(1-ε)s}，需要k^{Ω(εs)}内存。这些结果揭示了多项式空间生成与指数空间精确识别之间的尖锐转变。
Space-Efficient Language Generation in the Limit
We initiate a resource-aware theory of \textit{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 \subseteq K$ while omitting at most $Δ$ strings of $K$. We focus on $\mathcal{C}_{s,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 $\mathrm{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 $Δ\le k^{(1-\varepsilon)s}$ requires $k^{Ω(\varepsilon s)}$ memory. Together, these results reveal a sharp transition between polynomial-space generation and exponential-space exact identification.