Search papers, labs, and topics across Lattice.
This paper explores the potential of succinct machine-independent traces for language identification, addressing limitations of previous models that relied on large automata-theoretic frameworks. By defining computational traces directly from the languages themselves and using a small alphabet, the authors demonstrate that positive identification results can be achieved without the need for complex underlying machine models. The findings reveal that these traces, which are linear in size relative to the language's alphabet, significantly enhance the learning process in language identification tasks.
Small, machine-independent traces can revolutionize language identification by enabling effective learning without complex automata.
Motivated by the power of large language models, there has been renewed interest in the Gold-Angluin model of language identification in the limit, with an eye toward variants of the model that might overcome the negative results for its original formulation. Recent papers on this question have proposed looking at computational traces and annotations of training strings as a source of additional power for a learner, reflecting empirical regularities such as the way that commented source code is easier to learn from than arbitrary source code, and text annotated with algorithmically generated chain-of-thought tokens can be easier to learn from than the raw text itself. This recent work has shown positive results for language identification in the presence of such computational traces, but the traces in these positive results come from explicit automata-theoretic machine models that generate the language, where the underlying vocabulary of tokens for the traces is very large. In this paper, we address two fundamental issues left open by this line of work: can we achieve positive results with traces that use only a small alphabet, and can we define traces directly from the language itself, without requiring an underlying machine model that generates it? We establish positive results for both of these questions: for an arbitrary collection of languages, we show how to define computational traces that enable identification in the limit, using an alphabet of tokens that is linear in the size of the alphabet that the languages are defined over, and independent of any other properties of the languages.
