Language Generation and Identification from Partial Enumeration: Tight Density Bounds and Topological Characterizations

The recent successes of large language models (LLMs) have led to active lines of work in formal theories of language generation and learning. We build on one such theory, language generation in the limit, in which an adversary enumerates the strings of an unknown language K drawn from a countable list of candidate languages, and an algorithm tries to generate unseen strings from the language. Initial work on this model showed there is an algorithm that can always succeed at this task, and more recent work has shown there is in fact an algorithm that can produce a positive-density subset of the language. These results on density reflect the validity-breadth tension in language generation: the trade-off between generating only valid strings while also achieving wide coverage of the true language. Here we begin by resolving one of the main open questions from this work on density, establishing a tight bound of 1/2 on the best achievable lower density of any algorithm. We then consider a more powerful adversary, capturing the fact that generation algorithms may typically be faced with an environment in which only a subset of the language is being produced. This is a model with only partial enumeration of K: We show that there is an algorithm with the property that if an adversary only outputs an infinite subset C of the true language K, it can still achieve language generation in the limit; and moreover, if the subset C has lower density α in K, then the algorithm produces a subset of lower density at least α/2, which matches the upper bound. This generalizes the tight density bound of 1/2 to the case where the algorithm must come within 1/2 of the density of whichever subset of K the adversary reveals. We also revisit the classical Gold-Angluin model of language identification (rather than generation) when the adversary need only partially enumerate an infinite subset C of the true language K. We characterize when it is possible for an algorithm to achieve the natural analogue of identification in the limit in this partial setting, producing languages Mt (and finite representations of them) such that eventually C C M C K. Our characterization builds on our earlier topological approach on density in language generation [], and in the process we give a new topological formulation of Angluin's characterization for language identification in the limit, showing that her condition is precisely equivalent to some appropriate topological space having the TD separation property.