A Characterization of List Language Identification in the Limit

• URL: http://arxiv.org/abs/2511.04103v1
• Date: Thu, 06 Nov 2025 06:39:20 GMT
• Title: A Characterization of List Language Identification in the Limit
• Abstract summary: We study the problem of language identification in the limit, where given a sequence of examples from a target language.<n>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.<n>We give an exact characterization of collections of languages that can be $k$-list identified in the limit.
• Score: 31.38302438096483
• License: http://creativecommons.org/licenses/by/4.0/
• 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 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.

Related papers

• Language Identification with Succinct Machine-Independent Traces [10.036312061637764]
  We show how to define computational traces that enable identification in the limit.<n>We show how to define traces using an alphabet of tokens that is linear in the size of the alphabet that the languages are defined over.
  arXiv  Detail & Related papers  (2026-07-14T07:18:07Z)
• On Language Generation in the Limit with Bounded Memory [17.70989972580602]
  We study language generation in the limit under bounded memory.<n>In this task, a learner observes examples from an unknown target language one at a time and must eventually output only new valid examples.
  arXiv  Detail & Related papers  (2026-05-28T17:57:03Z)
• Differentially Private Language Generation and Identification in the Limit [17.31852533022177]
  We study the study of language generation in the limit, a model recently introduced by Kleinberg and Mullainathan [KM24], under the constraint of differential privacy.<n>We provide an $varepsilon$-differentially-private algorithm that generates in the limit from any countable collection.<n>We prove that no $varepsilon$-DP algorithm can identify a collection containing two languages with an infinite intersection and a finite set difference.
  arXiv  Detail & Related papers  (2026-04-09T17:48:46Z)
• Density Measures for Language Generation [2.2872032473279065]
  We study the trade-off between validity and breadth of language generation algorithms.<n>Existing algorithms for language generation in the limit produce output sets that can have zero density in the true language.<n>We show, however, that we provide an algorithm for language generation in the limit whose outputs have strictly positive density in $K$.
  arXiv  Detail & Related papers  (2025-04-19T18:08:18Z)
• Exploring Facets of Language Generation in the Limit [10.18252143035175]
  We show that every countable language collection has a generator which has the stronger property of non-uniform generation in the limit.<n>We formalize the tension between validity and breadth in the generation algorithm of [KM24] by introducing a definition of exhaustive generation.<n>We also provide a precise characterization of the language collections for which exhaustive generation is possible.
  arXiv  Detail & Related papers  (2024-11-22T22:13:40Z)
• On the Limits of Language Generation: Trade-Offs Between Hallucination and Mode Collapse [26.73254784599135]
  Given samples from an unknown language, a language model should produce valid strings not seen in training.<n>Otherwise, outputting invalid strings constitutes "hallucination," and failing to capture the full range leads to "mode collapse"<n>We investigate this within a statistical language generation setting building on Gold and Angluin.
  arXiv  Detail & Related papers  (2024-11-14T18:06:55Z)
• Language Generation in the Limit [0.7787343335258782]
  We show that there is an agent that is able to generate in the limit for every countable list of candidate languages. This contrasts dramatically with negative results due to Gold and Angluin in a well-studied model of language learning.
  arXiv  Detail & Related papers  (2024-04-10T05:53:25Z)
• AdaCCD: Adaptive Semantic Contrasts Discovery Based Cross Lingual Adaptation for Code Clone Detection [69.79627042058048]
  AdaCCD is a novel cross-lingual adaptation method that can detect cloned codes in a new language without annotations in that language. We evaluate the cross-lingual adaptation results of AdaCCD by constructing a multilingual code clone detection benchmark consisting of 5 programming languages.
  arXiv  Detail & Related papers  (2023-11-13T12:20:48Z)
• Improving Cross-Lingual Transfer through Subtree-Aware Word Reordering [17.166996956587155]
  One obstacle for effective cross-lingual transfer is variability in word-order patterns. We present a new powerful reordering method, defined in terms of Universal Dependencies. We show that our method consistently outperforms strong baselines over different language pairs and model architectures.
  arXiv  Detail & Related papers  (2023-10-20T15:25:53Z)
• Soft Language Clustering for Multilingual Model Pre-training [57.18058739931463]
  We propose XLM-P, which contextually retrieves prompts as flexible guidance for encoding instances conditionally. Our XLM-P enables (1) lightweight modeling of language-invariant and language-specific knowledge across languages, and (2) easy integration with other multilingual pre-training methods.
  arXiv  Detail & Related papers  (2023-06-13T08:08:08Z)
• Inducing Language-Agnostic Multilingual Representations [61.97381112847459]
  Cross-lingual representations have the potential to make NLP techniques available to the vast majority of languages in the world. We examine three approaches for this: (i) re-aligning the vector spaces of target languages to a pivot source language; (ii) removing language-specific means and variances, which yields better discriminativeness of embeddings as a by-product; and (iii) increasing input similarity across languages by removing morphological contractions and sentence reordering.
  arXiv  Detail & Related papers  (2020-08-20T17:58:56Z)
• XCOPA: A Multilingual Dataset for Causal Commonsense Reasoning [68.57658225995966]
  Cross-lingual Choice of Plausible Alternatives (XCOPA) is a typologically diverse multilingual dataset for causal commonsense reasoning in 11 languages. We evaluate a range of state-of-the-art models on this novel dataset, revealing that the performance of current methods falls short compared to translation-based transfer.
  arXiv  Detail & Related papers  (2020-05-01T12:22:33Z)
• On the Importance of Word Order Information in Cross-lingual Sequence Labeling [80.65425412067464]
  Cross-lingual models that fit into the word order of the source language might fail to handle target languages. We investigate whether making models insensitive to the word order of the source language can improve the adaptation performance in target languages.
  arXiv  Detail & Related papers  (2020-01-30T03:35:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.