Language Generation with Feedback: Queries and Mistakes

This paper introduces a theoretical framework for language generation in the limit, exploring how machines can learn to produce valid, unseen strings from a target language through various forms of feedback. The authors specifically investigate two models: mistake feedback, where a generator learns if its prior output was incorrect, and query feedback, where the generator can actively ask if specific strings belong to the target language. A central contribution of the research is the identification of countable inner-covers as the definitive combinatorial property that determines whether a collection of languages can be successfully generated under these feedback conditions. The...