On Computational Hardness of Mistake-Bounded Language Generation: A Random-Oracle Query Separation

Xiaoyu Li, Andi Han, Dai Shi +2

Generation in the limit guarantees eventual generation for every countable collection of infinite languages in the model of Kleinberg and Mullainathan [KM24], while closure dimensi…