Language Identification with Succinct Machine-Independent Traces

arXiv cs.CL · 18 hours ago

Researchers developed a method for language identification in the limit using computational traces with small alphabets, without requiring an underlying machine model to generate the languages. The alphabet size is linear in the size of the language alphabet, addressing two open questions about whether traces could work with limited vocabularies and be defined directly from languages themselves. This enables learners to identify formal languages more efficiently by using succinct annotations similar to how commented code or chain-of-thought tokens improve machine learning from text.