Non-Uniform Language Generation with Replay

In the framework of language generation in the limit introduced by KM24, an algorithm receives example strings from an unknown target language, which is chosen from a known collection of potential languages. The goal for the algorithm is to eventually generate only strings that belong to the target and have not appeared among the examples. The stronger notion of non-uniform generation requires correct generation after a finite number of distinct examples that may depend on the target language but not on its enumeration LRT25,CP25. RVS26 introduced a replay model in which the adversary can also provide the algorithm's previous outputs as examples, even when those outputs lie outside the target language. They showed that some countable collections cannot be non-uniformly generated with replay, and left finding a characterization as an open question. In this paper, we resolve this question by giving a complete characterization of non-uniform generation with replay for arbitrary collections over a countable universe. For countable collections, we obtain a simpler characterization: generation is possible if and only if, for each language $L$, every intersection of $L$ with finitely many other languages is either infinite or has size bounded by a constant depending only on $L$. Beyond determining whether non-uniform generation is possible, we characterize how many distinct inputs an algorithm needs before it must generate correctly. For any assignment of a positive integer $d(L)$ to each language $L$, we determine an exact characterization for when there exists an algorithm that generates correctly from every target $L$ once it has received at least $d(L)$ distinct inputs.