这篇论文为有界记忆下的语言生成建立了理论基础，对设计内存受限的AI生成系统（如边缘设备上的语言模型）有直接指导意义。做理论或系统优化的开发者值得关注其中的密度与识别界限。
这篇论文研究了在有限记忆条件下语言生成的理论极限。传统研究假设学习者能访问全部历史数据，但现实算法只能保留有限信息。作者首先证明了在温和的枚举限制下，即使没有记忆，任何可数无限语言集合仍可生成；否则，他们精确刻画了无记忆生成可行的条件。对于有限集合，他们利用Sperner定理和对称链分解给出了无记忆生成器能达到的最优极小极大密度。进一步发现，滑动窗口（最近W个样本）不改善最坏情况密度，而自适应存储b个历史样本则能提升密度。最后，他们重新审视了极限识别问题，证明在仅记忆上一次猜测的增量变体中，精确识别对三个语言集合即失败，但放宽到“近似”版本后，对任何有限集合都可行。
On Language Generation in the Limit with Bounded Memory
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. Prior work assumes access to the entire history, a strong assumption since realistic algorithms retain limited past information. Classical work in learning theory shows memory constraints dramatically alter learnability; we extend this to language generation. First, we study memoryless generators. Under a mild enumeration restriction, every countable collection of infinite languages remains generable without memory. Without this restriction, we exactly characterize when memoryless generation is possible. For finite collections, we characterize the optimal minimax density achievable by memoryless generators -- the best density guaranteed against any collection of a given size. This combinatorial bound relies on Sperner's theorem and symmetric chain decompositions. We further show that 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 improves the achievable density for every $b \geq 1$. Finally, we revisit identification in the limit, where the learner must converge to a single correct hypothesis for the target language. We focus on its incremental variant, where the learner remembers only its previous guess. Here, although exact identification fails on a collection of just three languages, a mild relaxation requiring convergence to an ``approximate'' version of the target is achievable for every finite collection. These results show bounded memory affects these tasks differently: generation remains achievable for every countable collection, while density and identification are confined to finite collections, with guarantees weakening as the collection grows.