Language Identification with Succinct Machine-Independent Traces

# Language Identification with Succinct Machine-Independent Traces
Source: [https://arxiv.org/html/2607.12443](https://arxiv.org/html/2607.12443)
\\coltauthor\\Name

Moses Charikar\\Emailmoses@cs\.stanford\.edu \\addrStanford University and\\NameJon Kleinberg\\Emailkleinberg@cornell\.edu \\addrCornell University and\\NameChirag Pabbaraju\\Emailcpabbara@cs\.stanford\.edu \\addrStanford University

###### Abstract

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 atcomputational tracesandannotationsof 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\.

###### keywords:

language models, identification in the limit, computational traces

## 1Introduction

The success of large language models has motivated several lines of recent work exploring theoretical models that might provide insight into how they are achieving strong performance from the types of training data and training pipelines that they are built from\. One direction this research has taken has been to start from a classical model of Gold onlanguage identification in the limit\(Gold,[1967](https://arxiv.org/html/2607.12443#bib.bib5)\), in which we view the language learning task as a game played between an adversary and an algorithm: the adversary thinks of a secret languageKKknown only to come from a countable list of candidatesL1,L2,L3,…L\_\{1\},L\_\{2\},L\_\{3\},\.\.\.; the adversary enumerates the strings ofKKin an arbitrary order111A valid enumerationx1,x2,…x\_\{1\},x\_\{2\},\\dotsofKKsatisfies: \(1\)xi∈Kx\_\{i\}\\in K, for allii, and \(2\)∀x∈K\\forall x\\in K, there existsiisuch thatxi=xx\_\{i\}=x\.; in each stepttthe algorithm guesses the indexiti\_\{t\}of the true language; and the algorithm wins the game \(it hasidentifiedKKin the limit\) if for some timet∗t^\{\*\}, and allt≥t∗t\\geq t^\{\*\}, we haveLit=KL\_\{i\_\{t\}\}=K— the algorithm is correct in every step beginning witht∗t^\{\*\}\.

The main results in Gold’s framework, beginning with Gold’s original theorem about his model, are negative\(Gold,[1967](https://arxiv.org/html/2607.12443#bib.bib5)\); for all but highly constrained families of languages \(much more restricted than the class of regular languages\), the algorithm cannot win this game\(Angluin,[1980](https://arxiv.org/html/2607.12443#bib.bib1)\)\. Yet real language models seem much more powerful than what these sweeping negative results suggest, and so the question has turned to finding reasonable variations on this model in which we are able to obtain positive results more consistent with the successes we see in practice\.

#### Computational traces\.

One promising line of recent work has explored the power ofannotationorcomputational tracesin helping solve the problem of language identification in the limit\(Papazov and Flammarion,[2025](https://arxiv.org/html/2607.12443#bib.bib7); Bhattamishra et al\.,[2026](https://arxiv.org/html/2607.12443#bib.bib2); Peng et al\.,[2026](https://arxiv.org/html/2607.12443#bib.bib8)\)\. These models are motivated by the observation that training corpora often contains text or sequence data that is enriched by some kind of meta\-data, thinking traces, or domain\-relevant annotation\. This can include cases in which the data itself has this type of supporting information, as in the way that learning from corpora of source code can be more effective if the code is commented, or learning from corpora of mathematics can be more effective if the proofs contain step\-by\-step arguments\. It also includes cases in which the data has been annotated algorithmically, as in the success ofchain\-of\-thoughtand related methods\(Wei et al\.,[2022](https://arxiv.org/html/2607.12443#bib.bib10)\)\. This range of examples suggests that learners can be more effective on a corpus of training data if that data is annotated with some kind of computational trace\.

These recent models have begun from the assumption that there is an automata\-theoretic underpinning for the candidate languages — for example, that they are produced by an unknown finite\-state machine, pushdown automaton, or Turing machine — and that the annotation in question is produced from the computational trace of the machine itself\. Prior work obtains possibility results with this approach\. This line of work leaves open two fundamental classes of questions, however\. First, the kind of annotation they describe is fine\-grained and expansive: in one case it is represented in terms of the states of the underlying machine\(Peng et al\.,[2026](https://arxiv.org/html/2607.12443#bib.bib8)\), and in the other case it is represented by the power\-set of the vocabulary, with an exponential blow\-up as a result\(Bhattamishra et al\.,[2026](https://arxiv.org/html/2607.12443#bib.bib2)\)\. Second, the premise of these models is that annotation is directly tied to the automaton that produced the language; it leaves open the question of how we might usefully annotate for identification when we have no access to the underlying machine models\.

In contrast, the kinds of annotations or computational trace we see in practice tend not to come from an underlying machine model, but tend to be more designed as objects in their own right, with their own vocabularies, and much coarser than the full state set of the machine architecture\. For example, in commented code, it is the comments that form the additional tokens helping learn the corpus; and with chain\-of\-thought, it is the thinking tokens that provide this help\. Neither of these corresponds to the state of the underlying machine that produced the training data, to the extent that there is such a machine at all\. What would a theory of computational traces look like if we take the tokens in the trace to have this coarse\-grained structure, and independent of any specific machine model? Could we still obtain possibility results for language identification in the limit?

#### The present work: Compact, machine\-independent traces\.

In this paper, we develop such a theory, and we show that annotation with a small set of tokens — independent of the size of the state set of the underlying machine — is sufficient to achieve language identification in the limit\. Moreover, our construction of the annotation works at the level of the language itself, and does not assume knowledge of any underlying machine producing the language\.

We will describe the model in detail in the subsequent sections, but we begin here with a high\-level overview of it\. As a starting point, let’s consider how earlier machine\-based models defined computational traces in the case of a finite automaton: as the automaton processed the string one symbol at a time, from left to right, the trace reported the state of the automaton at each symbol\. This kind of trace has the property ifx=x1​x2​…​xnx=x\_\{1\}x\_\{2\}\\ldots x\_\{n\}is the input string, then the trace annotates each input symbolxix\_\{i\}with an annotation symbolcic\_\{i\}\(corresponding to the state of the automaton at that point\); and becausecic\_\{i\}is the state, it depends only on the prefixx1​x2​…​xix\_\{1\}x\_\{2\}\\ldots x\_\{i\}up to that point, and not any subsequent symbols\.

We use this as the defining property of our traces: we say that atrace coloring functionccover a finite set of colorsPP\(the “palette”\) is a function that maps finite strings to elements ofPP, and we define thecolor traceof a stringx=x1​x2​…​xnx=x\_\{1\}x\_\{2\}\\ldots x\_\{n\}to be the value ofccapplied to each of its prefixes:

tracec​\(x\):=\(c​\(ε\),c​\(x≤1\),c​\(x≤2\),…,c​\(x≤n\)\)\\displaystyle\{\\mathrm\{trace\}\}\_\{c\}\(x\):=\(c\(\\varepsilon\),c\(x\_\{\\leq 1\}\),c\(x\_\{\\leq 2\}\),\\dots,c\(x\_\{\\leq n\}\)\)\(1\)wherex≤ix\_\{\\leq i\}denotes the prefixx1​x2​…​xix\_\{1\}x\_\{2\}\\ldots x\_\{i\}andε\\varepsilondenotes the empty string\. A coloring ofxxby the states of a finite automaton that produces it is one way to produce such a trace coloring, but our definition here makes clear that we can define this object as an annotation scheme for any language, even if we don’t know the underlying machine model, or even if there isn’t one\. \(This is the same sense in which comments or thinking tokens can annotate a string in a training corpus even though they don’t correspond in any respect to the generative mechanism that originally produced the string\.\)

#### Identification using traces\.

We would like to achieve identification in the limit using these traces, and further, with small palettes, so that we do not need to provide annotations using voluminous alphabets like fine\-grained state sets\. Formally, given an instance of language identification in the limit with candidate languagesL1,L2,L3,…L\_\{1\},L\_\{2\},L\_\{3\},\\ldots, we consider a process in which each languageLiL\_\{i\}is first annotated by its own trace coloring functioncLic\_\{L\_\{i\}\}, and then an adversary enumerates the stringsx∈Kx\\in K, each as an annotated pair consisting ofxxand its color trace,\(x,tracecK​\(x\)\)\(x,\{\\mathrm\{trace\}\}\_\{c\_\{K\}\}\(x\)\)\.

Is this sufficient to enable language identification in the limit, even with no underlying machine model? We show that it is: there is an algorithm𝒜\\mathcal\{A\}such that for any collection of candidate languagesL1,L2,L3,…L\_\{1\},L\_\{2\},L\_\{3\},\\ldots, there exists a choice of trace coloringscL1,cL2,cL3,…c\_\{L\_\{1\}\},c\_\{L\_\{2\}\},c\_\{L\_\{3\}\},\\ldotsfor which𝒜\\mathcal\{A\}is able to achieve identification in the limit when presented with the ordered pairs\(x,tracecK​\(x\)\)\(x,\{\\mathrm\{trace\}\}\_\{c\_\{K\}\}\(x\)\)arising from an enumeration of the adversary’s languageKK\.

Moreover, the trace colorings required can be constructed using very few colors: for problem instances with an alphabet of sizekk, there is an algorithm that achieves this using trace colorings with palettes of size at mostk\+1k\+1\. Even in the case where the languages come from an underlying machine model, this is a bound that is independent of the number of states of these machines, which must grow unboundedly for an infinite family of languages\. As such, it is a much more resource\-efficient construction of computational traces — and one that applies much more broadly — than the computational traces proposed by earlier approaches\.

We prove this result by establishing an exact combinatorial characterization of when a trace coloring permits identification in the limit, and we relax this to a related sufficient condition for identification that we show how to achieve\. This sufficient condition has interesting combinatorial interpretations in its own right, and we show matching upper and lower bounds for this condition in the case of languages over a binary alphabet \(whenk=2k=2\): our result shows how to achieve the required condition withk\+1=3k\+1=3colors, and we prove that 2 colors are not sufficient\.

We explore further extensions of our result, including the fact that identification in the limit is still possible \(using a larger palette\) when the trace can be corrupted to a bounded extent; and the fact that when the candidate languagesL1,L2,L3,…L\_\{1\},L\_\{2\},L\_\{3\},\\ldotsare regular, we can achieve identification in the limit with trace coloring functions that use only two colors\.

### 1\.1Main Results

Given a language collection222All languages in the collection are assumed to be non\-empty\.𝒞\\mathcal\{C\}, our objective is to associate every languageLLin𝒞\\mathcal\{C\}with a suitable trace coloring functioncLc\_\{L\}, such that when everyx∈Lx\\in Lis accompanied withtracecL​\(x\)\{\\mathrm\{trace\}\}\_\{c\_\{L\}\}\(x\), the collection𝒞\\mathcal\{C\}becomes identifiable in the limit\. Towards this, as our first contribution, we derive an exact characterization of when identification in the limit is possible with color traces\. Our characterization is structurally similar to Angluin’s condition\(Angluin,[1980](https://arxiv.org/html/2607.12443#bib.bib1)\)for identification in the limit, but additionally takes into account the color traces seen in the input; the proof is given in\\Crefsec:characterization\-appendix\.

###### Theorem 1\.1\(Characterization of Identification in the Limit with Color Traces\)\.

Let𝒞\\mathcal\{C\}be a countable language collection\. Then,𝒞\\mathcal\{C\}is identifiable in the limit with a color trace given by the trace coloring functions\{cL\}L∈𝒞\\\{c\_\{L\}\\\}\_\{L\\in\\mathcal\{C\}\}if and only if for every languageL∈𝒞L\\in\\mathcal\{C\}, there exists a finite “tell\-tale” subsetTL⊆LT\_\{L\}\\subseteq L, such that for every languageL′∈𝒞L^\{\\prime\}\\in\\mathcal\{C\}that is a proper subset ofLL, either \(1\)L′L^\{\\prime\}does not containTLT\_\{L\}, or \(2\) there existsx∈L′x\\in L^\{\\prime\}such thattracecL′​\(x\)≠tracecL​\(x\)\{\\mathrm\{trace\}\}\_\{c\_\{L^\{\\prime\}\}\}\(x\)\\neq\{\\mathrm\{trace\}\}\_\{c\_\{L\}\}\(x\)\.

The characterization above gives a precise objective for constructing trace coloring functions\{cL\}L∈𝒞\\\{c\_\{L\}\\\}\_\{L\\in\\mathcal\{C\}\}\. Perhaps surprisingly, our next result, which is one of the main structural results of the paper, shows that for every language collection, we can construct trace coloring functions that use a small palette, and have the stronger property that theyalwayssatisfy requirement \(2\) above\.

###### Lemma 1\.2\(Coloring Lemma\)\.

Let𝒞\\mathcal\{C\}be a language collection over a finite alphabetΣ\\Sigmaof sizekk\. There exist trace coloring functions\{cL\}L∈𝒞\\\{c\_\{L\}\\\}\_\{L\\in\\mathcal\{C\}\}mapping to a palettePPof sizek\+1k\+1, that satisfy the following “distinguishable coloring condition”: for everyL,L′∈𝒞L,L^\{\\prime\}\\in\\mathcal\{C\}that satisfyL⊊L′L\\subsetneq L^\{\\prime\}, there existsx∈Lx\\in Lfor whichtracecL​\(x\)≠tracecL′​\(x\)\{\\mathrm\{trace\}\}\_\{c\_\{L\}\}\(x\)\\neq\{\\mathrm\{trace\}\}\_\{c\_\{L^\{\\prime\}\}\}\(x\)\.

We also show that our trace coloring functions use an optimal palette size for the purposes of satisfying the distinguishable coloring condition over a binary alphabet \(\\Crefprop:2\-coloring\-lower\-bound\-for\-sufficient\-condition\): namely, there exists a \(finite\) language collection over a binary alphabet for which any set of trace coloring functions that satisfies the distinguishable coloring condition necessarily requires three colors\.

Given that our trace coloring functions ensure that requirement \(2\) of the characterizing condition in\\Crefthm:characterization\-identification\-with\-traces always holds, tell\-tale sets are not needed and we get our main result:

###### Theorem 1\.3\(Identification in the Limit withk\+1k\+1Colors\)\.

Let𝒞\\mathcal\{C\}be a countable language collection over a finite alphabetΣ\\Sigmaof sizekk\. There exist trace coloring functions\{cL\}L∈𝒞\\\{c\_\{L\}\\\}\_\{L\\in\\mathcal\{C\}\}mapping to a palettePPof sizek\+1k\+1that make𝒞\\mathcal\{C\}identifiable in the limit with color traces\.

In order to specify a trace coloring function for a language, in general, one needs to specify the color that it maps every string in the universe to\. However, our trace\-coloring functions from\\Crefthm:main\-theorem above have a particularly special structure forregular languagecollections\. Concretely, consider a regular languageLL, and letMMbe any finite automaton that recognizesLL\. Denote its set of states byQ​\(M\)Q\(M\)\. For any stateqqinQ​\(M\)Q\(M\), all strings that arrive at this stateqq\(starting from the initial state\) are assigned the same color by our state coloring functioncLc\_\{L\}for languageLL\. Now, associate the stateqqwith this common color\. Then, for anyx∈Lx\\in L, the sequence of colors associated with the sequence of states it traverses inMMwould exactly equal the color trace generated by our trace coloring function onxx\. Thus, for a regular language, our trace coloring functionscLc\_\{L\}can be described very compactly, by simply specifying the unique color associated with every state in any automaton recognizingLL\.

This structural property of our trace coloring functions motivates studying a natural class of trace coloring functions that come from directly coloring thestatesof automata for regular languages — we denote these asstate coloring functions\. Concretely, a state coloring functioncMc\_\{M\}maps every state inQ​\(M\)Q\(M\)to a palettePP\. DenotingL​\(M\)L\(M\)to be the regular language recognized byMM, everyx∈L​\(M\)x\\in L\(M\)has a well\-definedstate color traceassociated with it: ifxxtraverses the sequence of statesq0,…,q\|x\|q\_\{0\},\\dots,q\_\{\|x\|\}inMM, then the state color trace is simply

tracecM​\(x\):=\(cM​\(q0\),…,cM​\(q\|x\|\)\)\.\\displaystyle\{\\mathrm\{trace\}\}\_\{c\_\{M\}\}\(x\):=\(c\_\{M\}\(q\_\{0\}\),\\dots,c\_\{M\}\(q\_\{\|x\|\}\)\)\.\(2\)The work ofPeng et al\. \([2026](https://arxiv.org/html/2607.12443#bib.bib8)\)andBhattamishra et al\. \([2026](https://arxiv.org/html/2607.12443#bib.bib2)\)can be viewed in this framework \(see Section[1\.2](https://arxiv.org/html/2607.12443#S1.SS2)for a discussion\)\. For the computational traces used byPeng et al\. \([2026](https://arxiv.org/html/2607.12443#bib.bib8)\), the ‘color’ of a state is the name of the state itself\. Our notion is a coarsening of this state information\.

With this definition \([2](https://arxiv.org/html/2607.12443#S1.E2)\), we can now study the distinguishable coloring condition for any given collection𝒞=\{M1,M2,…\}\\mathcal\{C\}=\\\{M\_\{1\},M\_\{2\},\\dots\\\}of finite automata\. By the reasoning above, we can show that state coloring functions derived from our trace coloring functions satisfy the condition withk\+1k\+1colors\. Recall that for arbitrary language collections, we could show that our trace coloring functions achieved an optimal palette size for the distinguishable coloring condition only in the case of a binary alphabet\. Interestingly, for arbitraryautomatoncollections, we show thatk\+1k\+1is the optimal palette size achievable by state coloring functions for the distinguishable coloring condition for any alphabet sizekk\.

###### Lemma 1\.4\(State Coloring Lemma\)\.

Let𝒞\\mathcal\{C\}be an automata collection over an alphabet of sizekk\. There exist state coloring functions\{cM\}M∈𝒞\\\{c\_\{M\}\\\}\_\{M\\in\\mathcal\{C\}\}mapping to a palettePPof sizek\+1k\+1, such that for anyM,M′∈𝒞M,M^\{\\prime\}\\in\\mathcal\{C\}that satisfyL​\(M\)⊊L​\(M′\)L\(M\)\\subsetneq L\(M^\{\\prime\}\), there existsx∈L​\(M\)x\\in L\(M\)for whichtracecM​\(x\)≠tracecM′​\(x\)\{\\mathrm\{trace\}\}\_\{c\_\{M\}\}\(x\)\\neq\{\\mathrm\{trace\}\}\_\{c\_\{M^\{\\prime\}\}\}\(x\)\. Moreover, for anykk, there exists a collection of automata over an alphabet of sizekksuch that any set of state coloring functions requiresk\+1k\+1colors to satisfy this condition\.

\\Cref

lemma:state\-coloring\-optimal\-bound above is primarily about the tightness ofk\+1k\+1colors for state coloring functions to satisfy the distinguishable coloring condition for any given collection of automata\. We now return to our main question of identification in the limit with arbitrary trace coloring functions, but for the special class of regular language collections\. In particular, we ask: what is the optimal palette size necessary for these collections? Instead of the general\-purpose trace coloring functions given by\\Crefthm:main\-theorem, which usek\+1k\+1colors, can we perhaps use different trace coloring functions that use fewer colors? Our final result shows that any collection of regular languages, where every language is infinite, is in fact identifiable in the limit using onlytwo colors\!

###### Theorem 1\.5\(Two Colors Suffice for Identifying Regular Languages\)\.

Let𝒞=\{L1,L2,…\}\\mathcal\{C\}=\\\{L\_\{1\},L\_\{2\},\\dots\\\}be a countable collection of regular languages, where everyLiL\_\{i\}is infinite\. Then,𝒞\\mathcal\{C\}is identifiable in the limit with color traces given by trace coloring functions\{cL\}L∈𝒞\\\{c\_\{L\}\\\}\_\{L\\in\\mathcal\{C\}\}that use just two colors\.

We note that a palette size of two is optimal above, since using a single color is equivalent to having no trace information, and we know by Gold’s results that there are simple regular language collections, where every language is infinite, that are not identifiable in the limit without any traces\.

Finally, we also study identification in the limit with traces that are potentially corrupted \(\\Crefsec:corruptions\); in this setting, we derive arobustversion of the coloring lemma, and analogously show optimality of the palette size in the case of state coloring functions for regular languages\.

We note that our primary focus in this paper is information\-theoretic\. Namely, for our upper bounds for identification, we seek to specify a function that maps inputs and color traces to a guess for the target language\. Nevertheless, for implementing the identification algorithm of\\Crefthm:main\-theorem, we would require access to the coloring functionscLc\_\{L\}for every languageLLin the collection, and the ability to determine membership of any stringxxin any languageLLin the collection\.

### 1\.2Related Work

We discuss two recent works most closely related to our work, that demonstrate the power of annotation or computational traces for language identification\.

Peng et al\. \([2026](https://arxiv.org/html/2607.12443#bib.bib8)\)take a machine\-centric view, studying identification for languages accepted by a particular machine model \(deterministic finite automata, deterministic push down automata, and Turing machines\)\. For a machineMMand inputxx, they considerxxaugmented by a computational trace given by the sequence of computational steps ofMMonxx\. In the case of a DFADD, the computational trace is simply the sequence of states visited byDDwhile processing inputxx\. In the case of a Turing machineMM, the computational trace is the sequence of ‘states’ of the Turing machine while processingxx, where each ‘state’ includes the state of the finite state control, but also the contents of the memory tape, the position of the head, and so on\. Given an enumeration of inputs accepted by machineMM, augmented by their computational traces, they show that one can converge to the correct representation ofMM, and hence identify the language accepted byMM\. We note that this notion of computational traces requires very detailed, fine\-grained information to facilitate language identification\. The computational trace for inputxxcan be significantly longer thanxx\. They also study the question of robust identification, i\.e\., language identification from corrupted traces, establishing results in different error regimes\.

Another recent work\(Bhattamishra et al\.,[2026](https://arxiv.org/html/2607.12443#bib.bib2)\)also takes a machine\-centric view, studying learnability of regular languages in the Next Symbol Prediction \(NSP\) setting\. Here, the learner receives strings from the language, as well as rich annotation for every prefix of the string: whether the prefix belongs to the language, and which next symbols can lead to a string in the language, i\.e\.,k\+1k\+1bits for alphabet sizekk\. They show that this annotation is information\-theoretically sufficient to identify minimal DFAs; however the problem of improper learning remains computationally intractable\. We note that the annotation considered in this work is closely related to, but significantly richer that the annotation we use in our work\. If the input alphabet is of sizekk, each prefix of the input string is annotated with a symbol from an alphabet size of2k\+12^\{k\+1\}\. In contrast to our work, this work is focussed on regular languages\. Much of their focus is on computationally efficient learning – an issue that we \(mostly\) do not study in our work\.

## 2Background and Motivating Examples

Language identification with a color trace can be related to language identification with alist\(Charikar, Pabbaraju, and Tewari,[2025](https://arxiv.org/html/2607.12443#bib.bib3)\), where the algorithm guesses a list ofkklanguages at every step, and the algorithm identifies in the limit if the list eventually always contains the target language\. In particular,Charikar et al\. \([2025](https://arxiv.org/html/2607.12443#bib.bib3), Theorem 2\)shows that a language collection𝒞\\mathcal\{C\}is identifiable in the limit with a list of sizekkif and only if it can be expressed as a union ofkkcollections,eachof which is identifiable in the limit with a single guess\. By this characterization, any collection𝒞\\mathcal\{C\}that iskk\-list identifiable decomposes as𝒞=∪i=1k𝒞i\\mathcal\{C\}=\\cup\_\{i=1\}^\{k\}\\mathcal\{C\}\_\{i\}, where each𝒞i\\mathcal\{C\}\_\{i\}is identifiable\. In this case, we can assign a constant color trace corresponding to a unique coloriito every language in𝒞i\\mathcal\{C\}\_\{i\}\. Then, the color traces seen along with the input reveal the specific𝒞i\\mathcal\{C\}\_\{i\}that the target languageKKbelongs to\. Once this is known, one can simply apply any known algorithm that identifies in the limit to the collection𝒞i\\mathcal\{C\}\_\{i\}; since𝒞i\\mathcal\{C\}\_\{i\}is identifiable in the limit, the algorithm will correctly identify the target language\. Thus,kk\-list identifiability always implies identifiability withkkcolors\.

Interestingly, the converse is not true: identifiability with a color trace does not always imply identifiability with a finite\-size list\. To see this, fix any alphabetΣ\\Sigma\. For any finiteF⊆Σ∗F\\subseteq\\Sigma^\{\*\}, letLF=Σ∗∖FL\_\{F\}=\\Sigma^\{\*\}\\setminus F\. Now, consider the collection𝒞=\{LF:F​is a finite subset of​Σ∗\}\\mathcal\{C\}=\\\{L\_\{F\}:F\\text\{ is a finite subset of \}\\Sigma^\{\*\}\\\}\. This collection is not identifiable with a list of any finite size \(see Remark 3 inCharikar et al\. \([2025](https://arxiv.org/html/2607.12443#bib.bib3)\)\)\. However, there is a simple trace coloring scheme with just two colors that makes the collection identifiable: associate everyL∈𝒞L\\in\\mathcal\{C\}with the trace coloring functioncL​\(x\)=𝟙​\[x∈L\]c\_\{L\}\(x\)=\\mathds\{1\}\[x\\in L\]\. We call this the “accept\-reject” coloring\. Note then thatcLF​\(x\)=0c\_\{L\_\{F\}\}\(x\)=0only ifx∈Fx\\in F\. Thus, an algorithm may initializeF=∅F=\\emptyset, and initialize its guess for the target languageKKto beL∅L\_\{\\emptyset\}\. Whenever it sees an input stringxxwhose color trace has0in it, it obtains the prefixwwofxxat which the color0was seen \(i\.e\.,cK​\(w\)=0c\_\{K\}\(w\)=0\)\. The algorithm then addswwtoFF, and updates its guessLFL\_\{F\}accordingly\. If the target languageKKwasL∅L\_\{\\emptyset\}, the algorithm will never see a0in any color trace, and its initial guess remains correct throughout\. If the target languageKKwasLFL\_\{F\}for someF≠∅F\\neq\\emptyset, then for everyw∈Fw\\in F, the algorithm is guaranteed to see an inputxxthat containswwas its prefix; at this point, the algorithm correctly infersww’s membership inFF\. SinceFFis finite, the algorithm identifiesLFL\_\{F\}in the limit\.

The example above motivates studying the simple accept\-reject coloring scheme further\. Notice a key property about the collection in the example above: for everyL∈𝒞L\\in\\mathcal\{C\}, if a stringwwwas not inLL, it could be extended by some suffixyysuch thatw​y∈Lwy\\in L\. Indeed, this “reject\-extendability” property is sufficient for a collection to be identifiable in the limit with the accept\-reject coloring\.

###### Proposition 2\.1\(Reject\-Extendability Sufficient for Accept\-Reject Coloring\)\.

Let𝒞\\mathcal\{C\}be a countable language collection over the alphabetΣ\\Sigma, where everyL∈𝒞L\\in\\mathcal\{C\}satisfies the property: for everyw∈Σ∗w\\in\\Sigma^\{\*\}, ifw∉Lw\\notin L, then there exists a suffixy∈Σ∗y\\in\\Sigma^\{\*\}such thatw​y∈Lwy\\in L\. Then, the collection𝒞\\mathcal\{C\}is identifiable in the limit with a color trace given by the accept\-reject trace coloring\.

###### Proof 2\.2\.

LetK∈𝒞=\{L1,L2,…\}K\\in\\mathcal\{C\}=\\\{L\_\{1\},L\_\{2\},\\dots\\\}be the target language\. For everyL∈𝒞L\\in\\mathcal\{C\}, consider the accept\-reject coloring given by the trace functioncL​\(x\)=𝟙​\[x∈L\]c\_\{L\}\(x\)=\\mathds\{1\}\[x\\in L\]\. Consider the algorithm, which at time steptt, outputs the smallest indexiti\_\{t\}such that the languageLitL\_\{i\_\{t\}\}is consistent with all the information seen in the input so far\. Namely,LitL\_\{i\_\{t\}\}satisfies that\{x1,…,xt\}⊆Lit\\\{x\_\{1\},\\dots,x\_\{t\}\\\}\\subseteq L\_\{i\_\{t\}\}, and furthermore,tracecK​\(xb\)=tracecLit​\(xb\)\{\\mathrm\{trace\}\}\_\{c\_\{K\}\}\(x\_\{b\}\)=\{\\mathrm\{trace\}\}\_\{c\_\{L\_\{i\_\{t\}\}\}\}\(x\_\{b\}\)for all1≤b≤t1\\leq b\\leq t\. Furthermore, for everyj<itj<i\_\{t\}, either\{x1,…,xt\}⊈Lj\\\{x\_\{1\},\\dots,x\_\{t\}\\\}\\nsubseteq L\_\{j\}, ortracecK​\(xb\)≠tracecLj​\(xb\)\{\\mathrm\{trace\}\}\_\{c\_\{K\}\}\(x\_\{b\}\)\\neq\{\\mathrm\{trace\}\}\_\{c\_\{L\_\{j\}\}\}\(x\_\{b\}\)for some1≤b≤t1\\leq b\\leq t\.

Now, letzzbe the smallest index in the collection for whichLz=KL\_\{z\}=K\. We claim that the indexiti\_\{t\}output by the algorithm converges tozz\. To see this, note that the indexzzis always a valid candidate for the algorithm to output, since every string in the input is fromLz=KL\_\{z\}=K, and furthermore,cLzc\_\{L\_\{z\}\}andcKc\_\{K\}are identical\. Now, consider anyj<zj<zfor whichLj⊉LzL\_\{j\}\\nsupseteq L\_\{z\}\. For each suchLjL\_\{j\}, there exists somex∈Lz∖Ljx\\in L\_\{z\}\\setminus L\_\{j\}which shows up in the input at some finite time\. At this time, the languageLjL\_\{j\}becomes inconsistent\. Since there are finitely manyj<zj<z, we have that beyond some finite time, everyLjL\_\{j\}satisfyingj<zj<zandLj⊉LzL\_\{j\}\\nsupseteq L\_\{z\}is rendered inconsistent by the algorithm\. So, we restrict our attention to languagesLjL\_\{j\}that satisfyj<zj<zandLj⊋LzL\_\{j\}\\supsetneq L\_\{z\}\(note thatLjL\_\{j\}cannot equalLzL\_\{z\}, by our choice ofzz\)\. Fix any suchLjL\_\{j\}, and consider anyw∈Lj∖Lzw\\in L\_\{j\}\\setminus L\_\{z\}\. By the assumed reject\-extendability property, there exists some suffixy∈Σ∗y\\in\\Sigma^\{\*\}such thatw​y∈Lzwy\\in L\_\{z\}; furthermore, this stringw​ywyis guaranteed to show up in the input at some finite time\. But now, notice thatcK​\(w\)=cLz​\(w\)=0c\_\{K\}\(w\)=c\_\{L\_\{z\}\}\(w\)=0, butcLj​\(w\)=1c\_\{L\_\{j\}\}\(w\)=1\. Thus,tracecLj​\(w​y\)≠tracecK​\(w​y\)\{\\mathrm\{trace\}\}\_\{c\_\{L\_\{j\}\}\}\(wy\)\\neq\{\\mathrm\{trace\}\}\_\{c\_\{K\}\}\(wy\), and hence, the algorithm will declareLjL\_\{j\}to have an inconsistent color trace onw​ywy\. In this manner, every proper superset ofLzL\_\{z\}occurring before it gets invalidated at some finite time, and we conclude that the algorithm’s guess eventually converges tozz\.

The sufficient condition above for which the accept\-reject coloring works may be deemed to be fairly weak: it only stipulates that every rejected string may be extended in some way to acceptance\. Could it not be necessary? Namely, could every language collection be identifiable with the simple accept\-reject coloring? The following example shows that this is not the case\.

###### Example 2\.3\(Accept\-Reject Coloring Doesn’t Always Work\)\.

Consider a collection𝒞\\mathcal\{C\}over the binary alphabetΣ=\{0,1\}\\Sigma=\\\{0,1\\\}, which comprises of the regular languageL∞=\{0,1\}∗L\_\{\\infty\}=\\\{0,1\\\}^\{\*\}, together with the regular languagesLi=\{0,1\}∗∖1i​\{0,1\}∗L\_\{i\}=\\\{0,1\\\}^\{\*\}\\setminus 1^\{i\}\\\{0,1\\\}^\{\*\}fori≥1i\\geq 1\. Namely,LiL\_\{i\}excludes strings in\{0,1\}∗\\\{0,1\\\}^\{\*\}that start withiiones\. We have that for everyi≥1i\\geq 1,Li⊊Li\+1L\_\{i\}\\subsetneq L\_\{i\+1\},Li⊊L∞L\_\{i\}\\subsetneq L\_\{\\infty\}, and furthermore,∪iLi=L∞\\cup\_\{i\}L\_\{i\}=L\_\{\\infty\}\. Observe that for anyi∈ℕ∪\{∞\}i\\in\\mathds\{N\}\\cup\\\{\\infty\\\}andx∈Lix\\in L\_\{i\}, the accept\-reject coloring satisfiestracecLi​\(x\)=\(1,1,1,…,1\)⏟\|x\|\+1​times\{\\mathrm\{trace\}\}\_\{c\_\{L\_\{i\}\}\}\(x\)=\\underbrace\{\(1,1,1,\\dots,1\)\}\_\{\|x\|\+1\\text\{ times\}\}\. This is because eachLiL\_\{i\}is prefix\-closed: every prefix ofx∈Lix\\in L\_\{i\}is also contained inLiL\_\{i\}\. To see this, note that anyx∈Lix\\in L\_\{i\}does not start with1i1^\{i\}, and hence no prefix ofxxstarts with1i1^\{i\}as well\. In particular, no string ever has 0 in its color trace\. Furthermore, for anyi\>ji\>j,tracecLi​\(x\)=tracecLj​\(x\)\{\\mathrm\{trace\}\}\_\{c\_\{L\_\{i\}\}\}\(x\)=\{\\mathrm\{trace\}\}\_\{c\_\{L\_\{j\}\}\}\(x\)for everyx∈Lix\\in L\_\{i\}\.

Now, fix any identification algorithm, and consider an adversary that starts enumerating the strings inL1L\_\{1\}in the order that they appear in a fixed background ordering ofL∞L\_\{\\infty\}, together with their color traces \(according tocL1c\_\{L\_\{1\}\}, which is always the constant\-ones trace\)\. Then, at some finite time, the algorithm must guessL1L\_\{1\}to be the target language\. At this time, the adversary switches to enumerating the strings inL2L\_\{2\}, also in the fixed background ordering ofL∞L\_\{\\infty\}, and starting from the leftmost string inL2L\_\{2\}that has not been enumerated as yet\. The adversary continues giving color traces according toL2L\_\{2\}, which they can legally do, sinceL1⊊L2L\_\{1\}\\subsetneq L\_\{2\}, and the traces ofL2L\_\{2\}andL1L\_\{1\}matched on all strings inL1L\_\{1\}\. Now, the algorithm must guess the target language to beL2L\_\{2\}at some subsequent finite time, at which time the adversary switches toL3L\_\{3\}\. The adversary repeats this switching process endlessly, enumerating eachLiL\_\{i\}for a finite phase\. As the adversary begins enumeratingLiL\_\{i\}from the leftmost string that has not yet been enumerated in the fixed background ordering ofL∞L\_\{\\infty\}, the adversary eventually enumerates every string inL∞L\_\{\\infty\}, together also with its correct color trace according tocL∞c\_\{L\_\{\\infty\}\}\. But the algorithm guesses an incorrect language infinitely often, and hence does not identifyL∞L\_\{\\infty\}in the limit\.

The structure that enabled the adversarial strategy in\\Crefexample:accept\-reject\-failure distills precisely into the characterizing condition of\\Crefthm:characterization\-identification\-with\-traces\. Indeed, one direction of the characterization is a generalization of the adversarial strategy employed above\. In the other direction, we appropriately modify the algorithm used in\\Crefprop:reject\-extendability\-sufficiency to account for trace discrepancies, and tell\-tales associated with languages\.

## 3The Coloring Lemma

In this section, we restate and prove our main coloring lemma\. We also discuss an extension to the setting where the color traces observed have a bounded number of corruptions\. See[1\.2](https://arxiv.org/html/2607.12443#S1.Thmtheorem2)

###### Proof 3\.1\.

For any languageLL, define the setPref​\(L\)\\mathrm\{Pref\}\(L\)to be the set of all strings inΣ∗\\Sigma^\{\*\}that can be extended to form a string contained inLL\. Namely,

Pref​\(L\):=\{x∈Σ∗:∃t∈Σ∗​such that​x​t∈L\}\.\\displaystyle\\mathrm\{Pref\}\(L\):=\\\{x\\in\\Sigma^\{\*\}:\\exists t\\in\\Sigma^\{\*\}\\text\{ such that \}xt\\in L\\\}\.\(3\)Now, for anyL∈𝒞L\\in\\mathcal\{C\}, defineIsAcceptL:Σ∗→\{0,1\}\\mathrm\{IsAccept\}\_\{L\}:\\Sigma^\{\*\}\\to\\\{0,1\\\}andNextLiveL:Σ∗→\{0,1,…,k\}\\mathrm\{NextLive\}\_\{L\}:\\Sigma^\{\*\}\\to\\\{0,1,\\dots,k\\\}as:

IsAcceptL​\(x\):=𝟙​\[x∈L\],\\displaystyle\\mathrm\{IsAccept\}\_\{L\}\(x\):=\\mathds\{1\}\[x\\in L\],\(4\)NextLiveL​\(x\):=\|\{a∈Σ:x​a∈Pref​\(L\)\}\|\.\\displaystyle\\mathrm\{NextLive\}\_\{L\}\(x\):=\|\\\{a\\in\\Sigma:xa\\in\\mathrm\{Pref\}\(L\)\\\}\|\.\(5\)In words,IsAcceptL​\(x\)\\mathrm\{IsAccept\}\_\{L\}\(x\)is the indicator forxxbeing inLL, whereasNextLiveL​\(x\)\\mathrm\{NextLive\}\_\{L\}\(x\)counts the number of lettersa∈Σa\\in\\Sigmasuch thatx​axacan be further extended to form a string contained inLL\. Now fix the paletteP=\{1,2,…,k\+1\}P=\\\{1,2,\\dots,k\+1\\\}, and define the trace coloring functioncL:Σ∗→Pc\_\{L\}:\\Sigma^\{\*\}\\to Pas follows:

cL​\(x\)=\{IsAcceptL​\(x\)\+NextLiveL​\(x\)if​x∈Pref​\(L\),1otherwise\.\\displaystyle c\_\{L\}\(x\)=\\begin\{cases\}\\mathrm\{IsAccept\}\_\{L\}\(x\)\+\\mathrm\{NextLive\}\_\{L\}\(x\)&\\text\{if \}x\\in\\mathrm\{Pref\}\(L\),\\\\ 1&\\text\{otherwise\.\}\\\\ \\end\{cases\}\(6\)Ifx∉Pref​\(L\)x\\notin\\mathrm\{Pref\}\(L\),cL​\(x\)=1c\_\{L\}\(x\)=1; otherwise, ifx∈Pref​\(L\)x\\in\\mathrm\{Pref\}\(L\), then eitherIsAcceptL​\(x\)=1\\mathrm\{IsAccept\}\_\{L\}\(x\)=1, orNextLiveL​\(x\)\>0\\mathrm\{NextLive\}\_\{L\}\(x\)\>0; hencecL​\(x\)≥1c\_\{L\}\(x\)\\geq 1\. Therefore,cL​\(x\)∈\{1,2,…,k\+1\}c\_\{L\}\(x\)\\in\\\{1,2,\\dots,k\+1\\\}for allx∈Σ∗x\\in\\Sigma^\{\*\}\. We now observe that the functionscLc\_\{L\}satisfy monotonicity on any stringxxwith respect to inclusion\.

###### Observation 3\.2\(Monotonicity of Trace Coloring\)

For anyx∈Σ∗x\\in\\Sigma^\{\*\}, andL⊆L′L\\subseteq L^\{\\prime\}, it holds that

\(1\)​IsAcceptL​\(x\)≤IsAcceptL′​\(x\),\(2\)​NextLiveL​\(x\)≤NextLiveL′​\(x\),\(3\)​cL​\(x\)≤cL′​\(x\)\.\\displaystyle\\text\{\(1\) \}\\mathrm\{IsAccept\}\_\{L\}\(x\)\\leq\\mathrm\{IsAccept\}\_\{L^\{\\prime\}\}\(x\),\\quad\\text\{\(2\) \}\\ \\mathrm\{NextLive\}\_\{L\}\(x\)\\leq\\mathrm\{NextLive\}\_\{L^\{\\prime\}\}\(x\),\\quad\\text\{\(3\) \}\\ c\_\{L\}\(x\)\\leq c\_\{L^\{\\prime\}\}\(x\)\.

Now, fix anyL,L′∈𝒞L,L^\{\\prime\}\\in\\mathcal\{C\}for whichL⊊L′L\\subsetneq L^\{\\prime\}, and fix anyz∈L′∖Lz\\in L^\{\\prime\}\\setminus L\.

#### Case 1:z∈Pref​\(L\)z\\in\\mathrm\{Pref\}\(L\)\.

In this case, lett∈Σ∗t\\in\\Sigma^\{\*\}be such thatz​t∈Lzt\\in L\(note thatt≠εt\\neq\\varepsilon, sincez∉Lz\\notin L\)\. We claim thatx:=z​tx:=ztsatisfiestracecL​\(x\)≠tracecL′​\(x\)\{\\mathrm\{trace\}\}\_\{c\_\{L\}\}\(x\)\\neq\{\\mathrm\{trace\}\}\_\{c\_\{L^\{\\prime\}\}\}\(x\)\. To see this, note thatIsAcceptL​\(z\)=0\\mathrm\{IsAccept\}\_\{L\}\(z\)=0, butIsAcceptL′​\(z\)=1\\mathrm\{IsAccept\}\_\{L^\{\\prime\}\}\(z\)=1; together with\\Crefobservation:monotonicity\-trace\-coloring, this implies thatcL​\(z\)<cL′​\(z\)c\_\{L\}\(z\)<c\_\{L^\{\\prime\}\}\(z\)\.

#### Case 2:z∉Pref​\(L\)z\\notin\\mathrm\{Pref\}\(L\)\.

In this case, letw∈Σ∗w\\in\\Sigma^\{\*\}be the maximal prefix ofzzthat satisfiesw∈Pref​\(L\)w\\in\\mathrm\{Pref\}\(L\), and letz=w​a​tz=wat, wherea∈Σa\\in\\Sigma, andt∈Σ∗t\\in\\Sigma^\{\*\}\. Here, by maximal, we mean thatw​a∉Pref​\(L\)wa\\notin\\mathrm\{Pref\}\(L\)\. Note thatwwcan beε\\varepsilon, but its existence is guaranteed sinceLLis non\-empty\.

Now, sincew∈Pref​\(L\)w\\in\\mathrm\{Pref\}\(L\), there existsy∈Σ∗y\\in\\Sigma^\{\*\}such thatw​y∈Lwy\\in L\. We claim thatx:=w​yx:=wysatisfies thattracecL​\(x\)≠tracecL′​\(x\)\{\\mathrm\{trace\}\}\_\{c\_\{L\}\}\(x\)\\neq\{\\mathrm\{trace\}\}\_\{c\_\{L^\{\\prime\}\}\}\(x\)\. To see this, observe thatw​a∉Pref​\(L\)wa\\notin\\mathrm\{Pref\}\(L\), sincewwwas chosen to be the maximal prefix ofzzsatisfyingw∈Pref​\(L\)w\\in\\mathrm\{Pref\}\(L\)\. However,w​a∈Pref​\(L′\)wa\\in\\mathrm\{Pref\}\(L^\{\\prime\}\), sincez=w​a​t∈L′∖Lz=wat\\in L^\{\\prime\}\\setminus L\. Thus,NextLiveL​\(w\)<NextLiveL′​\(w\)\\mathrm\{NextLive\}\_\{L\}\(w\)<\\mathrm\{NextLive\}\_\{L^\{\\prime\}\}\(w\)\. By\\Crefobservation:monotonicity\-trace\-coloring, this implies thatcL​\(w\)<cL′​\(w\)c\_\{L\}\(w\)<c\_\{L^\{\\prime\}\}\(w\)\.

In both cases, we have shown the existence of anx∈Lx\\in LsatisfyingtracecL​\(x\)≠tracecL′​\(x\)\{\\mathrm\{trace\}\}\_\{c\_\{L\}\}\(x\)\\neq\{\\mathrm\{trace\}\}\_\{c\_\{L^\{\\prime\}\}\}\(x\)\.The next claim shows that at least fork=2k=2, the bound achieved by our construction is tight\.

###### Proposition 3\.3\(Coloring Lemma Tight fork=2k=2\)\.

There exists a finite collection𝒞\\mathcal\{C\}of non\-empty languages over the binary alphabetΣ=\{0,1\}\\Sigma=\\\{0,1\\\}, such that any family of trace coloring functions\{cL\}L∈𝒞\\\{c\_\{L\}\\\}\_\{L\\in\\mathcal\{C\}\}that satisfies the distinguishable coloring condition must necessarily use33colors\.

###### Proof 3\.4\.

Consider the finite collection𝒞=\{L1,L2,L3,L4,L5\}\\mathcal\{C\}=\\\{L\_\{1\},L\_\{2\},L\_\{3\},L\_\{4\},L\_\{5\}\\\}, where

L1=\{ε\},L2=\{ε,0\},L3=\{ε,1\},L4=\{ε,0,1\},L5=\{ε,0,1,01\}\.\\displaystyle L\_\{1\}=\\\{\\varepsilon\\\},\\quad L\_\{2\}=\\\{\\varepsilon,0\\\},\\quad L\_\{3\}=\\\{\\varepsilon,1\\\},\\quad L\_\{4\}=\\\{\\varepsilon,0,1\\\},\\quad L\_\{5\}=\\\{\\varepsilon,0,1,01\\\}\.Fix any trace coloring functionscL1,cL2,cL3,cL4,cL5c\_\{L\_\{1\}\},c\_\{L\_\{2\}\},c\_\{L\_\{3\}\},c\_\{L\_\{4\}\},c\_\{L\_\{5\}\}that map to the palette\{red,blue\}\\\{\\mathrm\{red\},\\mathrm\{blue\}\\\}, and satisfy the distinguishable coloring condition\.

SinceL1L\_\{1\}only containsε\\varepsilon, it must hold thatcL1​\(ε\)≠cL2​\(ε\)=cL3​\(ε\)=cL4​\(ε\)=cL5​\(ε\)c\_\{L\_\{1\}\}\(\\varepsilon\)\\neq c\_\{L\_\{2\}\}\(\\varepsilon\)=c\_\{L\_\{3\}\}\(\\varepsilon\)=c\_\{L\_\{4\}\}\(\\varepsilon\)=c\_\{L\_\{5\}\}\(\\varepsilon\)\. Without loss of generality, letcL1​\(ε\)=redc\_\{L\_\{1\}\}\(\\varepsilon\)=\\mathrm\{red\}, so thatcL2​\(ε\)=cL3​\(ε\)=cL4​\(ε\)=cL5​\(ε\)=bluec\_\{L\_\{2\}\}\(\\varepsilon\)=c\_\{L\_\{3\}\}\(\\varepsilon\)=c\_\{L\_\{4\}\}\(\\varepsilon\)=c\_\{L\_\{5\}\}\(\\varepsilon\)=\\mathrm\{blue\}\.

Then, forL2L\_\{2\}, it must hold thatcL2​\(0\)≠cL4​\(0\)=cL5​\(0\)c\_\{L\_\{2\}\}\(0\)\\neq c\_\{L\_\{4\}\}\(0\)=c\_\{L\_\{5\}\}\(0\)\. Similarly, forL3L\_\{3\}, it must be the case thatcL3​\(1\)≠cL4​\(1\)=cL5​\(1\)c\_\{L\_\{3\}\}\(1\)\\neq c\_\{L\_\{4\}\}\(1\)=c\_\{L\_\{5\}\}\(1\)\. Without loss of generality, supposecL2​\(0\)=redc\_\{L\_\{2\}\}\(0\)=\\mathrm\{red\}andcL3​\(1\)=redc\_\{L\_\{3\}\}\(1\)=\\mathrm\{red\}, so thatcL4​\(0\)=cL5​\(0\)=bluec\_\{L\_\{4\}\}\(0\)=c\_\{L\_\{5\}\}\(0\)=\\mathrm\{blue\}, andcL4​\(1\)=cL5​\(1\)=bluec\_\{L\_\{4\}\}\(1\)=c\_\{L\_\{5\}\}\(1\)=\\mathrm\{blue\}\.

But now, consider the traces ofL4L\_\{4\}\. By the previous assignments, we have that

tracecL4​\(ε\)=\(cL4​\(ε\)\)=\(blue\),\\displaystyle\{\\mathrm\{trace\}\}\_\{c\_\{L\_\{4\}\}\}\(\\varepsilon\)=\(c\_\{L\_\{4\}\}\(\\varepsilon\)\)=\(\\mathrm\{blue\}\),\\qquadtracecL5​\(ε\)=\(cL5​\(ε\)\)=\(blue\),\\displaystyle\{\\mathrm\{trace\}\}\_\{c\_\{L\_\{5\}\}\}\(\\varepsilon\)=\(c\_\{L\_\{5\}\}\(\\varepsilon\)\)=\(\\mathrm\{blue\}\),tracecL4​\(0\)=\(cL4​\(ε\),cL4​\(0\)\)=\(blue,blue\),\\displaystyle\{\\mathrm\{trace\}\}\_\{c\_\{L\_\{4\}\}\}\(0\)=\(c\_\{L\_\{4\}\}\(\\varepsilon\),c\_\{L\_\{4\}\}\(0\)\)=\(\\mathrm\{blue\},\\mathrm\{blue\}\),\\qquadtracecL5​\(0\)=\(cL5​\(ε\),cL5​\(0\)\)=\(blue,blue\),\\displaystyle\{\\mathrm\{trace\}\}\_\{c\_\{L\_\{5\}\}\}\(0\)=\(c\_\{L\_\{5\}\}\(\\varepsilon\),c\_\{L\_\{5\}\}\(0\)\)=\(\\mathrm\{blue\},\\mathrm\{blue\}\),tracecL4​\(1\)=\(cL4​\(ε\),cL4​\(1\)\)=\(blue,blue\),\\displaystyle\{\\mathrm\{trace\}\}\_\{c\_\{L\_\{4\}\}\}\(1\)=\(c\_\{L\_\{4\}\}\(\\varepsilon\),c\_\{L\_\{4\}\}\(1\)\)=\(\\mathrm\{blue\},\\mathrm\{blue\}\),\\qquadtracecL5​\(1\)=\(cL5​\(ε\),cL5​\(1\)\)=\(blue,blue\)\.\\displaystyle\{\\mathrm\{trace\}\}\_\{c\_\{L\_\{5\}\}\}\(1\)=\(c\_\{L\_\{5\}\}\(\\varepsilon\),c\_\{L\_\{5\}\}\(1\)\)=\(\\mathrm\{blue\},\\mathrm\{blue\}\)\.So, even thoughL4⊊L5L\_\{4\}\\subsetneq L\_\{5\}, everyx∈L4x\\in L\_\{4\}satisfiestracecL4​\(x\)=tracecL5​\(x\)\{\\mathrm\{trace\}\}\_\{c\_\{L\_\{4\}\}\}\(x\)=\{\\mathrm\{trace\}\}\_\{c\_\{L\_\{5\}\}\}\(x\)\. This contradicts the trace coloring functions satisfying the distinguishable coloring condition\.

We remark that the lower bound above does not, in general, preclude identifiability in the limit with trace coloring functions that use only 2 colors\. Rather, it merely shows that the distinguishable coloring condition may not be achieved for all collections using 2 colors\. Indeed, the collection above is finite, and every finite collection is identifiable without any color traces\(Angluin,[1980](https://arxiv.org/html/2607.12443#bib.bib1)\)\.

### 3\.1Extension to Corrupted Traces

We also obtain the guarantee of\\Creflemma:main\-coloring\-upper\-bound in the setting where the color traces seen may becorrupted\. Formally, we consider a notion of corrupted traces similar toPeng et al\. \([2026](https://arxiv.org/html/2607.12443#bib.bib8)\), where the trace seen along with an input stringxxistrace~cK​\(x\)\\widetilde\{\{\\mathrm\{trace\}\}\}\_\{c\_\{K\}\}\(x\), a corrupted version oftracecK​\(x\)\{\\mathrm\{trace\}\}\_\{c\_\{K\}\}\(x\)\. We restrict the nature of allowed corruptions as follows\. For anyxx, we require\|trace~cK​\(x\)\|=\|tracecK​\(x\)\|\|\\widetilde\{\{\\mathrm\{trace\}\}\}\_\{c\_\{K\}\}\(x\)\|=\|\{\\mathrm\{trace\}\}\_\{c\_\{K\}\}\(x\)\|\(i\.e\., the corrupted trace must have the same length as the uncorrupted trace\), and that every element intrace~cK​\(x\)\\widetilde\{\{\\mathrm\{trace\}\}\}\_\{c\_\{K\}\}\(x\)belongs to the same palettePPused bycKc\_\{K\}\(i\.e\., the corrupted trace cannot introduce colors outside the palette\)\. With these restrictions, we consider traces containing a bounded number of corruptions, as measured by theHamming distancebetween the corrupted and uncorrupted traces\. Namely, iftracecK​\(x\)=\(a1,a2,…,an\)\{\\mathrm\{trace\}\}\_\{c\_\{K\}\}\(x\)=\(a\_\{1\},a\_\{2\},\\dots,a\_\{n\}\)andtrace~cK​\(x\)=\(b1,b2,…,bn\)\\widetilde\{\{\\mathrm\{trace\}\}\}\_\{c\_\{K\}\}\(x\)=\(b\_\{1\},b\_\{2\},\\dots,b\_\{n\}\), we restrictd​\(a,b\)=\|\{i:ai≠bi,1≤i≤n\}\|≤ℓd\(a,b\)=\|\\\{i:a\_\{i\}\\neq b\_\{i\},1\\leq i\\leq n\\\}\|\\leq\\ell, whereℓ\>0\\ell\>0is an a priori known corruption budget\.

In this setting, we wish to correctly identify the target languageKKin the limit for any target languageKK, and for any enumeration\(x1,trace~cK​\(x1\)\),\(x2,trace~cK​\(x2\)\),…\(x\_\{1\},\\widetilde\{\{\\mathrm\{trace\}\}\}\_\{c\_\{K\}\}\(x\_\{1\}\)\),\(x\_\{2\},\\widetilde\{\{\\mathrm\{trace\}\}\}\_\{c\_\{K\}\}\(x\_\{2\}\)\),\\dotsofKKwith corrupted traces satisfying a corrupted budgetℓ\\ell\. From the proof of\\Crefthm:characterization\-identification\-with\-traces, it is straightforward to verify that asufficientcondition for identifiability of a collection𝒞\\mathcal\{C\}in this setting is the following: for everyL∈𝒞L\\in\\mathcal\{C\}, there exists a finite tell\-taleTL⊆LT\_\{L\}\\subseteq L, such that for everyL′∈𝒞L^\{\\prime\}\\in\\mathcal\{C\}satisfyingL′⊊LL^\{\\prime\}\\subsetneq L, either \(1\)L′L^\{\\prime\}does not containTLT\_\{L\}, or \(2\) there existsx∈L′x\\in L^\{\\prime\}such thatd​\(tracecL′​\(x\),tracecL​\(x\)\)\>2​ℓd\\left\(\{\\mathrm\{trace\}\}\_\{c\_\{L^\{\\prime\}\}\}\(x\),\{\\mathrm\{trace\}\}\_\{c\_\{L\}\}\(x\)\\right\)\>2\\ell\.

Then, just like\\Creflemma:main\-coloring\-upper\-bound, we seek trace coloring functions that always satisfy \(2\) above\. This will guarantee identifiability with corrupted traces having at mostℓ\\ellcorruptions\. Indeed, the next lemma constructs trace coloring functions that always satisfy \(2\) with a palette of sizeO​\(k2​ℓ\+1\)O\(k^\{2\\ell\+1\}\)\.

###### Lemma 3\.5\(Robust Coloring Lemma\)\.

Let𝒞\\mathcal\{C\}be a language collection comprising of non\-empty languages over a finite alphabetΣ\\Sigmaof sizekk, and fixℓ\>0\\ell\>0\. There exist trace coloring functions\{cL\}L∈𝒞\\\{c\_\{L\}\\\}\_\{L\\in\\mathcal\{C\}\}mapping to a palettePPof sizemax⁡\(8​ℓ\+4,8​k2​ℓ\+1\)\\max\(8\\ell\+4,8k^\{2\\ell\+1\}\), such that for anyL,L′∈𝒞L,L^\{\\prime\}\\in\\mathcal\{C\}that satisfyL⊊L′L\\subsetneq L^\{\\prime\}, andLLcontains some stringxxhaving length at least2​ℓ2\\ell, there existsx∈Lx\\in Lfor whichd​\(tracecL​\(x\),tracecL′​\(x\)\)\>2​ℓd\\left\(\{\\mathrm\{trace\}\}\_\{c\_\{L\}\}\(x\),\{\\mathrm\{trace\}\}\_\{c\_\{L^\{\\prime\}\}\}\(x\)\\right\)\>2\\ell\.

The proof of this lemma is given in\\Crefsec:robust\-coloring\-appendix\. The high\-level idea is to propagate the discrepancy at a single location implied by the construction in\\Creflemma:main\-coloring\-upper\-bound to all the2​ℓ2\\elllocations preceding it\.

## 4Traces for Regular Languages

The trace coloring functions that we constructed in\\Crefsec:main\-coloring satisfy a special property for regular languages\. Consider any regular languageLL, and letMMbe anyDeterministic Finite\-State Automaton \(DFA\)333We give a formal definition of a DFA in\\Crefsec:state\-traces\-appendix\.that recognizesLL\. LetQ​\(M\)Q\(M\)be its set of states,δM\\delta\_\{M\}be the associated state transition function,q0​\(M\)q\_\{0\}\(M\)be its initial state andF​\(M\)⊆Q​\(M\)F\(M\)\\subseteq Q\(M\)its accepting states\. For any stateqqinQ​\(M\)Q\(M\), letWqW\_\{q\}be the set of all the strings that arrive at stateqq, starting from the initial state\.

Recall the definition of our trace coloring functioncLc\_\{L\}from \([6](https://arxiv.org/html/2607.12443#S3.E6)\)\. We claim that for any stateqq, for anyw,w′∈Wqw,w^\{\\prime\}\\in W\_\{q\},cL​\(w\)=cL​\(w′\)c\_\{L\}\(w\)=c\_\{L\}\(w^\{\\prime\}\)\. To see this, note that sincewwandw′w^\{\\prime\}both end up at the stateqq, for any suffixyy,w​ywyandw′​yw^\{\\prime\}yalso end up in the same state inQ​\(M\)Q\(M\)\. This implies thatw∈Pref​\(L\)⇔w′∈Pref​\(L\)w\\in\\mathrm\{Pref\}\(L\)\\iff w^\{\\prime\}\\in\\mathrm\{Pref\}\(L\), and also thatIsAcceptL​\(w\)=IsAcceptL​\(w′\),NextLiveL​\(w\)=NextLiveL​\(w′\)\\mathrm\{IsAccept\}\_\{L\}\(w\)=\\mathrm\{IsAccept\}\_\{L\}\(w^\{\\prime\}\),\\mathrm\{NextLive\}\_\{L\}\(w\)=\\mathrm\{NextLive\}\_\{L\}\(w^\{\\prime\}\)\. We conclude thatcL​\(w\)=cL​\(w′\)c\_\{L\}\(w\)=c\_\{L\}\(w^\{\\prime\}\)\.

We now restate and prove\\Creflemma:state\-coloring\-optimal\-bound, which constructs state coloring functions usingk\+1k\+1colors so as to satisfy the distinguishable coloring condition, and also show that this palette size is optimal\.

See[1\.4](https://arxiv.org/html/2607.12443#S1.Thmtheorem4)

###### Proof 4\.1\.

For any stateq∈Q​\(M\)q\\in Q\(M\), we say thatqqis a live state if there exists a suffixy∈Σ∗y\\in\\Sigma^\{\*\}such thatδM​\(q,y\)∈F​\(M\)\\delta\_\{M\}\(q,y\)\\in F\(M\); otherwise, we callqqa dead state\. Now, similar to the definitions in \([4](https://arxiv.org/html/2607.12443#S3.E4)\) and \([5](https://arxiv.org/html/2607.12443#S3.E5)\), defineIsAcceptM:Q​\(M\)→\{0,1\}\\mathrm\{IsAccept\}\_\{M\}:Q\(M\)\\to\\\{0,1\\\}andNextLiveM:Q​\(M\)→\{0,1,…,k\}\\mathrm\{NextLive\}\_\{M\}:Q\(M\)\\to\\\{0,1,\\dots,k\\\}as:

IsAcceptM​\(q\):=𝟙​\[q∈F​\(M\)\],NextLiveM​\(q\):=\|\{a∈Σ:δM​\(q,a\)​is live\}\|\.\\displaystyle\\mathrm\{IsAccept\}\_\{M\}\(q\):=\\mathds\{1\}\[q\\in F\(M\)\],\\qquad\\mathrm\{NextLive\}\_\{M\}\(q\):=\|\\\{a\\in\\Sigma:\\delta\_\{M\}\(q,a\)\\text\{ is live\}\\\}\|\.Then, define the state coloring functioncM:Q​\(M\)→Pc\_\{M\}:Q\(M\)\\to Pas follows:

cM​\(q\)=\{IsAcceptM​\(q\)\+NextLiveM​\(q\)ifqis live,1otherwise\.\\displaystyle c\_\{M\}\(q\)=\\begin\{cases\}\\mathrm\{IsAccept\}\_\{M\}\(q\)\+\\mathrm\{NextLive\}\_\{M\}\(q\)&\\text\{if $q$ is live\},\\\\ 1&\\text\{otherwise\.\}\\end\{cases\}\(7\)We can then verify that for anyx=x0​x1​…​xn∈L​\(M\)x=x\_\{0\}x\_\{1\}\\dots x\_\{n\}\\in L\(M\)\(wherex0=εx\_\{0\}=\\varepsilon\) that traverses the statesq0,q1,…,qnq\_\{0\},q\_\{1\},\\dots,q\_\{n\}inMM, and for anyqiq\_\{i\}, it holds thatcM​\(qi\)=cL​\(M\)​\(x0​x1​…​xi\)c\_\{M\}\(q\_\{i\}\)=c\_\{L\(M\)\}\(x\_\{0\}x\_\{1\}\\dots x\_\{i\}\), wherecL​\(M\)c\_\{L\(M\)\}is exactly the trace coloring function defined in \([6](https://arxiv.org/html/2607.12443#S3.E6)\) in the proof of\\Creflemma:main\-coloring\-upper\-bound\. The conclusion of that lemma implies that\{cM\}M∈𝒞\\\{c\_\{M\}\\\}\_\{M\\in\\mathcal\{C\}\}satisfy the required distinguishable coloring condition\.

We now show thatk\+1k\+1colors are optimal\. Fixk≥1k\\geq 1, and consider𝒞=\{M0,M1,…,Mk\}\\mathcal\{C\}=\\\{M\_\{0\},M\_\{1\},\\dots,M\_\{k\}\\\}\. EachMiM\_\{i\}has just two statesq0​\(Mi\)q\_\{0\}\(M\_\{i\}\)andq1​\(Mi\)q\_\{1\}\(M\_\{i\}\), whereq0​\(Mi\)q\_\{0\}\(M\_\{i\}\)is the initial state, and also the only accepting state, andq1​\(Mi\)q\_\{1\}\(M\_\{i\}\)is a rejecting sink state\. Namely,∀i​∀a:\\forall i\\forall a:δMi​\(q1​\(Mi\),a\)=q1​\(Mi\)\\delta\_\{M\_\{i\}\}\(q\_\{1\}\(M\_\{i\}\),a\)=q\_\{1\}\(M\_\{i\}\)\.

Now, inM0M\_\{0\}, we further setδM0​\(q0​\(M0\),a\)=q1​\(M0\)\\delta\_\{M\_\{0\}\}\(q\_\{0\}\(M\_\{0\}\),a\)=q\_\{1\}\(M\_\{0\}\)for everya∈Σa\\in\\Sigma\. So, it holds thatL​\(M0\)=\{ε\}L\(M\_\{0\}\)=\\\{\\varepsilon\\\}\. Next, fori∈\{1,…,k\}i\\in\\\{1,\\dots,k\\\}, we set

δMi​\(q0​\(Mi\),a\)=\{q0​\(Mi\)ifa∈\{1,…,i\},q1​\(Mi\)otherwise\.\\displaystyle\\delta\_\{M\_\{i\}\}\(q\_\{0\}\(M\_\{i\}\),a\)=\\begin\{cases\}q\_\{0\}\(M\_\{i\}\)&\\text\{if $a\\in\\\{1,\\dots,i\\\}$\},\\\\ q\_\{1\}\(M\_\{i\}\)&\\text\{otherwise\.\}\\end\{cases\}Thus,L​\(Mi\)=\{1,…,i\}∗L\(M\_\{i\}\)=\\\{1,\\dots,i\\\}^\{\*\}\. Observe thatL​\(M0\)⊊L​\(M1\)⊊⋯⊊L​\(Mk\)L\(M\_\{0\}\)\\subsetneq L\(M\_\{1\}\)\\subsetneq\\dots\\subsetneq L\(M\_\{k\}\)\.

Now, fix any state coloring functionscM0,cM1,…,cMkc\_\{M\_\{0\}\},c\_\{M\_\{1\}\},\\dots,c\_\{M\_\{k\}\}that use a palette of sizekk, and assume that they satisfy: for everyMi,Mj∈𝒞M\_\{i\},M\_\{j\}\\in\\mathcal\{C\}withL​\(Mi\)⊊L​\(Mj\)L\(M\_\{i\}\)\\subsetneq L\(M\_\{j\}\), there existsx∈L​\(Mi\)x\\in L\(M\_\{i\}\)for whichtracecMi​\(x\)≠tracecMj​\(x\)\{\\mathrm\{trace\}\}\_\{c\_\{M\_\{i\}\}\}\(x\)\\neq\{\\mathrm\{trace\}\}\_\{c\_\{M\_\{j\}\}\}\(x\)\. Fix anyi,j∈\{0,1,…,k\}i,j\\in\\\{0,1,\\dots,k\\\}satisfyingi<ji<j\. Observe that anyx∈L​\(Mi\)x\\in L\(M\_\{i\}\)simply loops on the stateq0​\(Mi\)q\_\{0\}\(M\_\{i\}\), givingtracecMi​\(x\)=\(cMi​\(q0​\(Mi\)\),…,cMi​\(q0​\(Mi\)\)\)⏟\|x\|\+1​times\{\\mathrm\{trace\}\}\_\{c\_\{M\_\{i\}\}\}\(x\)=\\underbrace\{\(c\_\{M\_\{i\}\}\(q\_\{0\}\(M\_\{i\}\)\),\\dots,c\_\{M\_\{i\}\}\(q\_\{0\}\(M\_\{i\}\)\)\)\}\_\{\|x\|\+1\\text\{ times\}\}\. Thus, for the assumed guarantee to hold, it must be the case that for everyi<ji<j,cMi​\(q0​\(Mi\)\)≠cMj​\(q0​\(Mj\)\)c\_\{M\_\{i\}\}\(q\_\{0\}\(M\_\{i\}\)\)\\neq c\_\{M\_\{j\}\}\(q\_\{0\}\(M\_\{j\}\)\)\. But this is not possible if the state coloring functions use onlykkcolors\.

In\\Crefsec:corrupted\-state\-traces\-appendix, we extend the construction of the state coloring functions above to the setting with corrupted traces, similar to\\Crefsec:corruptions\. Here, we show that a palette of sizeO​\(k2​ℓ\+1\)O\(k^\{2\\ell\+1\}\)suffices to achieve a similar guarantee as\\Creflemma:corruptions\-coloring\-upper\-bound, and thatk2​ℓ−1k^\{2\\ell\-1\}colors are necessary in general\.

Finally, we restate and prove\\Crefthm:regular\-languages\-2\-colors\. See[1\.5](https://arxiv.org/html/2607.12443#S1.Thmtheorem5)

Before stating the formal proof, we give some intuition, specifically since the requirement that everyLiL\_\{i\}be infinite might appear counterintuitive at first glance for this positive result\. The trace coloring functions that we build interestingly arise via state coloring functions\. That is, we carefully choose a sequence of automataM1,M2,…M\_\{1\},M\_\{2\},\\dotsthat acceptL1,L2,…L\_\{1\},L\_\{2\},\\dots, prescribe state coloring functions for these automata, and then directly argue that they achieve the goal of identification with just two colors\. This is in contrast to\\Creflemma:state\-coloring\-optimal\-bound, where the automata were fixed and provided to us, and we were concerned with the \(stronger\) distinguishable coloring condition; here, we choose suitable automata as a tool for constructing trace coloring functions for identification\.

While there are several automata that recognizeLiL\_\{i\}, we want to chooseMiM\_\{i\}with a view to satisfying the following property: for each previous automatonMjM\_\{j\}wherej<ij<iandLjL\_\{j\}is a superset ofLiL\_\{i\}, we can designate a particular state inMiM\_\{i\}with a particular color, which helps distinguish it fromMjM\_\{j\}\. In order to choose such a designated state for everyj<ij<i, we need enough states \(at leasti−1i\-1\) inLiL\_\{i\}to begin with\. A sufficient condition to ensure this is that everyLiL\_\{i\}is infinite \(intuitively, since there are long enough strings in the language, these must cause a loop, which can be “disentangled” to enlarge the state space\)\. This ensures that with just two colors, we can distinguish the color traces of every languageLiL\_\{i\}from the color traces of every superset ofLiL\_\{i\}that appears beforeLiL\_\{i\}\. Note that this is a weaker property than the distinguishable coloring condition \(which requires such a property forallsupersets in the collection, not just the ones appearing before\), but is sufficient for identification in the limit \(see\\Crefremark:weaker\-condition\-sufficient\)\.

We now give the formal proof\.

###### Proof 4\.2\.

FixM1,M2,…M\_\{1\},M\_\{2\},\\dotsto be any arbitrary DFAs that recognizeL1,L2,…L\_\{1\},L\_\{2\},\\dots\. Now recall the definition of a live state in a DFA: a stateq∈Q​\(M\)q\\in Q\(M\)is live if∃\\existsa suffixy∈Σ∗y\\in\\Sigma^\{\*\}such thatδM​\(q,y\)∈F​\(M\)\\delta\_\{M\}\(q,y\)\\in F\(M\)\. Now call a stateqqreachable if∃w∈Σ∗\\exists w\\in\\Sigma^\{\*\}such thatδM​\(q0​\(M\),w\)=q\\delta\_\{M\}\(q\_\{0\}\(M\),w\)=q\. By\\Creflemma:increasing\-live\-states proved in\\Crefsec:state\-traces\-appendix, we can assume that everyMiM\_\{i\}has at leasti−1i\-1live and reachable states\. We will now inductively determine a binary state coloring functioncMic\_\{M\_\{i\}\}for everyi≥1i\\geq 1\.

To begin with, fixcM1c\_\{M\_\{1\}\}arbitrarily\. Now, for anyi\>1i\>1, let us assume thatcM1,…,cMi−1c\_\{M\_\{1\}\},\\dots,c\_\{M\_\{i\-1\}\}have been determined\. ConsiderMiM\_\{i\}: there are at leasti−1i\-1live and reachable states inMiM\_\{i\}\. Pick anyi−1i\-1of these, and denote the set as\{qb\}b=1,…,i−1\\\{q\_\{b\}\\\}\_\{b=1,\\dots,i\-1\}\. Associate eachqbq\_\{b\}with a prefixwb∈Σ∗w\_\{b\}\\in\\Sigma^\{\*\}and a suffixyb∈Σ∗y\_\{b\}\\in\\Sigma^\{\*\}, such thatδMi​\(q0​\(Mi\),wb\)=qb\\delta\_\{M\_\{i\}\}\(q\_\{0\}\(M\_\{i\}\),w\_\{b\}\)=q\_\{b\}, andδMi​\(qb,yb\)∈F​\(Mi\)\\delta\_\{M\_\{i\}\}\(q\_\{b\},y\_\{b\}\)\\in F\(M\_\{i\}\), so thatxb=wb​yb∈Lix\_\{b\}=w\_\{b\}y\_\{b\}\\in L\_\{i\}\. Now, consider the set\{j<i:Lj⊋Li\}\\\{j<i:L\_\{j\}\\supsetneq L\_\{i\}\\\}: this set has size at mosti−1i\-1\. Thus, we can map everyjjin this set to a distinct liveqbq\_\{b\}inMiM\_\{i\}\. Consider traversing the prefixwbw\_\{b\}associated withqbq\_\{b\}inMjM\_\{j\}, and letqb′=δMj​\(q0​\(Mj\),wb\)q^\{\\prime\}\_\{b\}=\\delta\_\{M\_\{j\}\}\(q\_\{0\}\(M\_\{j\}\),w\_\{b\}\)\. We will setcMi​\(qb\)=1−cMj​\(qb′\)c\_\{M\_\{i\}\}\(q\_\{b\}\)=1\-c\_\{M\_\{j\}\}\(q^\{\\prime\}\_\{b\}\)\. After doing this for everyjj, we assigncMi​\(q\)c\_\{M\_\{i\}\}\(q\)for the remaining states inMiM\_\{i\}arbitrarily\. This completes the specification ofcMi​\(q\)c\_\{M\_\{i\}\}\(q\)\.

Now consider anyi≥1i\\geq 1\. We claim that:\(⋆\)\(\\star\)for everyj<ij<i, ifLj⊋LiL\_\{j\}\\supsetneq L\_\{i\}, then there existsxxinLiL\_\{i\}for whichtracecMi​\(x\)≠tracecMj​\(x\)\{\\mathrm\{trace\}\}\_\{c\_\{M\_\{i\}\}\}\(x\)\\neq\{\\mathrm\{trace\}\}\_\{c\_\{M\_\{j\}\}\}\(x\)\. Indeed, fix any suchLjL\_\{j\}, and letqbq\_\{b\}be the distinct live state inMiM\_\{i\}that we had associatedLjL\_\{j\}with in the inductive construction ofcMic\_\{M\_\{i\}\}above\. Now consider the stringxb=wb​yb∈Lix\_\{b\}=w\_\{b\}y\_\{b\}\\in L\_\{i\}associated with the stateqbq\_\{b\}inMiM\_\{i\}\. Note that the prefixwbw\_\{b\}reaches the stateqb′=δMj​\(q0​\(Mj\),wb\)q^\{\\prime\}\_\{b\}=\\delta\_\{M\_\{j\}\}\(q\_\{0\}\(M\_\{j\}\),w\_\{b\}\)inMjM\_\{j\}, whereas it reaches the stateqbq\_\{b\}inMiM\_\{i\}; our construction above guarantees thatcMi​\(qb\)=1−cMj​\(qb′\)c\_\{M\_\{i\}\}\(q\_\{b\}\)=1\-c\_\{M\_\{j\}\}\(q^\{\\prime\}\_\{b\}\)\. Thus,tracecMi​\(xb\)≠tracecMj​\(xb\)\{\\mathrm\{trace\}\}\_\{c\_\{M\_\{i\}\}\}\(x\_\{b\}\)\\neq\{\\mathrm\{trace\}\}\_\{c\_\{M\_\{j\}\}\}\(x\_\{b\}\), as claimed\.

Finally, by\\Crefremark:weaker\-condition\-sufficient in the proof of\\Crefthm:characterization\-identification\-with\-traces, the property\(⋆\)\(\\star\)is sufficient for the algorithm considered in that proof to identify the collection in the limit with traces\.

## 5Conclusion and Discussion

We studied the problem of language identification with coarse\-grained annotations, independent of any underlying machine implementation of the target language\. Our main result shows that every countable language collection can be identified in the limit with annotations the same size as the input strings, with alphabet size one more than the input alphabet size\.

One open problem is to prove a lower bound on the number of colors required for language identification with a color trace\. For regular language collections, our result shows that two colors always suffice, independent of their alphabet sizekk\. Do constantly many colors always suffice for any arbitrary collection? Or must the number of colors grow linearly withkk? Another open problem is to establish a lower bound on the number of colors required to achieve the distinguishable coloring condition — going beyond our lower bound of 3 colors seems challenging\.

Regarding the question about the number of colors necessary for identification, very recently, we have been able to show that the result of\\Crefthm:regular\-languages\-2\-colors, that trace coloring functions with just two colors suffice for identifying collections of regular languages that are all infinite, can in fact be generalized to collections ofarbitrarylanguages that are all infinite\. In fact, while trace coloring functions color every character in each string, this strengthened result can even be obtained with “terminal” coloring functions, where one only needs to assign a color to the entire string at once\.

However, the terminal coloring functions for each language in this 2\-coloring result arecollection\-dependent\(as are the trace coloring functions from\\Crefthm:regular\-languages\-2\-colors\)\. Note, in contrast, that our general\-purpose trace\-coloring functions from\\Crefthm:main\-theorem which usek\+1k\+1colors, arecollection\-independent\. This raises the natural question: do there exist collection\-independent terminal coloring functions that use only two colors, and suffice for identification in the limit for all countable language collections \(possibly with the restriction that every language is infinite\)?

It turns out that the answer to this question is yes; however, the required 2\-coloring functions turn out to be highly non\-constructive \(and, we can prove, necessarily so in a precise sense\), involving reasoning with uncountable ordinals and transfinite recursion\. As a result, this new result is in a sense not directly comparable to the general trace coloring result in\\Crefthm:main\-theorem of the present paper: the new result is quantitatively stronger \(using 2 colors instead ofk\+1k\+1\), but it markedly lacks the constructive, natural formulation of\\Crefthm:main\-theorem\. Because the premise, techniques and analyses used to obtain these results largely depart from the present results in this paper, we defer them to a different manuscript\(Charikar et al\.,[2026](https://arxiv.org/html/2607.12443#bib.bib4)\)\.

\\acks

This work was supported by Moses Charikar’s and Gregory Valiant’s Simons Investigator Awards, a Google PhD Fellowship, a Simons Collaboration grant and a grant from the MacArthur Foundation\.

## References

- Angluin \(1980\)Dana Angluin\.Inductive inference of formal languages from positive data\.*Information and control*, 45\(2\):117–135, 1980\.
- Bhattamishra et al\. \(2026\)Satwik Bhattamishra, Michael Hahn, and Varun Kanade\.Automata learning and identification of the support of language models\.In*The Fourteenth International Conference on Learning Representations*, 2026\.URLhttps://openreview\.net/forum?id=L8SMNWsxfK\.
- Charikar et al\. \(2025\)Moses Charikar, Chirag Pabbaraju, and Ambuj Tewari\.A characterization of list language identification in the limit\.*arXiv preprint arXiv:2511\.04103*, 2025\.
- Charikar et al\. \(2026\)Moses Charikar, Jon Kleinberg, and Chirag Pabbaraju\.Globally consistent coloring schemes for language identification\.*arXiv preprint arXiv:2607\.11606*, 2026\.
- Gold \(1967\)E Mark Gold\.Language identification in the limit\.*Information and control*, 10\(5\):447–474, 1967\.
- Hopcroft et al\. \(2001\)John E Hopcroft, Rajeev Motwani, and Jeffrey D Ullman\.Introduction to automata theory, languages, and computation\.*Acm Sigact News*, 32\(1\):60–65, 2001\.
- Papazov and Flammarion \(2025\)Hristo Papazov and Nicolas Flammarion\.Learning algorithms in the limit\.In Nika Haghtalab and Ankur Moitra, editors,*Proceedings of Thirty Eighth Conference on Learning Theory*, volume 291 of*Proceedings of Machine Learning Research*, pages 4486–4510\. PMLR, 30 Jun–04 Jul 2025\.URLhttps://proceedings\.mlr\.press/v291/papazov25a\.html\.
- Peng et al\. \(2026\)Binghui Peng, Amin Saberi, and Grigoris Velegkas\.Language identification in the limit with computational trace\.In*The Fourteenth International Conference on Learning Representations*, 2026\.URLhttps://openreview\.net/forum?id=1OAGf7ntSE\.
- Sipser \(1996\)Michael Sipser\.*Introduction to the Theory of Computation*\.International Thomson Publishing, 1st edition, 1996\.ISBN 053494728X\.
- Wei et al\. \(2022\)Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H\. Chi, Quoc V\. Le, and Denny Zhou\.Chain\-of\-thought prompting elicits reasoning in large language models\.In Sanmi Koyejo, S\. Mohamed, A\. Agarwal, Danielle Belgrave, K\. Cho, and A\. Oh, editors,*Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 \- December 9, 2022*, 2022\.URLhttp://papers\.nips\.cc/paper\_files/paper/2022/hash/9d5609613524ecf4f15af0f7b31abca4\-Abstract\-Conference\.html\.

\\crefalias

sectionappendix

## Appendix AOmitted Proofs from\\Crefsec:main\-coloring

### A\.1Characterization of Identification in the Limit with Color Traces

See[1\.1](https://arxiv.org/html/2607.12443#S1.Thmtheorem1)

###### Proof A\.1\.

#### If direction\.

Suppose that the stated condition holds for the collection𝒞=\{L1,L2,…\}\\mathcal\{C\}=\\\{L\_\{1\},L\_\{2\},\\dots\\\}and the associated trace coloring functions\{cL\}L∈𝒞\\\{c\_\{L\}\\\}\_\{L\\in\\mathcal\{C\}\}\. Furthermore, letTLT\_\{L\}be the finite tell\-tale subset associated with languageLLin the collection\. Denote the unknown target language byKK, and consider the following identification algorithm: at time steptt, upon seeing\(x1,tracecK​\(x1\)\),…,\(xt,tracecK​\(xt\)\)\(x\_\{1\},\{\\mathrm\{trace\}\}\_\{c\_\{K\}\}\(x\_\{1\}\)\),\\dots,\(x\_\{t\},\{\\mathrm\{trace\}\}\_\{c\_\{K\}\}\(x\_\{t\}\)\), the algorithm outputs the smallest indexiti\_\{t\}, which satisfies: \(1\)\{x1,…,xt\}⊆Lit\\\{x\_\{1\},\\dots,x\_\{t\}\\\}\\subseteq L\_\{i\_\{t\}\}, \(2\)TLit⊆\{x1,…,xt\}T\_\{L\_\{i\_\{t\}\}\}\\subseteq\\\{x\_\{1\},\\dots,x\_\{t\}\\\}, and \(3\)tracecLit​\(xj\)=tracecK​\(xj\)\{\\mathrm\{trace\}\}\_\{c\_\{L\_\{i\_\{t\}\}\}\}\(x\_\{j\}\)=\{\\mathrm\{trace\}\}\_\{c\_\{K\}\}\(x\_\{j\}\)for every1≤j≤t1\\leq j\\leq t\. We remark that without the check in \(3\), the algorithm would be identical to Angluin’s algorithm for identification in the limit\(Angluin,[1980](https://arxiv.org/html/2607.12443#bib.bib1)\)\.

Letzzbe any index in the collection for whichLz=KL\_\{z\}=K, andtracecLz​\(x\)=tracecK​\(x\)\{\\mathrm\{trace\}\}\_\{c\_\{L\_\{z\}\}\}\(x\)=\{\\mathrm\{trace\}\}\_\{c\_\{K\}\}\(x\)for everyx∈Kx\\in K\. Note that such an index exists sinceK∈𝒞K\\in\\mathcal\{C\}\. Note also that requirements \(1\) and \(3\) hold for indexzzat all time steps\. Furthermore, sinceTLzT\_\{L\_\{z\}\}is a finite subset ofKK, and the input eventually enumerates every string inKK, there exists a finite time at which requirement \(2\) gets satisfied as well\. Thus, beyond this time,zzis a valid candidate index for the algorithm to output\. We proceed assuming that we are beyond this time\.

Now, consider anyj<zj<zfor whichLj⊉LzL\_\{j\}\\nsupseteq L\_\{z\}\. For each suchLjL\_\{j\}, there exists somex∈Lz∖Ljx\\in L\_\{z\}\\setminus L\_\{j\}which is guaranteed to show up in the input at some finite time\. At this time and beyond, indexjjviolates \(1\)\. Since there are only finitely manyj<zj<z, we have that beyond some finite time, everyjjsatisfyingj<zj<zandLj⊉LzL\_\{j\}\\nsupseteq L\_\{z\}violates \(1\)\. So, we assume being beyond this time as well, and next restrict our attention to indicesjjthat satisfyj<zj<zandLj⊋LzL\_\{j\}\\supsetneq L\_\{z\}\. Suppose in one case thatTLj⊆LzT\_\{L\_\{j\}\}\\subseteq L\_\{z\}holds\. Then, at some finite time, all ofTLjT\_\{L\_\{j\}\}will show up in the input, and hence \(2\) will always be satisfied beyond this time by indexjj\. But now observe that we are in a position whereLzL\_\{z\}andLjL\_\{j\}satisfy:Lz⊊LjL\_\{z\}\\subsetneq L\_\{j\}andTLj⊆LzT\_\{L\_\{j\}\}\\subseteq L\_\{z\}\. By the condition in the theorem, it must then hold that there existsx∈Lzx\\in L\_\{z\}for whichtracecLz​\(x\)=tracecK​\(x\)≠tracecLj​\(x\)\{\\mathrm\{trace\}\}\_\{c\_\{L\_\{z\}\}\}\(x\)=\{\\mathrm\{trace\}\}\_\{c\_\{K\}\}\(x\)\\neq\{\\mathrm\{trace\}\}\_\{c\_\{L\_\{j\}\}\}\(x\)\. Such anxxis guaranteed to show up in the input at some finite time, together withtracecK​\(x\)\{\\mathrm\{trace\}\}\_\{c\_\{K\}\}\(x\); at this time and beyond, indexjjviolates \(3\)\. In the other case, suppose thatTLj⊈LzT\_\{L\_\{j\}\}\\nsubseteq L\_\{z\}\. In this case, at least one element inTLjT\_\{L\_\{j\}\}will never show up in the input, and hence \(2\) will never be satisfied by indexjj\. In all cases, we have shown that there exists a finite time beyond which indexjjstops being a candidate for the algorithm\. Since there are only finitely manyj<zj<z, we conclude that the algorithm eventually always outputs somej≤zj\\leq zfor whichLj=Lz=KL\_\{j\}=L\_\{z\}=K\.

#### Only if direction\.

Fix a set of trace coloring functions\{cL\}L∈𝒞\\\{c\_\{L\}\\\}\_\{L\\in\\mathcal\{C\}\}, and suppose that there exists a languageL∈𝒞L\\in\\mathcal\{C\}such that for every finiteT⊆LT\\subseteq L, there exists a languageL′∈𝒞L^\{\\prime\}\\in\\mathcal\{C\}that is a proper subset ofLL, such thatL′L^\{\\prime\}containsTTand alsotracecL′​\(x\)=tracecL​\(x\)\{\\mathrm\{trace\}\}\_\{c\_\{L^\{\\prime\}\}\}\(x\)=\{\\mathrm\{trace\}\}\_\{c\_\{L\}\}\(x\)for everyx∈L′x\\in L^\{\\prime\}\. We will show that the collection is not identifiable in the limit with color traces given by these trace coloring functions\.

Towards this, fix any identification algorithm, and consider an adversary that starts enumerating the strings inLL, together with their color traces according tocLc\_\{L\}, in the order that they appear in a fixed background ordering ofLL\. Then, at some finite time, the algorithm must guess an indexiisuch thatLi=LL\_\{i\}=L\. Suppose that the input strings enumerated so far by the adversary comprise of the setTT\. Then, by assumption, there exists a languageL′∈𝒞L^\{\\prime\}\\in\\mathcal\{C\}that is a proper subset ofLL, such thatL′L^\{\\prime\}containsTT, and furthermore,tracecL′​\(x\)=tracecL​\(x\)\{\\mathrm\{trace\}\}\_\{c\_\{L^\{\\prime\}\}\}\(x\)=\{\\mathrm\{trace\}\}\_\{c\_\{L\}\}\(x\)for everyx∈L′x\\in L^\{\\prime\}\(includingTT\)\. Thus, the adversary switches to enumerating strings inL′L^\{\\prime\}with their color traces \(which they can legally do, sinceT⊆L′T\\subseteq L^\{\\prime\}, and the traces ofL′L^\{\\prime\}andLLmatch on all strings inL′L^\{\\prime\}\)\. Now, the algorithm must guess an indexiisatisfyingLi=L′L\_\{i\}=L^\{\\prime\}at some subsequent finite time\. At this time, the adversary switches back to enumeratingLL\(they can do this since traces ofL′L^\{\\prime\}andLLmatch at all strings inL′L^\{\\prime\}\), starting from the leftmost string that has not yet been enumerated in the fixed background ordering ofLL\. Again, at some subsequent finite time, the algorithm must guess an indexiisuch thatLi=LL\_\{i\}=L\. Suppose that the input strings enumerated so far by the adversary comprise of the setT′T^\{\\prime\}\. Then, by assumption again, there exists a languageL′′∈𝒞L^\{\\prime\\prime\}\\in\\mathcal\{C\}that is a proper subset ofLL, such thatL′′L^\{\\prime\\prime\}containsT′T^\{\\prime\}, and furthermore,tracecL′′​\(x\)=tracecL​\(x\)\{\\mathrm\{trace\}\}\_\{c\_\{L^\{\\prime\\prime\}\}\}\(x\)=\{\\mathrm\{trace\}\}\_\{c\_\{L\}\}\(x\)for everyx∈L′′x\\in L^\{\\prime\\prime\}\(includingT′T^\{\\prime\}\)\. Thus, the adversary switches to enumerating strings inL′′L^\{\\prime\\prime\}\. The adversary thus continues switching back and forth betweenLLand some other languageL~⊊L\\tilde\{L\}\\subsetneq Lendlessly\. Since at each switch back toLL, the adversary begins with the leftmost string inLLthat has not yet been enumerated in its fixed background ordering, the adversary eventually enumerates every string inLLalong with its trace according tocLc\_\{L\}\. But also, each switch back toLLfollows a time step at which the algorithm guesses an indexiifor whichLi=L~⊊LL\_\{i\}=\\tilde\{L\}\\subsetneq L, and hence the algorithm guesses an incorrect index infinitely often\. Thus, the algorithm does not identifyLLin the limit\.

### A\.2Robust Coloring Lemma

See[3\.5](https://arxiv.org/html/2607.12443#S3.Thmtheorem5)

###### Proof A\.3\.

For any languageL∈𝒞L\\in\\mathcal\{C\}, we extend the definitions ofIsAcceptL\\mathrm\{IsAccept\}\_\{L\}andNextLiveL\\mathrm\{NextLive\}\_\{L\}from the proof of\\Creflemma:main\-coloring\-upper\-bound, and also consider some global quantities for the language\. Namely, consider the functionsIsAcceptL\\mathrm\{IsAccept\}\_\{L\}andNextLiveL\\mathrm\{NextLive\}\_\{L\}that mapΣ∗\\Sigma^\{\*\}to a non\-negative integer, and the quantitiesShortAcceptL\\mathrm\{ShortAccept\}\_\{L\}andShortPrefixL\\mathrm\{ShortPrefix\}\_\{L\}, defined as follows:

IsAcceptL​\(x\):=\|\{y∈Σ\{0,…,2​ℓ\}:x​y∈L\}\|,\\displaystyle\\mathrm\{IsAccept\}\_\{L\}\(x\):=\|\\\{y\\in\\Sigma^\{\\\{0,\\dots,2\\ell\\\}\}:xy\\in L\\\}\|,\(8\)NextLiveL​\(x\):=\|\{y∈Σ\{1,…,2​ℓ\+1\}:x​y∈Pref​\(L\)\}\|,\\displaystyle\\mathrm\{NextLive\}\_\{L\}\(x\):=\|\\\{y\\in\\Sigma^\{\\\{1,\\dots,2\\ell\+1\\\}\}:xy\\in\\mathrm\{Pref\}\(L\)\\\}\|,\(9\)ShortAcceptL:=\|\{y∈Σ\{0,…,2​ℓ−1\}:y∈L\}\|,\\displaystyle\\mathrm\{ShortAccept\}\_\{L\}:=\|\\\{y\\in\\Sigma^\{\\\{0,\\dots,2\\ell\-1\\\}\}:y\\in L\\\}\|,\(10\)ShortPrefixL:=\|\{y∈Σ\{0,…,2​ℓ\}:y∈Pref​\(L\)\}\|\.\\displaystyle\\mathrm\{ShortPrefix\}\_\{L\}:=\|\\\{y\\in\\Sigma^\{\\\{0,\\dots,2\\ell\\\}\}:y\\in\\mathrm\{Pref\}\(L\)\\\}\|\.\(11\)Here,Σ\{i,i\+1,…,j\}\\Sigma^\{\\\{i,i\+1,\\dots,j\}\\\}denotes the set\{y∈Σ∗:i≤\|y\|≤j\}\\\{y\\in\\Sigma^\{\*\}:i\\leq\|y\|\\leq j\\\}, with\|y\|=0\|y\|=0implying the empty stringy=εy=\\varepsilon\.

In words,IsAcceptL​\(x\)\\mathrm\{IsAccept\}\_\{L\}\(x\)counts the number of suffixesyyhaving length\|y\|∈\{0,1,…,2​ℓ\}\|y\|\\in\\\{0,1,\\dots,2\\ell\\\}for whichx​yxyis inLL,NextLiveL​\(x\)\\mathrm\{NextLive\}\_\{L\}\(x\)counts the number of suffixesyyhaving length\|y\|∈\{1,…,2​ℓ\+1\}\|y\|\\in\\\{1,\\dots,2\\ell\+1\\\}such thatx​yxycan be extended further to form a string inLL,ShortAcceptL\\mathrm\{ShortAccept\}\_\{L\}counts the number of stringsyyhaving length\|y\|∈\{0,…,2​ℓ−1\}\|y\|\\in\\\{0,\\dots,2\\ell\-1\\\}such thatyybelongs toLL, andShortPrefixL\\mathrm\{ShortPrefix\}\_\{L\}counts the number of prefixesyyhaving length\|y\|∈\{0,…,2​ℓ\}\|y\|\\in\\\{0,\\dots,2\\ell\\\}such thatyycan be extended further to form a string inLL\. Note thatShortAcceptL\\mathrm\{ShortAccept\}\_\{L\}andShortPrefixL\\mathrm\{ShortPrefix\}\_\{L\}are global properties of the languageLL\. Furthermore, for anyxx,

0≤IsAcceptL​\(x\),NextLiveL​\(x\),ShortAcceptL,ShortPrefixL≤∑i=12​ℓ\+1ki≤max⁡\(2​ℓ\+1,2​k2​ℓ\+1\)\.\\displaystyle 0\\leq\\mathrm\{IsAccept\}\_\{L\}\(x\),\\mathrm\{NextLive\}\_\{L\}\(x\),\\mathrm\{ShortAccept\}\_\{L\},\\mathrm\{ShortPrefix\}\_\{L\}\\leq\\sum\_\{i=1\}^\{2\\ell\+1\}k^\{i\}\\leq\\max\(2\\ell\+1,2k^\{2\\ell\+1\}\)\.\(12\)
Now fix the paletteP=\{1,2,…,B\}P=\\\{1,2,\\dots,B\\\}, whereB=max⁡\(8​ℓ\+4,8​k2​ℓ\+1\)B=\\max\(8\\ell\+4,8k^\{2\\ell\+1\}\), and define the trace coloring functioncL:Σ∗→Pc\_\{L\}:\\Sigma^\{\*\}\\to Pas follows:

cL​\(x\)=\{IsAcceptL​\(x\)\+NextLiveL​\(x\)\+ShortAcceptL\+ShortPrefixLif​x∈Pref​\(L\),1otherwise\.\\displaystyle c\_\{L\}\(x\)=\\begin\{cases\}\\mathrm\{IsAccept\}\_\{L\}\(x\)\+\\mathrm\{NextLive\}\_\{L\}\(x\)\+\\mathrm\{ShortAccept\}\_\{L\}\+\\mathrm\{ShortPrefix\}\_\{L\}&\\text\{if \}x\\in\\mathrm\{Pref\}\(L\),\\\\ 1&\\text\{otherwise\.\}\\\\ \\end\{cases\}\(13\)
Ifx∉Pref​\(L\)x\\notin\\mathrm\{Pref\}\(L\),cL​\(x\)=1c\_\{L\}\(x\)=1; otherwise, ifx∈Pref​\(L\)x\\in\\mathrm\{Pref\}\(L\), then eitherIsAcceptL​\(x\)\>0\\mathrm\{IsAccept\}\_\{L\}\(x\)\>0, orNextLiveL​\(x\)\>0\\mathrm\{NextLive\}\_\{L\}\(x\)\>0, and hencecL​\(x\)≥1c\_\{L\}\(x\)\\geq 1\. Together with \([12](https://arxiv.org/html/2607.12443#A1.E12)\), this implies thatcL​\(x\)∈Pc\_\{L\}\(x\)\\in Pfor allx∈Σ∗x\\in\\Sigma^\{\*\}\. Similar to the proof of\\Creflemma:main\-coloring\-upper\-bound, we now observe that the quantities defined above satisfy monotonicity on any stringxxwith respect to inclusion\.

###### Observation A\.4\(Monotonicity of Trace Coloring\)

LetL,L′L,L^\{\\prime\}be languages satisfyingL⊆L′L\\subseteq L^\{\\prime\}\. Then, for anyx∈Σ∗x\\in\\Sigma^\{\*\}, it holds that:

\(1\)​IsAcceptL​\(x\)≤IsAcceptL′​\(x\),\(2\)​NextLiveL​\(x\)≤NextLiveL′​\(x\),\\displaystyle\\text\{\(1\) \}\\mathrm\{IsAccept\}\_\{L\}\(x\)\\leq\\mathrm\{IsAccept\}\_\{L^\{\\prime\}\}\(x\),\\quad\\text\{\(2\) \}\\mathrm\{NextLive\}\_\{L\}\(x\)\\leq\\mathrm\{NextLive\}\_\{L^\{\\prime\}\}\(x\),\(3\)​ShortAcceptL≤ShortAcceptL′,\(4\)​ShortPrefixL≤ShortPrefixL′,\(5\)​cL​\(x\)≤cL′​\(x\)\.\\displaystyle\\text\{\(3\) \}\\mathrm\{ShortAccept\}\_\{L\}\\leq\\mathrm\{ShortAccept\}\_\{L^\{\\prime\}\},\\quad\\text\{\(4\) \}\\mathrm\{ShortPrefix\}\_\{L\}\\leq\\mathrm\{ShortPrefix\}\_\{L^\{\\prime\}\},\\quad\\text\{\(5\) \}c\_\{L\}\(x\)\\leq c\_\{L^\{\\prime\}\}\(x\)\.

Now, fix anyL,L′∈𝒞L,L^\{\\prime\}\\in\\mathcal\{C\}for whichL⊊L′L\\subsetneq L^\{\\prime\}, andLLcontains some stringxxhaving length at least2​ℓ2\\ell\.

#### Case 1:ShortAcceptL<ShortAcceptL′\\mathrm\{ShortAccept\}\_\{L\}<\\mathrm\{ShortAccept\}\_\{L^\{\\prime\}\}orShortPrefixL<ShortPrefixL′\\mathrm\{ShortPrefix\}\_\{L\}<\\mathrm\{ShortPrefix\}\_\{L^\{\\prime\}\}\.

In this case, using\\Crefobservation:monotonicity\-trace\-coloring\-corruptions, note thatcL​\(x\)<cL′​\(x\)c\_\{L\}\(x\)<c\_\{L^\{\\prime\}\}\(x\)for everyx∈Lx\\in L\. Then, choose anyx∈Lx\\in Lhaving length at least2​ℓ2\\ell, which is guaranteed to exist by assumption\. We have that each ofcL​\(ε\),cL​\(x≤1\),…,cL​\(x\)c\_\{L\}\(\\varepsilon\),c\_\{L\}\(x\_\{\\leq 1\}\),\\dots,c\_\{L\}\(x\)is strictly smaller thancL′​\(ε\),cL′​\(x≤1\),…,cL′​\(x\)c\_\{L^\{\\prime\}\}\(\\varepsilon\),c\_\{L^\{\\prime\}\}\(x\_\{\\leq 1\}\),\\dots,c\_\{L^\{\\prime\}\}\(x\)respectively, and hence,d​\(tracecL​\(x\),tracecL′​\(x\)\)\>2​ℓd\\left\(\{\\mathrm\{trace\}\}\_\{c\_\{L\}\}\(x\),\{\\mathrm\{trace\}\}\_\{c\_\{L^\{\\prime\}\}\}\(x\)\\right\)\>2\\ellas required\.

#### Case 2:ShortAcceptL=ShortAcceptL′\\mathrm\{ShortAccept\}\_\{L\}=\\mathrm\{ShortAccept\}\_\{L^\{\\prime\}\}andShortPrefixL=ShortPrefixL′\\mathrm\{ShortPrefix\}\_\{L\}=\\mathrm\{ShortPrefix\}\_\{L^\{\\prime\}\}\.

SinceL⊊L′L\\subsetneq L^\{\\prime\},y∈L⟹y∈L′y\\in L\\implies y\\in L^\{\\prime\}, andy∈Pref​\(L\)⟹y∈Pref​\(L′\)y\\in\\mathrm\{Pref\}\(L\)\\implies y\\in\\mathrm\{Pref\}\(L^\{\\prime\}\)\. Therefore, this case implies the stronger properties that

\{y∈Σ\{0,…,2​ℓ−1\}:y∈L\}=\{y∈Σ\{0,…,2​ℓ−1\}:y∈L′\},\\displaystyle\\\{y\\in\\Sigma^\{\\\{0,\\dots,2\\ell\-1\\\}\}:y\\in L\\\}=\\\{y\\in\\Sigma^\{\\\{0,\\dots,2\\ell\-1\\\}\}:y\\in L^\{\\prime\}\\\},\(14\)\{y∈Σ\{0,…,2​ℓ\}:y∈Pref​\(L\)\}=\{y∈Σ\{0,…,2​ℓ\}:y∈Pref​\(L′\)\}\.\\displaystyle\\\{y\\in\\Sigma^\{\\\{0,\\dots,2\\ell\\\}\}:y\\in\\mathrm\{Pref\}\(L\)\\\}=\\\{y\\in\\Sigma^\{\\\{0,\\dots,2\\ell\\\}\}:y\\in\\mathrm\{Pref\}\(L^\{\\prime\}\)\\\}\.\(15\)Now, fix anyz∈L′∖Lz\\in L^\{\\prime\}\\setminus L\. Note that by \([14](https://arxiv.org/html/2607.12443#A1.E14)\), it must be the case that\|z\|≥2​ℓ\|z\|\\geq 2\\ell\. We then have the following two subcases:

#### Subcase 2a:z∈Pref​\(L\)z\\in\\mathrm\{Pref\}\(L\)\.

In this case, lett∈Σ∗t\\in\\Sigma^\{\*\}be such thatz​t∈Lzt\\in L\(note thatt≠εt\\neq\\varepsilon, sincez∉Lz\\notin L\)\. We claim thatx:=z​tx:=ztsatisfies thatd​\(tracecL​\(x\),tracecL′​\(x\)\)\>2​ℓd\\left\(\{\\mathrm\{trace\}\}\_\{c\_\{L\}\}\(x\),\{\\mathrm\{trace\}\}\_\{c\_\{L^\{\\prime\}\}\}\(x\)\\right\)\>2\\ell\. To see this, letz=z0​z1,…,znz=z\_\{0\}z\_\{1\},\\dots,z\_\{n\}, wherez0=εz\_\{0\}=\\varepsilonandn≥2​ℓn\\geq 2\\ell\. For anyp≤qp\\leq q, denotezp:q:=zp​zp\+1​…,zqz\_\{p:q\}:=z\_\{p\}z\_\{p\+1\}\\dots,z\_\{q\}\. We then observe that for anyi∈\{0,1,…,2​ℓ\}i\\in\\\{0,1,\\dots,2\\ell\\\},IsAcceptL​\(z0:n−i\)\\mathrm\{IsAccept\}\_\{L\}\(z\_\{0:n\-i\}\)is strictly smaller thanIsAcceptL′​\(z0:n−i\)\\mathrm\{IsAccept\}\_\{L^\{\\prime\}\}\(z\_\{0:n\-i\}\); this is because there exists a suffixy=zn−i\+1:ny=z\_\{n\-i\+1:n\}having length\|y\|∈\{0,…,2​ℓ\}\|y\|\\in\\\{0,\\dots,2\\ell\\\}, for whichz0:n−i​y∉Lz\_\{0:n\-i\}y\\notin Lbutz0:n−i​y∈L′z\_\{0:n\-i\}y\\in L^\{\\prime\}\(note thatz0:n−i​yz\_\{0:n\-i\}yis simply equal tozz\)\. This implies that d​\(tracecL​\(x\),tracecL′​\(x\)\)\>2​ℓd\\left\(\{\\mathrm\{trace\}\}\_\{c\_\{L\}\}\(x\),\{\\mathrm\{trace\}\}\_\{c\_\{L^\{\\prime\}\}\}\(x\)\\right\)\>2\\ell\.

#### Subcase 2b:z∉Pref​\(L\)z\\notin\\mathrm\{Pref\}\(L\)\.

In this case, letw∈Σ∗w\\in\\Sigma^\{\*\}be the maximal prefix ofzzthat satisfiesw∈Pref​\(L\)w\\in\\mathrm\{Pref\}\(L\), and letz=w​a​tz=wat, wherea∈Σa\\in\\Sigma, andt∈Σ∗t\\in\\Sigma^\{\*\}\. Here, by maximal, we mean thatw​a∉Pref​\(L\)wa\\notin\\mathrm\{Pref\}\(L\)\. We first claim that\|w\|≥2​ℓ\|w\|\\geq 2\\ell\. To see this, suppose that\|w\|<2​ℓ\|w\|<2\\ell\. In this case,\|w​a\|≤2​ℓ\|wa\|\\leq 2\\ell\. But it also holds thatw​a∉Pref​\(L\)wa\\notin\\mathrm\{Pref\}\(L\), andw​a∈Pref​\(L′\)wa\\in\\mathrm\{Pref\}\(L^\{\\prime\}\)\(sincez=w​a​t∈L′z=wat\\in L^\{\\prime\}\)\. This contradicts \([15](https://arxiv.org/html/2607.12443#A1.E15)\)\. Thus,\|w\|≥2​ℓ\|w\|\\geq 2\\ell\.

So, letw=w0​w1,…,wnw=w\_\{0\}w\_\{1\},\\dots,w\_\{n\}, wherew0=εw\_\{0\}=\\varepsilon\. We now argue that for everyi∈\{0,1,…,2​ℓ\}i\\in\\\{0,1,\\dots,2\\ell\\\},NextLiveL​\(w0:n−i\)\\mathrm\{NextLive\}\_\{L\}\(w\_\{0:n\-i\}\)is strictly smaller thanNextLiveL′​\(w0:n−i\)\\mathrm\{NextLive\}\_\{L^\{\\prime\}\}\(w\_\{0:n\-i\}\)\. Again, this holds because there exists a suffixy=wn−i\+1:n​ay=w\_\{n\-i\+1:n\}ahaving length\|y\|∈\{1,…,2​ℓ\+1\}\|y\|\\in\\\{1,\\dots,2\\ell\+1\\\}, for whichw0:n−i​y∉Pref​\(L\)w\_\{0:n\-i\}y\\notin\\mathrm\{Pref\}\(L\)butw0:n−i​y∉Pref​\(L′\)w\_\{0:n\-i\}y\\notin\\mathrm\{Pref\}\(L^\{\\prime\}\)\(note thatw0:n−i​yw\_\{0:n\-i\}yis simply equal tow​awa\)\. This then implies that d​\(tracecL​\(x\),tracecL′​\(x\)\)\>2​ℓd\\left\(\{\\mathrm\{trace\}\}\_\{c\_\{L\}\}\(x\),\{\\mathrm\{trace\}\}\_\{c\_\{L^\{\\prime\}\}\}\(x\)\\right\)\>2\\ell\.

In both cases, we have shown the existence of anx∈Lx\\in Lsatisfyingd​\(tracecL​\(x\),tracecL′​\(x\)\)\>2​ℓd\\left\(\{\\mathrm\{trace\}\}\_\{c\_\{L\}\}\(x\),\{\\mathrm\{trace\}\}\_\{c\_\{L^\{\\prime\}\}\}\(x\)\\right\)\>2\\ell, as required\.

## Appendix BTraces for Regular Languages

We give a formal definition of a DFA following the textbooksSipser \([1996](https://arxiv.org/html/2607.12443#bib.bib9)\); Hopcroft et al\. \([2001](https://arxiv.org/html/2607.12443#bib.bib6)\):

###### Definition B\.1\(Deterministic Finite\-State Automaton \(DFA\)\.

A DFAMMover a finite alphabetΣ\\Sigmais a 5\-tupleM=\(Q​\(M\),Σ,δM,q0​\(M\),F​\(M\)\)M=\(Q\(M\),\\Sigma,\\delta\_\{M\},q\_\{0\}\(M\),F\(M\)\), whereQ​\(M\)Q\(M\)is a finite set of states,δM:Q​\(M\)×Σ→Q​\(M\)\\delta\_\{M\}:Q\(M\)\\times\\Sigma\\to Q\(M\)is a state transition function,q0​\(M\)∈Q​\(M\)q\_\{0\}\(M\)\\in Q\(M\)is the initial state, andF​\(M\)⊆Q​\(M\)F\(M\)\\subseteq Q\(M\)is the set of accepting states\. The regular languageL​\(M\)L\(M\)that is accepted by the DFAMMis defined as the setL​\(M\)=\{x∈Σ∗:δM​\(q0​\(M\),x\)∈F​\(M\)\}L\(M\)=\\\{x\\in\\Sigma^\{\*\}:\\delta\_\{M\}\(q\_\{0\}\(M\),x\)\\in F\(M\)\\\}\.

We can extend the domain of the transition functionδM\\delta\_\{M\}fromΣ\\SigmatoΣ∗\\Sigma^\{\*\}by definingδM​\(q,ε\)=q\\delta\_\{M\}\(q,\\varepsilon\)=q, and recursively definingδM​\(q,a​y\)=δM​\(δM​\(q,a\),y\)\\delta\_\{M\}\(q,ay\)=\\delta\_\{M\}\(\\delta\_\{M\}\(q,a\),y\), for everyq∈Q​\(M\),a∈Σq\\in Q\(M\),a\\in\\Sigmaandy∈Σ∗y\\in\\Sigma^\{\*\}\.

### B\.1Corrupted State Traces

As we did in\\Crefsec:state\-machines, we describe how we can derive state coloring functions that are robust to corruptions in state traces from the trace coloring functions constructed in\\Creflemma:corruptions\-coloring\-upper\-bound above\. Consider any DFAMMin a given collection𝒞=\{M1,M2,…\}\\mathcal\{C\}=\\\{M\_\{1\},M\_\{2\},\\dots\\\}, and fixℓ\>0\\ell\>0\. For anyq∈Q​\(M\)q\\in Q\(M\), define

IsAcceptM​\(q\):=\|\{y∈Σ\{0,…,2​ℓ\}:δM​\(q,y\)∈F​\(M\)\}\|,\\displaystyle\\mathrm\{IsAccept\}\_\{M\}\(q\):=\|\\\{y\\in\\Sigma^\{\\\{0,\\dots,2\\ell\\\}\}:\\delta\_\{M\}\(q,y\)\\in F\(M\)\\\}\|,\(16\)NextLiveM​\(q\):=\|\{y∈Σ\{1,…,2​ℓ\+1\}:δM​\(q,y\)​is live\}\|,\\displaystyle\\mathrm\{NextLive\}\_\{M\}\(q\):=\|\\\{y\\in\\Sigma^\{\\\{1,\\dots,2\\ell\+1\\\}\}:\\delta\_\{M\}\(q,y\)\\text\{ is live\}\\\}\|,\(17\)ShortAcceptM:=\|\{y∈Σ\{0,…,2​ℓ−1\}:δM​\(q0​\(M\),y\)∈F​\(M\)\}\|,\\displaystyle\\mathrm\{ShortAccept\}\_\{M\}:=\|\\\{y\\in\\Sigma^\{\\\{0,\\dots,2\\ell\-1\\\}\}:\\delta\_\{M\}\(q\_\{0\}\(M\),y\)\\in F\(M\)\\\}\|,\(18\)ShortPrefixM:=\|\{y∈Σ\{0,…,2​ℓ\}:δM​\(q0​\(M\),y\)​is live\}\|\.\\displaystyle\\mathrm\{ShortPrefix\}\_\{M\}:=\|\\\{y\\in\\Sigma^\{\\\{0,\\dots,2\\ell\\\}\}:\\delta\_\{M\}\(q\_\{0\}\(M\),y\)\\text\{ is live\}\\\}\|\.\(19\)Note thatShortAcceptM\\mathrm\{ShortAccept\}\_\{M\}andShortPrefixM\\mathrm\{ShortPrefix\}\_\{M\}are global properties of the DFAMM\.

Now fix the paletteP=\{1,2,…,B\}P=\\\{1,2,\\dots,B\\\}, whereB=max⁡\(8​ℓ\+4,8​k2​ℓ\+1\)B=\\max\(8\\ell\+4,8k^\{2\\ell\+1\}\), and define the state coloring functioncM:Q​\(M\)→Pc\_\{M\}:Q\(M\)\\to Pas follows:

cM​\(q\)=\{IsAcceptM​\(q\)\+NextLiveM​\(q\)\+ShortAcceptM\+ShortPrefixMifqis live,1otherwise\.\\displaystyle c\_\{M\}\(q\)=\\begin\{cases\}\\mathrm\{IsAccept\}\_\{M\}\(q\)\+\\mathrm\{NextLive\}\_\{M\}\(q\)\+\\mathrm\{ShortAccept\}\_\{M\}\+\\mathrm\{ShortPrefix\}\_\{M\}&\\text\{if $q$ is live\},\\\\ 1&\\text\{otherwise\.\}\\\\ \\end\{cases\}\(20\)For anyx=x0​x1​…​xn∈L​\(M\)x=x\_\{0\}x\_\{1\}\\dots x\_\{n\}\\in L\(M\)\(wherex0=εx\_\{0\}=\\varepsilon\), which traverses the statesq0,q1,…,qnq\_\{0\},q\_\{1\},\\dots,q\_\{n\}inMM, we have that

cM​\(qi\)=cL​\(M\)​\(x0​x1​…​xi\),\\displaystyle c\_\{M\}\(q\_\{i\}\)=c\_\{L\(M\)\}\(x\_\{0\}x\_\{1\}\\dots x\_\{i\}\),wherecL​\(M\)c\_\{L\(M\)\}is exactly the trace coloring function defined in \([13](https://arxiv.org/html/2607.12443#A1.E13)\) in the proof of\\Creflemma:corruptions\-coloring\-upper\-bound\. Thus, we have that for anyM,M′∈𝒞M,M^\{\\prime\}\\in\\mathcal\{C\}satisfyingL​\(M\)⊊L​\(M′\)L\(M\)\\subsetneq L\(M^\{\\prime\}\), there exists anx∈L​\(M\)x\\in L\(M\)for whichd​\(tracecM​\(x\),tracecM′​\(x\)\)\>2​ℓd\\left\(\{\\mathrm\{trace\}\}\_\{c\_\{M\}\}\(x\),\{\\mathrm\{trace\}\}\_\{c\_\{M^\{\\prime\}\}\}\(x\)\\right\)\>2\\ell, and we can identify𝒞\\mathcal\{C\}in the limit using state color traces having at mostℓ\\ellcorruptions\.

Analogous to\\Creflemma:state\-coloring\-optimal\-bound, we next show that the palette size used above is optimal in order for state coloring functions in general\.

###### Claim 1\(k2​ℓ−1k^\{2\\ell\-1\}Colors Necessary for Corrupted State Traces\)\.

For anyk≥1k\\geq 1andℓ\>0\\ell\>0, there exists a finite collection𝒞\\mathcal\{C\}of DFAs over the alphabetΣ=\{1,2,…,k\}\\Sigma=\\\{1,2,\\dots,k\\\}, such that any family of state coloring functions\{cM\}M∈𝒞\\\{c\_\{M\}\\\}\_\{M\\in\\mathcal\{C\}\}which satisfies: for every pair of DFAsM,M′∈𝒞M,M^\{\\prime\}\\in\\mathcal\{C\}satisfying thatL​\(M\)⊊L​\(M′\)L\(M\)\\subsetneq L\(M^\{\\prime\}\), there existsx∈L​\(M\)x\\in L\(M\)for whichd​\(tracecM​\(x\),tracecM′​\(x\)\)\>2​ℓd\\left\(\{\\mathrm\{trace\}\}\_\{c\_\{M\}\}\(x\),\{\\mathrm\{trace\}\}\_\{c\_\{M^\{\\prime\}\}\}\(x\)\\right\)\>2\\ell, necessarily requires a palette of sizek2​ℓ−1k^\{2\\ell\-1\}\.

###### Proof B\.2\.

LetN=k2​ℓ−1N=k^\{2\\ell\-1\}, andS=\{s1,…,sN\}S=\\\{s\_\{1\},\\dots,s\_\{N\}\\\}be an ordering of all strings of size2​ℓ−12\\ell\-1inΣ2​ℓ−1\\Sigma^\{2\\ell\-1\}\. Consider the collection𝒞=\{M1,…,MN\}\\mathcal\{C\}=\\\{M\_\{1\},\\dots,M\_\{N\}\\\}, where eachMiM\_\{i\}accepts the regular language

L​\(Mi\)=\{w​y:w∈\{s1,…,si\},y∈Σ∗\}\.\\displaystyle L\(M\_\{i\}\)=\\\{wy:w\\in\\\{s\_\{1\},\\dots,s\_\{i\}\\\},y\\in\\Sigma^\{\*\}\\\}\.\(21\)Namely,L​\(Mi\)L\(M\_\{i\}\)has strings of the formw​ywy, wherewwis any of the firstiistrings inSS, andyyis any suffix inΣ∗\\Sigma^\{\*\}\. We have thatL​\(M1\)⊊L​\(M2\)⊊⋯⊊L​\(MN\)L\(M\_\{1\}\)\\subsetneq L\(M\_\{2\}\)\\subsetneq\\dots\\subsetneq L\(M\_\{N\}\)\.

Now observe that eachMiM\_\{i\}can be specified by a DFA that first builds a prefix tree over the set\{s1,…,si\}\\\{s\_\{1\},\\dots,s\_\{i\}\\\}, followed by an accepting sink state\. Namely, for anyxx, the prefix tree part checks whether the first2​ℓ−12\\ell\-1characters ofxxbelong to\{s1,…,si\}\\\{s\_\{1\},\\dots,s\_\{i\}\\\}—if they do, then the string is accepted\. Letq0​\(Mi\)q\_\{0\}\(M\_\{i\}\)be the initial state ofMiM\_\{i\}\(i\.e\., the root of the prefix tree\), and letqF​\(Mi\)q\_\{F\}\(M\_\{i\}\)be the single accepting sink state\. Note then that anyx∈L​\(Mi\)x\\in L\(M\_\{i\}\)traverses a sequence of states of the form

q0​\(Mi\)→qj1​\(Mi\)→…→qj2​ℓ−1​\(Mi\)⏟prefix tree→qF​\(Mi\)→…→qF​\(Mi\)⏟loop on accepting sink state\.\\displaystyle\\underbrace\{q\_\{0\}\(M\_\{i\}\)\\to q\_\{j\_\{1\}\}\(M\_\{i\}\)\\to\\dots\\to q\_\{j\_\{2\\ell\-1\}\}\(M\_\{i\}\)\}\_\{\\text\{prefix tree\}\}\\to\\underbrace\{q\_\{F\}\(M\_\{i\}\)\\to\\dots\\to q\_\{F\}\(M\_\{i\}\)\}\_\{\\text\{loop on accepting sink state\}\}\.\(22\)
Now, fix any state coloring functionscM1,…,cMNc\_\{M\_\{1\}\},\\dots,c\_\{M\_\{N\}\}that use a palettePPof sizeN−1N\-1, and satisfy that for everyMi,MjM\_\{i\},M\_\{j\}withL​\(Mi\)⊊L​\(Mj\)L\(M\_\{i\}\)\\subsetneq L\(M\_\{j\}\), there existsx∈L​\(Mi\)x\\in L\(M\_\{i\}\)for which d​\(tracecMi​\(x\),tracecMj​\(x\)\)\>2​ℓd\\left\(\{\\mathrm\{trace\}\}\_\{c\_\{M\_\{i\}\}\}\(x\),\{\\mathrm\{trace\}\}\_\{c\_\{M\_\{j\}\}\}\(x\)\\right\)\>2\\ell\.

Fix anyi,j∈\{1,…,N\}i,j\\in\\\{1,\\dots,N\\\}satisfyingi<ji<j\. For anyx∈L​\(Mi\)x\\in L\(M\_\{i\}\), by the characterization \([22](https://arxiv.org/html/2607.12443#A2.E22)\) of the sequence of states traversed byxxinMiM\_\{i\}, we get thattracecMi​\(x\)\{\\mathrm\{trace\}\}\_\{c\_\{M\_\{i\}\}\}\(x\)is some sequence inP2​ℓP^\{2\\ell\}, followed by the sequence\(cMi​\(qF​\(Mi\)\),…,cMi​\(qF​\(Mi\)\)\)⏟\|x\|−2​ℓ\+1​times\\underbrace\{\(c\_\{M\_\{i\}\}\(q\_\{F\}\(M\_\{i\}\)\),\\dots,c\_\{M\_\{i\}\}\(q\_\{F\}\(M\_\{i\}\)\)\)\}\_\{\|x\|\-2\\ell\+1\\text\{ times\}\}\. Similarly, we have thattracecMj​\(x\)\{\\mathrm\{trace\}\}\_\{c\_\{M\_\{j\}\}\}\(x\)is some sequence inP2​ℓP^\{2\\ell\}, followed by the sequencecMj​\(qF​\(Mj\),…,cMj​\(qF​\(Mj\)\)\)⏟\|x\|−2​ℓ\+1​times\\underbrace\{c\_\{M\_\{j\}\}\(q\_\{F\}\(M\_\{j\}\),\\dots,c\_\{M\_\{j\}\}\(q\_\{F\}\(M\_\{j\}\)\)\)\}\_\{\|x\|\-2\\ell\+1\\text\{ times\}\}\. Thus, in order ford​\(tracecMi​\(x\),tracecMj​\(x\)\)\>2​ℓd\\left\(\{\\mathrm\{trace\}\}\_\{c\_\{M\_\{i\}\}\}\(x\),\{\\mathrm\{trace\}\}\_\{c\_\{M\_\{j\}\}\}\(x\)\\right\)\>2\\ellto hold, we necessarily require thatcMi​\(qF​\(Mi\)\)≠cMj​\(qF​\(Mj\)\)c\_\{M\_\{i\}\}\(q\_\{F\}\(M\_\{i\}\)\)\\neq c\_\{M\_\{j\}\}\(q\_\{F\}\(M\_\{j\}\)\)\. But this is not possible for everyi<ji<j, if the state coloring functions use onlyN−1N\-1colors\.

### B\.2Identifying Regular Languages with Two Colors

###### Lemma B\.3\(Increasing Live, Reachable States in DFA\)\.

LetMMbe a DFA satisfying\|L​\(M\)\|=∞\|L\(M\)\|=\\infty, and letMMhavennstates that are live and reachable\. Then, for anyk\>0k\>0, there exists a DFAM′M^\{\\prime\}satisfyingL​\(M′\)=L​\(M\)L\(M^\{\\prime\}\)=L\(M\), such thatM′M^\{\\prime\}hasn\+kn\+kstates that are live and reachable\.

###### Proof B\.4\.

SinceL​\(M\)L\(M\)is infinite, it must contain strings of arbitrarily large length\. Letx=x1​x2​…​xtx=x\_\{1\}x\_\{2\}\\dots x\_\{t\}be any string inL​\(M\)L\(M\)having lengtht≥nt\\geq n\. Then, consider the sequence of statesq0,q1,…,qtq\_\{0\},q\_\{1\},\\dots,q\_\{t\}traversed byxxinMM: note that every state in this sequence is live and reachable\. Then, since there are onlynnlive and reachable states inMM, and the number of states in this sequence ist\+1\>nt\+1\>n, by the pigeonhole principle, there exists at least one live and reachable state that appears twice in the sequence\. Letssbe the smallest index for which there existsi<si<ssuch thatqi=qsq\_\{i\}=q\_\{s\}\(i\.e\., this is the first time a state got repeated in the sequence\), and consider the intermediate sequence of transitionsqi→qi\+1→…→qs−1→qsq\_\{i\}\\to q\_\{i\+1\}\\to\\dots\\to q\_\{s\-1\}\\to q\_\{s\}, together with the symbolsxi\+1,…,xs−1,xsx\_\{i\+1\},\\dots,x\_\{s\-1\},x\_\{s\}that effected these transitions\. Note that by the choice ofss, the statesq0,…,qs−1q\_\{0\},\\dots,q\_\{s\-1\}are all distinct\.

Now, consider a DFAM′M^\{\\prime\}that operates on the same alphabetΣ\\Sigma\.M′M^\{\\prime\}has a copyq′q^\{\\prime\}of every stateqqinMM, plus an additional stateqnew′q^\{\\prime\}\_\{\{\\mathrm\{new\}\}\}\. The state transitions for all the states inM′M^\{\\prime\}are identical to their copies inMM, except for the statesqs−1′q^\{\\prime\}\_\{s\-1\}andqnew′q^\{\\prime\}\_\{\{\\mathrm\{new\}\}\}, whereqs−1q\_\{s\-1\}is the copy of the stateqs−1q\_\{s\-1\}, andqnew′q^\{\\prime\}\_\{\{\\mathrm\{new\}\}\}is the additional new state\. The state transitions forqs−1′q^\{\\prime\}\_\{s\-1\}andqnewq\_\{\{\\mathrm\{new\}\}\}are as follows\. First, we make the transitions out ofqnew′q^\{\\prime\}\_\{\\mathrm\{new\}\}to be identical to those out ofqsq\_\{s\}, i\.e\., setδM′​\(qnew′,a\)\\delta\_\{M^\{\\prime\}\}\(q^\{\\prime\}\_\{\{\\mathrm\{new\}\}\},a\)to be the copy ofδM​\(qs,a\)\\delta\_\{M\}\(q\_\{s\},a\)for everya∈Σa\\in\\Sigma\. Next, we redirect the single transitionqs−1′→xsqs′q^\{\\prime\}\_\{s\-1\}\\xrightarrow\{x\_\{s\}\}q^\{\\prime\}\_\{s\}to beqs−1′→xsqnew′q^\{\\prime\}\_\{s\-1\}\\xrightarrow\{x\_\{s\}\}q^\{\\prime\}\_\{\\mathrm\{new\}\}instead; namely, for anya≠xsa\\neq x\_\{s\}, we setδM′​\(qs−1′,a\)\\delta\_\{M^\{\\prime\}\}\(q^\{\\prime\}\_\{s\-1\},a\)to be the copy of the stateδM​\(qs−1,a\)\\delta\_\{M\}\(q\_\{s\-1\},a\), and we makeqnew′q^\{\\prime\}\_\{\{\\mathrm\{new\}\}\}reachable by settingδM′​\(qs−1′,xs\)=qnew′\\delta\_\{M^\{\\prime\}\}\(q^\{\\prime\}\_\{s\-1\},x\_\{s\}\)=q^\{\\prime\}\_\{\{\\mathrm\{new\}\}\}\. In essence, we have redirected the transition fromqs−1′q^\{\\prime\}\_\{s\-1\}which was looping back intoqs′q^\{\\prime\}\_\{s\}to the new stateqnew′q^\{\\prime\}\_\{\{\\mathrm\{new\}\}\}, whose outward transitions are then identical toqsq\_\{s\}\. The initial state inM′M^\{\\prime\}is set to the copy of the initial state inMM, and the accepting states inM′M^\{\\prime\}are set to the copies of the accepting states inMM, plus the stateqnew′q^\{\\prime\}\_\{\{\\mathrm\{new\}\}\}ifqsq\_\{s\}was an accepting state\. This completes the specification ofM′M^\{\\prime\}\.

We now argue thatM′M^\{\\prime\}hasn\+1n\+1live and reachable states, and thatL​\(M′\)=L​\(M\)L\(M^\{\\prime\}\)=L\(M\); the lemma is then established by inducting thiskktimes\. First, it is clear that for any stateqqinMMthat was either not live or reachable inMM, its copyq′q^\{\\prime\}has the same status inM′M^\{\\prime\}\. Now, by construction, the newly added stateqnew′q^\{\\prime\}\_\{\{\\mathrm\{new\}\}\}and the stateqs′q^\{\\prime\}\_\{s\}are both live and reachable, as witnessed by the traversal ofxxthroughM′M^\{\\prime\}, which passes through bothqs′q^\{\\prime\}\_\{s\}andqnew′q^\{\\prime\}\_\{\\mathrm\{new\}\}on the way to an accepting state\. Finally, for every stateq≠qsq\\neq q\_\{s\}that was live and reachable inMM, its copyq′q^\{\\prime\}remains live and reachable inM′M^\{\\prime\}\. This can be seen by tracing out the sequence of states traversed by anyy∈L​\(M\)y\\in L\(M\)that passed throughqqon the way to an accepting state inMM\. In its traversal throughM′M^\{\\prime\}, the only notable change is that a transition of the formqs−1→xsqsq\_\{s\-1\}\\xrightarrow\{x\_\{s\}\}q\_\{s\}gets replaced byqs−1′→xsqnew′q^\{\\prime\}\_\{s\-1\}\\xrightarrow\{x\_\{s\}\}q^\{\\prime\}\_\{\{\\mathrm\{new\}\}\}\. But since the transitions out ofqnew′q^\{\\prime\}\_\{\\mathrm\{new\}\}are identical toqsq\_\{s\},yycontinues on its path to an accepting state, and any occurrences ofqqin the traversal throughMMoverlap with occurrences ofq′q^\{\\prime\}in the traversal throughM′M^\{\\prime\}; thus,q′q^\{\\prime\}remains live and reachable inM′M^\{\\prime\}\. Thus, we have argued thatM′M^\{\\prime\}hasn\+1n\+1live and reachable states\.

It remains to argue thatL​\(M′\)=L​\(M\)L\(M^\{\\prime\}\)=L\(M\)\. Again, this is made clear by tracing out the traversal of anyxxthroughMMandM′M^\{\\prime\}: if the traversal never uses the single redirected transitionqs−1′→xsqnew′q^\{\\prime\}\_\{s\-1\}\\xrightarrow\{x\_\{s\}\}q^\{\\prime\}\_\{\{\\mathrm\{new\}\}\}, then the end outcomes are clearly identical; if it does use this transition, then inMM, the transition leads into the stateqsq\_\{s\}, whereas inM′M^\{\\prime\}, the transition leads into the stateqnew′q^\{\\prime\}\_\{\\mathrm\{new\}\}; however, since the transitions out ofqnew′q^\{\\prime\}\_\{\\mathrm\{new\}\}andqsq\_\{s\}are identical, the end outcome is identical as well\.