Language Generation in the Limit: Complexity Barriers and Implications for Learning

Marcelo Arenas, Pablo Barcelo, Luis Cofré, Alexander Kozachinskiy
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:3423-3433, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-arenas26a, title = {Language Generation in the Limit: Complexity Barriers and Implications for Learning}, author = {Arenas, Marcelo and Barcelo, Pablo and Cofr\'{e}, Luis and Kozachinskiy, Alexander}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {3423--3433}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/arenas26a/arenas26a.pdf}, url = {https://proceedings.mlr.press/v306/arenas26a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Language Generation in the Limit: Complexity Barriers and Implications for Learning %A Marcelo Arenas %A Pablo Barcelo %A Luis Cofré %A Alexander Kozachinskiy %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-arenas26a %I PMLR %P 3423--3433 %U https://proceedings.mlr.press/v306/arenas26a.html %V 306 %X 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.
APA
Arenas, M., Barcelo, P., Cofré, L. & Kozachinskiy, A.. (2026). Language Generation in the Limit: Complexity Barriers and Implications for Learning. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:3423-3433 Available from https://proceedings.mlr.press/v306/arenas26a.html.

Related Material