Sharp Half-Density Language Generation with Self-Replay Using Membership Queries

Abstract

We study language generation from a complete enumeration of an unknown member of a countable family of infinite languages, when the input stream may also replay any earlier output, including erroneous outputs. We prove that a single deterministic oracle algorithm, using only membership queries to the candidate languages, eventually generates correctly and achieves lower asymptotic density at least 1/2 in the target language. Every round terminates after finitely many queries, and all outputs are distinct and absent from the input history. The construction permanently reserves a set of tail counterexamples that has relative density zero in every candidate. These protected examples make a finite-prefix fallback search eventually correct under replay. An oracle-computable partial pairing supplies the density guarantee, while its two-element components prevent unbounded propagation of erroneous outputs. The matching upper bound holds even for a known target and a clean complete enumeration. Thus the optimal universal density guarantee remains exactly 1/2 under self-replay with candidate-membership access. The density concerns the eventual output set in a fixed domain order; no uniform running-time or convergence-time bound is asserted.