Language Generation: Complexity Barriers and Implications for Learning

Marcelo Arenas, Pablo Barceló, Luis Cofré +1

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 g…