Language Generation: Complexity Barriers and Implications for Learning
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908795211350016 |
|---|---|
| author | Arenas, Marcelo Barceló, Pablo Cofré, Luis Kozachinskiy, Alexander |
| author_facet | Arenas, Marcelo Barceló, Pablo Cofré, Luis Kozachinskiy, Alexander |
| contents | Kleinberg and Mullainathan showed that language generation in the limit is always possible at the level of computability: given enough positive examples, a learner can eventually generate data indistinguishable from a target language. However, such existence results do not address feasibility. We study the sample complexity of language generation in the limit for several canonical classes of formal languages. Our results show that infeasibility already appears for context-free and regular languages, and persists even for strict subclasses such as locally threshold testable languages, as well as for incomparable classes such as non-erasing pattern languages, a well-studied class in the theory of language identification. Overall, our results establish a clear gap between the theoretical possibility of language generation in the limit and its computational feasibility. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_05759 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Language Generation: Complexity Barriers and Implications for Learning Arenas, Marcelo Barceló, Pablo Cofré, Luis Kozachinskiy, Alexander Computation and Language Artificial Intelligence Formal Languages and Automata Theory Machine Learning Kleinberg and Mullainathan showed that language generation in the limit is always possible at the level of computability: given enough positive examples, a learner can eventually generate data indistinguishable from a target language. However, such existence results do not address feasibility. We study the sample complexity of language generation in the limit for several canonical classes of formal languages. Our results show that infeasibility already appears for context-free and regular languages, and persists even for strict subclasses such as locally threshold testable languages, as well as for incomparable classes such as non-erasing pattern languages, a well-studied class in the theory of language identification. Overall, our results establish a clear gap between the theoretical possibility of language generation in the limit and its computational feasibility. |
| title | Language Generation: Complexity Barriers and Implications for Learning |
| topic | Computation and Language Artificial Intelligence Formal Languages and Automata Theory Machine Learning |
| url | https://arxiv.org/abs/2511.05759 |