Characterizing Language Generation in the Limit: Finite Witnesses and a Separation-Width Hierarchy

• URL: http://arxiv.org/abs/2609.10525v2
• Date: Thu, 10 Sep 2026 11:32:57 GMT
• Title: Characterizing Language Generation in the Limit: Finite Witnesses and a Separation-Width Hierarchy
• Abstract summary: Generation is possible exactly when each target can be assigned a finite positive witness.<n>A search through unconfirmed histories converts any successful generator into one depending only on the observed set.<n>Countable families admit singleton witnesses, explicit families realize every finite width, and a union of two families with infinite common cores requires finite witnesses.
• Score: 39.91890433860882
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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

Related papers

• A Formal Limitation on Learning Human Language From Textual Corpora [54.22186267212778]
  We derive upper bounds on the probability that a decoder recovers a speaker's intended meaning from a representation of the utterance.<n>Experiments on artificial languages, Mandarin zero-pronoun resolution, and color reference provide empirical evidence in support of the theory.
  arXiv  Detail & Related papers  (2026-08-28T17:38:24Z)
• On Language Generation in the Limit with Bounded Memory [17.70989972580602]
  We study language generation in the limit under bounded memory.<n>In this task, a learner observes examples from an unknown target language one at a time and must eventually output only new valid examples.
  arXiv  Detail & Related papers  (2026-05-28T17:57:03Z)
• Contrastive Identification and Generation in the Limit [39.91890433860882]
  We study contrastive identification and generation in the limit, where the learner observes a contrastive presentation of data.<n>We prove a sharp reversal under adversarial corruption: there exist classes identifiable from contrastive pairs under any finite corruption budget.<n>The unifying technical object is the common crossing graph, which encodes pairwise ambiguity, family-level generation obstructions, and corruption defects in a single coverage-and-incidence language.
  arXiv  Detail & Related papers  (2026-05-07T13:14:51Z)
• Language Generation: Complexity Barriers and Implications for Learning [51.449718747429756]
  We show that even for simple and well-studied language families the number of examples required for successful generation can be extraordinarily large.<n>These results reveal a substantial gap between theoretical possibility and efficient learnability.
  arXiv  Detail & Related papers  (2025-11-07T23:06:48Z)
• Language Generation in the Limit: Noise, Loss, and Feedback [10.280148603465697]
  We show that a finite union of uniformly generatable collections is generatable in the limit, and asked if the same is true for non-uniform generation.<n>We show the equivalence of these models for uniform and non-uniform generation, and provide a characterization of non-uniform noisy generation.
  arXiv  Detail & Related papers  (2025-07-21T07:18:04Z)
• On Union-Closedness of Language Generation [48.36356615217017]
  We investigate language generation in the limit - a model by Kleinberg and Mullainathan and extended by Li, Raman, and Tewari.<n>Our results resolve two open questions of Li et al. by proving finite unions of generatable or non-uniformly generatable classes need not be generatable.<n>Our approach utilizes carefully constructed classes along with a novel diagonalization argument that could be of independent interest in the growing area of language generation.
  arXiv  Detail & Related papers  (2025-06-23T13:42:25Z)
• Exploring Facets of Language Generation in the Limit [10.18252143035175]
  We show that every countable language collection has a generator which has the stronger property of non-uniform generation in the limit.<n>We formalize the tension between validity and breadth in the generation algorithm of [KM24] by introducing a definition of exhaustive generation.<n>We also provide a precise characterization of the language collections for which exhaustive generation is possible.
  arXiv  Detail & Related papers  (2024-11-22T22:13:40Z)
• A Measure-Theoretic Characterization of Tight Language Models [105.16477132329416]
  In some pathological cases, probability mass can leak'' onto the set of infinite sequences. This paper offers a measure-theoretic treatment of language modeling. We prove that many popular language model families are in fact tight, meaning that they will not leak in this sense.
  arXiv  Detail & Related papers  (2022-12-20T18:17:11Z)
• Language learnability in the limit for general metrics: a Gold-Angluin result [91.3755431537592]
  We use Niyogi's extended version of a theorem by Blum and Blum (1975) on the existence of locking data sets to prove a necessary condition for learnability in the limit of any family of languages in any given metric. When the language family is further assumed to contain all finite languages, the same condition also becomes sufficient for learnability in the limit.
  arXiv  Detail & Related papers  (2021-03-24T13:11:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.