Dense Language Generation Made Simple: Deterministic, Randomized, and Multi-Order Algorithms

This paper studies language generation in the limit, where a generator receives a positive enumeration of an unknown language and must eventually produce only valid, previously unseen strings. It presents a unified framework with a simpler analysis for the optimal deterministic lower-density guarantee of 1/2. Against an oblivious adversary, randomization improves the optimal guarantee to 1-1/e. The framework also handles any finite collection of output orders simultaneously, achieving the optimal deterministic and randomized guarantees for every order without sacrificing coverage.