Research map / Learning theory and algorithms / Sample complexity
On Union-Closedness of Language Generation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that language generation in the limit is not closed under finite unions, via a diagonalization construction over two collections of integer languages, and answers related open questions on EUC and minimal counterexamples.
Problem
Whether generation in the limit (Kleinberg-Mullainathan model and its uniform/non-uniform/generatable hierarchy) is closed under finite unions, and whether uncountable non-uniformly generatable classes must satisfy the EUC property.
Approach
Builds two uncountable collections over the integers, each individually generatable, whose union is non-generatable, using a novel diagonalization where the adversary forces generator mistakes in alternating rounds so the final enumerated language lies in one of the collections; a minimal variant uses a countable plus a uniformly generatable uncountable class.
Key results
- Two uncountable collections, each non-uniformly generatable, have a non-generatable union, so generation is not closed under finite unions (answering Questions 1 and 2 negatively).
- A countable non-uniformly generatable collection plus an uncountable uniformly generatable collection can have a non-generatable union.
- An uncountable non-uniformly generatable collection violating EUC is exhibited, answering Question 3.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Take the union of two uncountable non-uniformly generatable classes | Language generation in the limit · Uncountable language classes | generatability | Hurt |
| Take the union of a countable non-uniformly generatable class and an uncountable uniformly generatable class | Language generation in the limit · Countable-union uncountable class pair | generatability | Hurt |
| Use the uncountable class L1 of languages omitting finitely many negative integers and infinitely many positive integers | Non-uniform language generation · Eventually Unbounded Closure (EUC) | EUC property | Hurt |
| Take the union of two uniformly generatable classes | Language generation in the limit · Finite unions | generatability | Helped |
| Make the countable component uniformly generatable | The minimal pair of classes whose union is not generatable · Finite unions | generatability | Helped |
| Make the uncountable component countable | The minimal pair of classes whose union is not generatable · Finite unions | generatability | Helped |
Surprising findings
- Union of two individually generatable classes can be non-generatable, so generators cannot be boosted by combining them.
- Language identification is also not closed under finite unions, shown by a finite plus countable example.
Limitations
- Results are purely theoretical and concern abstract collections; no practical generator is studied.
- The paper does not provide a full characterization of generatability.
Experimental setup
Builds on: Kleinberg-Mullainathan language generation in the limit Li-Raman-Tewari generation hierarchy eventually unbounded closure (EUC)
Closest papers by meaning
- Representative Language Generation (ICML 2025 · similarity 0.88)
- Language Generation in the Limit (NeurIPS 2024 · similarity 0.87)
- Agnostic Language Identification and Generation (NeurIPS 2026 · similarity 0.87)
- Generating in the Limit with Infinitely Many Hallucinations (NeurIPS 2026 · similarity 0.87)
- On Generation in Metric Spaces (NeurIPS 2026 · similarity 0.87)
- A Theory of Time-Sensitive Language Generation: Sparse Hallucination Beats Mode Collapse (NeurIPS 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.