A Characterization of List Language Identification in the Limit
Moses Charikar, Chirag Pabbaraju, Ambuj Tewari · 2025
Read A Characterization of List Language Identification in the Limit by Moses Charikar, Chirag Pabbaraju, Ambuj Tewari (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-04103.txt.
Introduction
Moses Charikar, Chirag Pabbaraju, and Ambuj Tewari characterize when a learner can identify a target language in the limit. The learner may offer a list of k guesses at each step instead of one. Gold showed single-guess identification fails for most interesting language families, and Angluin later pinned down exactly when it succeeds.
Their exact characterization rests on a recursive version of Angluin's condition, generalized to lists. A cleaner equivalent form also emerges for collections that can be list-identified. Allowing several guesses enlarges what can be learned in the limit, and the result maps that enlargement precisely, linking a classic learning theory question to recent progress on language generation.
Catalog record
| CREATOR | Moses Charikar, Chirag Pabbaraju, Ambuj Tewari |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 107 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-04103
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Characterization of List Language Identification in the Limit Moses Charikar, Chirag Pabbaraju, Ambuj Tewari Abstract We study the problem of language identification in the limit, where given a sequence of examples from a target language, the goal of the learner is to output a sequence of guesses for the target language such that all the guesses beyond some finite time are correct. Classical results of Gold showed that language identification in the limit is impossible for essentially any interesting collection of languages. Later, Angluin gave a precise characterization of language collections for which language identification is possible. Motivated by recent positive results for the related problem of language generation, we revisit the classic language identification problem in the setting where the learner is given the additional power of producing a list of k k guesses at each time step. The goal is to ensure that beyond some finite time, one of the guesses is correct at each time step. Such list learning versions of several basic learning problems have been widely studied. We give an exact characterization of collections of languages that can be k k -list identified in the limit, based on a recursive version of Angluin’s characterization (for language identification with a list of size 1 1 ). This further leads to a conceptually appealing characterization: A language collection can be k k -list identified in the limit if and only if the collection can be decomposed into k k collections of languages, each of which can be identified in the limit (with a list of size 1 1 ). We also use our characterization to establish rates for list identification in the statistical setting where the input is drawn as an i.i.d. stream from a distribution supported on some language in the collection. Our results show that if a collection is k k -list identifiable in the limit, then the collection can be k k -list identified at an exponential rate, and this is best possible. On the other hand, if a collection is not k k -list identifiable in the limit, then it cannot be k k -list identified at any rate that goes to zero. 1 Introduction Modeling language learning is a complex and multi-faceted task. This paper is concerned with the model of language identification in the limit proposed by Gold in his seminal work ( 17 ) . One of Gold’s motivations for considering such a model was to formalize the process of language acquisition in children. Viewed in a certain way, the language learning environment for children comprises of people around them constantly uttering valid sentences from a language, with few instances of negative examples. In this environment, a child supposedly infers a valid grammatical representation of the language, as the number of positive utterances increases. Moreover, linguistic studies indicate that children are rarely given feedback when they utter invalid sentences ( 8 ) , or are not fully receptive of it when they are ( 42 ; 31 ) . Thus, the learning environment would appear to comprise of a corpus of largely positive examples from the target language of interest, from which the child is supposed to infer a valid grammar for the language. The formal setup that Gold proposes to model this is as follows: there is a countable collection \mathcal{C}=(L_{1},L_{2},\dots) of languages, of which a certain language L_{z} is the target language of interest. The sentences, or “strings” in this language are enumerated to a learner in an online fashion, and in an arbitrary order. Concretely, the learner is provided a sequence x_{1},x_{2},\dots as input, and at every time step t , the learner guesses an index i_{t} based on the input it has seen so far. The learner is said to have identified the language L_{z} in the limit if beyond some finite time, all of its guesses i_{t} satisfy that L_{i_{t}}=L_{z} . If we think of the collection \mathcal{C} as comprising of different grammars for languages, then the criterion of identification in the limit is ensuring that the learner eventually acquires a valid grammar for the target language. We note that the input does not contain any negative examples that are outside the target language, and furthermore, the learner is never given any feedback about its guess being correct or not. The results established by Gold for when language identification in the limit is possible in this model are drastically negative. Gold showed that essentially any interesting collection of languages that contains an infinite language cannot be identified in the limit. In particular, this rules out most formal language families of interest like regular languages, context-free languages, etc. Later follow-up work by Angluin ( 1 ; 2 ) established a precise characterization of collections that may be identified in the limit. Namely, Angluin identified a strict combinatorial condition that must be satisfied by a collection for it to be identifiable in the limit, giving justification for why most formal language collections are not identifiable. In contrast to these classical negative results, the recent work of Kleinberg and Mullainathan ( 28 ) establishes surprisingly general positive results for a slightly different task of language generation in the limit. In this model, instead of making a guess i_{t} of the identity of the target language at every time step, the learner is tasked with generating a string z_{t} . The learner successfully generates in the limit, if beyond some finite time, the string z_{t} generated by the learner belongs to the target language L_{z} , and is not one of the input strings x_{1},\dots,x_{t} it has seen so far. 28 showed that this modified success criterion can be achieved for every countable collection of languages! Such a strong positive result for generation in the limit motivates revisiting Gold’s model for language identification in the limit, and asking: Could the strong negative results in the model be circumvented if we consider slightly more relaxed notions of identification in the limit? Motivated by this question, in this work, we consider the setting of language identification in the limit, where instead of making a single guess at every time step, the learner may make a short list of at most k guesses. We will deem the learner to have successfully k -list identified the target language L_{z} in the limit, if beyond some finite time, every list of guesses output by the learner contains an index i such that L_{i}=L_{z} . This is a natural way to impose a slightly weaker desideratum on the learner: of its k guesses, we merely require that at least one is correct. In fact, this formulation of “learning with a list” has received considerable attention in the literature for various natural learning problems (see Section 1.2 ). 1.1 Main Results As noted above, Angluin ( 2 ) provided a precise characterization of language collections that are identifiable in the limit. This characterization requires every language in the collection to have a finite tell-tale set which distinguishes it from every other language that is a proper subset of it. As our first main contribution, we present a tell-tale condition ( Section 4 ) which we term the k -Angluin condition , that precisely characterizes k