[论文] Characterizing Language Generation in the Limit: Finite Witnesses and a Separation-Width Hierarchy (arXiv:2609.10525)

论文概要

研究领域: ML
作者: Xiaoyu Li, Andi Han, Jiaojiao Jiang, Junbin Gao
发布时间: 2026-09-09
arXiv: 2609.10525

中文摘要

极限语言生成要求从任何穷尽正例呈现中为未知无限语言生成有效的未见元素。本文对可数宇宙上的任意语言族刻画了这一任务。生成是可能的，当且仅当每个目标可以被分配一个有限正见证，使得被任何有限样本激活的目标具有无限共同交集。必要方向来自一个通用归一化：通过未确认历史的搜索将任何成功生成器转换为仅依赖于观测集合的生成器。本文还探讨了兼容见证需要多大：正分离宽度记录最小统一尺寸界，还有两个进一步的层次分别对应无界有限见证和不存在兼容有限见证分配的情况。每个层次都存在实例。所有刻画和完整宽度层次已在Lean中验证。

原文摘要

Language generation in the limit asks for valid unseen elements from every exhaustive positive presentation of an unknown infinite language. We characterize this task for arbitrary families over a countable universe. Generation is possible exactly when each target can be assigned a finite positive witness so that the targets activated by any finite sample have an infinite common intersection. The necessary direction follows from a universal normalization: a search through unconfirmed histories converts any successful generator into one depending only on the observed set. We then ask how large compatible witnesses must be. Positive separation width records the smallest uniform size bound, with two further levels for unbounded finite witnesses and the absence of any compatible finite-witness assignment. Every level occurs. Countable families admit singleton witnesses, explicit families realize every finite width, and a union of two families with infinite common cores requires unbounded finite witnesses. Finally, countable-support and finite-profile obstructions explain why local combinatorial data cannot determine generation in the limit. The characterization and full width hierarchy are checked in Lean, including the simplified normalization and a direct diagonal capture lemma. The accompanying Lean development is maintained at https://github.com/xiaoyulics/language-generation-characterization

自动采集于 2026-09-11

#论文 #arXiv #ML #小凯