# A Characterization of List Language Identification in the Limit

arXiv: https://arxiv.org/abs/2511.04103 · HTML: https://mlsanity.com/paper/2511.04103/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 39 references that are in the map.
- First posted on arXiv 6 Nov 2025.

## Builds on (most cited first, 12 of 12)

- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians](https://mlsanity.com/paper/1711.07211/) (2017)
- [List-Decodable Linear Regression](https://mlsanity.com/paper/1905.05679/) (2019)
- [Language Generation in the Limit](https://mlsanity.com/paper/2404.06757/) (2024)
- [List Decodable Learning via Sum of Squares](https://mlsanity.com/paper/1905.04660/) (2019)
- [Generation through the lens of learning theory](https://mlsanity.com/paper/2410.13714/) (2024)
- [Exploring Facets of Language Generation in the Limit](https://mlsanity.com/paper/2411.15364/) (2024)
- [A Characterization of List Learnability](https://mlsanity.com/paper/2211.04956/) (2022)
- [List Online Classification](https://mlsanity.com/paper/2303.15383/) (2023)
- [Learning Algorithms in the Limit](https://mlsanity.com/paper/2506.15543/) (2025)
- [Near-tight closure bounds for Littlestone and threshold dimensions](https://mlsanity.com/paper/2007.03668/) (2020)
- [A Characterization of List Regression](https://mlsanity.com/paper/2409.19218/) (2024)

## Built on by (most cited first, 9 of 9)

- [Characterizing the Effect of Noise in Language Generation in the Limit](https://mlsanity.com/paper/2601.21237/) (2026)
- [An Optimal Sauer Lemma Over k-ary Alphabets](https://mlsanity.com/paper/2604.12952/) (2026)
- [Contrastive Identification and Generation in the Limit](https://mlsanity.com/paper/2605.06211/) (2026)
- [On the Price of Privacy for Language Identification and Generation](https://mlsanity.com/paper/2604.07238/) (2026)
- [On Language Generation in the Limit with Bounded Memory](https://mlsanity.com/paper/2605.30324/) (2026)
- [PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting](https://mlsanity.com/paper/2605.25678/) (2026)
- [Space-Efficient Language Generation in the Limit](https://mlsanity.com/paper/2606.25777/) (2026)
- [Language Identification with Succinct Machine-Independent Traces](https://mlsanity.com/paper/2607.12443/) (2026)
- [Hallucination Rates in Language Generation](https://mlsanity.com/paper/2607.23361/) (2026)

## Abstract (arXiv)

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 this task 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 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. We give an exact characterization of collections of languages that can be k-list identified in the limit, based on a recursive version of Angluin's characterization (for language identification with a list of size 1). This further leads to a conceptually appealing characterization: A language collection can be k-list identified in the limit if and only if the collection can be decomposed into k collections of languages, each of which can be identified in the limit (with a list of size 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-list identifiable in the limit, then the collection can be k-list identified at an exponential rate, and this is best possible. On the other hand, if a collection is not k-list identifiable in the limit, then it cannot be k-list identified at any rate that goes to zero.