arXiv:2511.05295cs.DScs.CL2025-11被引 12

提出语言生成密度上限为1/2,且在部分信息下仍可保持一半密度。

Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizations

  • 基于部分枚举设定,设计算法在未知语言中生成新字符串。
  • 证明最优生成密度严格不超过1/2,且在部分信息下可达α/2。
  • 首次用拓扑性质刻画语言识别可行性,连接形式语言与拓扑空间。

大语言模型的成功激发了对语言生成与学习的正式理论研究。本文研究‘极限生成’框架:对手从未知语言 $K$ 中枚举字符串(来自可数类),算法需生成 $K$ 中未出现的新串。已有工作表明生成始终可能,且某些算法可达到正密度,揭示正确性与覆盖率间的权衡。本文解决核心开放问题,证明最优下界密度为 $1/2$。随后将模型推广至‘部分枚举’:对手仅揭示 $K$ 的无限子集 $C eq K$。我们证明生成仍可行,若 $C$ 在 $K$ 中具有下密度 $α$,则生成输出密度至少为 $α/2$,匹配上界。该结果将 $1/2$ 界推广至部分信息场景,即生成器可恢复原密度的 $1/2$。此外,重新审视经典 Gold–Angluin 模型下的语言识别问题。我们刻画了识别在极限下成立的条件——假设序列 $M_t$ 最终满足 $C \ackslashsubseteq M \ackslashsubseteq K$,并给出新的拓扑表述:该条件等价于某个适当拓扑空间满足 $T_D$ 分离公理。

原文摘要 · Abstract (English)

The success of large language models (LLMs) has motivated formal theories of language generation and learning. We study the framework of \emph{language generation in the limit}, where an adversary enumerates strings from an unknown language $K$ drawn from a countable class, and an algorithm must generate unseen strings from $K$. Prior work showed that generation is always possible, and that some algorithms achieve positive lower density, revealing a \emph{validity--breadth} trade-off between correctness and coverage. We resolve a main open question in this line, proving a tight bound of $1/2$ on the best achievable lower density. We then strengthen the model to allow \emph{partial enumeration}, where the adversary reveals only an infinite subset $C \subseteq K$. We show that generation in the limit remains achievable, and if $C$ has lower density $α$ in $K$, the algorithm's output achieves density at least $α/2$, matching the upper bound. This generalizes the $1/2$ bound to the partial-information setting, where the generator must recover within a factor $1/2$ of the revealed subset's density. We further revisit the classical Gold--Angluin model of \emph{language identification} under partial enumeration. We characterize when identification in the limit is possible -- when hypotheses $M_t$ eventually satisfy $C \subseteq M \subseteq K$ -- and in the process give a new topological formulation of Angluin's characterization, showing that her condition is precisely equivalent to an appropriate topological space having the $T_D$ separation property.

语言生成形式理论拓扑学习理论

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。