Language Generation: Complexity Barriers and Implications for 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.
Code (0)
등록된 구현이 없습니다.
Tasks
Language IdentificationSimilar Papers 제목 키워드 기반
Breaking the Programming Language Barrier: Multilingual Prompting to Empower Non-Native English Learners
Non-native English speakers (NNES) face multiple barriers to learning programming. These barriers can be obvious, such as the fact that programming language syntax and instruction are often in English, or more subtle, su…
Code GenerationBarriers to Discrete Reasoning with Transformers: A Survey Across Depth, Exactness, and Bandwidth
Transformers have become the foundational architecture for a broad spectrum of sequence modeling applications, underpinning state-of-the-art systems in natural language processing, vision, and beyond. However, their theo…
Generating Scientific Definitions with Controllable Complexity
Unfamiliar terminology and complex language can present barriers to understanding science. Natural language processing stands to help address these issues by automatically defining unfamiliar terms. We introduce a new ta…
RerankingGenerating Scientific Definitions with Controllable Complexity
Unfamiliar terminology and complex language can present barriers to understanding science. Natural language processing stands to help address these issues by automatically defining unfamiliar terms. We introduce a new t…
RerankingIntrinsic Barriers to Explaining Deep Foundation Models
Deep Foundation Models (DFMs) offer unprecedented capabilities but their increasing complexity presents profound challenges to understanding their internal workings-a critical need for ensuring trust, safety, and account…