Characterizing Language Generation in the Limit: Finite Witnesses and a Separation-Width Hierarch
New work characterizes language generation in the limit via finite witnesses, proves a full separation-width hierarchy, and formalizes all results in Lean.
The paper fully characterizes when language generation in the limit is possible for arbitrary families over a countable universe: each target must admit a finite positive witness such that targets activated by any finite sample share an infinite common intersection. It defines positive separation width and proves every level of the resulting hierarchy occurs, with countable families admitting singleton witnesses and unions of families with infinite common cores requiring unbounded finite witnesses. The characterization, a universal normalization, and a diagonal capture lemma are machine-checked in the Lean proof assistant, with the development maintained on GitHub.
- Generation possible exactly when targets admit finite witnesses with infinite common intersection.
- Positive separation width hierarchy: every level is realized.
- Countable families admit singleton witnesses; finite widths realized by explicit families.
- Full characterization verified in the Lean proof assistant.
- Products
- Lean
From the original article
1 min read at arxiv.orgLanguage 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.
By Xiaoyu Li · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.