language identification 2Borel maps 1computational traces 1Gold's model 1identification in the limit 1machine-independent learning 1succinct alphabets 1terminal coloring 1trace coloring 1transfinite recursion 1
From the 2 of 12 linked papers with an AI index.
Showing cs.CLShow all
3 papers · 1 filter
cs.CL2026
Language Identification with Succinct Machine-Independent Traces
Moses Charikar, Jon Kleinberg, Chirag Pabbaraju
The paper shows that language identification in the limit can be achieved using compact, machine‑independent computational traces that use only a small alphabet derived directly fr…
cs.CL2026
Globally Consistent Coloring Schemes for Language Identification
Moses Charikar, Jon Kleinberg, Chirag Pabbaraju
The paper shows that a single terminal bit attached to each example string is sufficient to identify any countable collection of infinite languages in Gold's language identificatio…
cs.CL2025
A Characterization of List Language Identification in the Limit
Moses Charikar, Chirag Pabbaraju, Ambuj Tewari
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…