Proceedings of Machine Learning Research vol 336:1–21, 2026
39th Annual Conference on Learning Theory
Language Identification with Succinct Machine-Independent Traces Moses Charikar
MOSES @ CS . STANFORD . EDU
Stanford University
Jon Kleinberg
KLEINBERG @ CORNELL . EDU
Cornell University
Chirag Pabbaraju
CPABBARA @ CS . STANFORD . EDU
Stanford University
Editors: Steve Hanneke and Tor Lattimore
arXiv:2607.12443v1 [cs.CL] 14 Jul 2026
Abstract Motivated by the power of large language models, there has been renewed interest in the GoldAngluin model of language identification in the limit, with an eye toward variants of the model that might overcome the negative results for its original formulation. Recent papers on this question have proposed looking at computational traces and annotations of training strings as a source of additional power for a learner, reflecting empirical regularities such as the way that commented source code is easier to learn from than arbitrary source code, and text annotated with algorithmically generated chain-of-thought tokens can be easier to learn from than the raw text itself. This recent work has shown positive results for language identification in the presence of such computational traces, but the traces in these positive results come from explicit automata-theoretic machine models that generate the language, where the underlying vocabulary of tokens for the traces is very large. In this paper, we address two fundamental issues left open by this line of work: can we achieve positive results with traces that use only a small alphabet, and can we define traces directly from the language itself, without requiring an underlying machine model that generates it? We establish positive results for both of these questions: for an arbitrary collection of languages, we show how to define computational traces that enable identification in the limit, using an alphabet of tokens that is linear in the size of the alphabet that the languages are defined over, and independent of any other properties of the languages. Keywords: language models, identification in the limit, computational traces
1. Introduction 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 on language identification in the limit (Gold, 1967), in which we view the language learning task as a game played between an adversary and an algorithm: the adversary thinks of a secret language K known only to come from a countable list of candidates L1 , L2 , L3 , ...; the adversary enumerates the strings of K in an arbitrary order1 ; in each step t the algorithm guesses the index it of the true language; and the algorithm wins the game (it has identified K in the limit) if for some time t∗ , and all t ≥ t∗ , we have Lit = K — the algorithm is correct in every step beginning with t∗ . 1. A valid enumeration x1 , x2 , . . . of K satisfies: (1) xi ∈ K, for all i, and (2) ∀x ∈ K, there exists i such that xi = x. © 2026 M. Charikar, J. Kleinberg & C. Pabbaraju.
C HARIKAR K LEINBERG PABBARAJU
The main results in Gold’s framework, beginning with Gold’s original theorem about his model, are negative (Gold, 1967); 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). 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 of annotation or computational traces in helping solve the problem of language identification in the limit (Papazov and Flammarion, 2025; Bhattamishra et al., 2026; Peng et al., 2026). 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 of chain-of-thought and related methods (Wei et al., 2022). 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), 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). 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 highlevel overview of it. As a starting point, let’s consider how earlier machine-based models defined 2
L ANGUAGE I DENTIFICATION WITH S UCCINCT M ACHINE -I NDEPENDENT T RACES
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 if x = x1 x2 . . . xn is the input string, then the trace annotates each input symbol xi with an annotation symbol ci (corresponding to the state of the automaton at that point); and because ci is the state, it depends only on the prefix x1 x2 . . . xi up to that point, and not any subsequent symbols. We use this as the defining property of our traces: we say that a trace coloring function c over a finite set of colors P (the “palette”) is a function that maps finite strings to elements of P , and we define the color trace of a string x = x1 x2 . . . xn to be the value of c applied to each of its prefixes: tracec (x) := (c(ε), c(x≤1 ), c(x≤2 ), . . . , c(x≤n ))
(1)
where x≤i denotes the prefix x1 x2 . . . xi and ε denotes the empty string. A coloring of x by 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 languages L1 , L2 , L3 , . . ., we consider a process in which each language Li is first annotated by its own trace coloring function cLi , and then an adversary enumerates the strings x ∈ K, each as an annotated pair consisting of x and its color trace, (x, tracecK (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 A such that for any collection of candidate languages L1 , L2 , L3 , . . ., there exists a choice of trace colorings cL1 , cL2 , cL3 , . . . for which A is able to achieve identification in the limit when presented with the ordered pairs (x, tracecK (x)) arising from an enumeration of the adversary’s language K. Moreover, the trace colorings required can be constructed using very few colors: for problem instances with an alphabet of size k, there is an algorithm that achieves this using trace colorings with palettes of size at most k + 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 resourceefficient 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 (when k = 2): our result shows how to achieve the required condition with k + 1 = 3 colors, 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 languages L1 , L2 , L3 , . . . are regular, we can achieve identification in the limit with trace coloring functions that use only two colors. 3
C HARIKAR K LEINBERG PABBARAJU
1.1. Main Results Given a language collection2 C, our objective is to associate every language L in C with a suitable trace coloring function cL , such that when every x ∈ L is accompanied with tracecL (x), the collection 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) for identification in the limit, but additionally takes into account the color traces seen in the input; the proof is given in Section A.1. Theorem 1 (Characterization of Identification in the Limit with Color Traces) Let C be a countable language collection. Then, C is identifiable in the limit with a color trace given by the trace coloring functions {cL }L∈C if and only if for every language L ∈ C, there exists a finite “tell-tale” subset TL ⊆ L, such that for every language L′ ∈ C that is a proper subset of L, either (1) L′ does not contain TL , or (2) there exists x ∈ L′ such that tracecL′ (x) ̸= tracecL (x). The characterization above gives a precise objective for constructing trace coloring functions {cL }L∈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 they always satisfy requirement (2) above. Lemma 2 (Coloring Lemma) Let C be a language collection over a finite alphabet Σ of size k. There exist trace coloring functions {cL }L∈C mapping to a palette P of size k + 1, that satisfy the following “distinguishable coloring condition”: for every L, L′ ∈ C that satisfy L ⊊ L′ , there exists x ∈ L for which tracecL (x) ̸= tracecL′ (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 (Proposition 8): 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 Theorem 1 always holds, tell-tale sets are not needed and we get our main result: Theorem 3 (Identification in the Limit with k + 1 Colors) Let C be a countable language collection over a finite alphabet Σ of size k. There exist trace coloring functions {cL }L∈C mapping to a palette P of size k + 1 that make 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 Theorem 3 above have a particularly special structure for regular language collections. Concretely, consider a regular language L, and let M be any finite automaton that recognizes L. Denote its set of states by Q(M ). For any state q in Q(M ), all strings that arrive at this state q (starting from the initial state) are assigned the same color by our state coloring function cL for language L. Now, associate the state q with this common color. Then, for any x ∈ L, the sequence of colors associated with the sequence of states it traverses in M would exactly equal the color trace generated by our trace coloring function on x. Thus, for a regular language, our trace coloring functions cL can be 2. All languages in the collection are assumed to be non-empty.
4
L ANGUAGE I DENTIFICATION WITH S UCCINCT M ACHINE -I NDEPENDENT T RACES
described very compactly, by simply specifying the unique color associated with every state in any automaton recognizing L. This structural property of our trace coloring functions motivates studying a natural class of trace coloring functions that come from directly coloring the states of automata for regular languages — we denote these as state coloring functions. Concretely, a state coloring function cM maps every state in Q(M ) to a palette P . Denoting L(M ) to be the regular language recognized by M , every x ∈ L(M ) has a well-defined state color trace associated with it: if x traverses the sequence of states q0 , . . . , q|x| in M , then the state color trace is simply tracecM (x) := (cM (q0 ), . . . , cM (q|x| )).
(2)
The work of Peng et al. (2026) and Bhattamishra et al. (2026) can be viewed in this framework (see Section 1.2 for a discussion). For the computational traces used by Peng et al. (2026), 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), we can now study the distinguishable coloring condition for any given collection C = {M1 , M2 , . . . } of finite automata. By the reasoning above, we can show that state coloring functions derived from our trace coloring functions satisfy the condition with k + 1 colors. 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 arbitrary automaton collections, we show that k + 1 is the optimal palette size achievable by state coloring functions for the distinguishable coloring condition for any alphabet size k. Lemma 4 (State Coloring Lemma) Let C be an automata collection over an alphabet of size k. There exist state coloring functions {cM }M ∈C mapping to a palette P of size k + 1, such that for any M, M ′ ∈ C that satisfy L(M ) ⊊ L(M ′ ), there exists x ∈ L(M ) for which tracecM (x) ̸= tracecM ′ (x). Moreover, for any k, there exists a collection of automata over an alphabet of size k such that any set of state coloring functions requires k + 1 colors to satisfy this condition. Lemma 4 above is primarily about the tightness of k + 1 colors 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 Theorem 3, which use k + 1 colors, 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 only two colors! Theorem 5 (Two Colors Suffice for Identifying Regular Languages) Let C = {L1 , L2 , . . . } be a countable collection of regular languages, where every Li is infinite. Then, C is identifiable in the limit with color traces given by trace coloring functions {cL }L∈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. 5
C HARIKAR K LEINBERG PABBARAJU
Finally, we also study identification in the limit with traces that are potentially corrupted (Section 3.1); in this setting, we derive a robust version 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 Theorem 3, we would require access to the coloring functions cL for every language L in the collection, and the ability to determine membership of any string x in any language L in the collection. 1.2. Related 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) 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 machine M and input x, they consider x augmented by a computational trace given by the sequence of computational steps of M on x. In the case of a DFA D, the computational trace is simply the sequence of states visited by D while processing input x. In the case of a Turing machine M , the computational trace is the sequence of ‘states’ of the Turing machine while processing x, 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 machine M , augmented by their computational traces, they show that one can converge to the correct representation of M , and hence identify the language accepted by M . We note that this notion of computational traces requires very detailed, fine-grained information to facilitate language identification. The computational trace for input x can be significantly longer than x. 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) 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 + 1 bits for alphabet size k. 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 size k, each prefix of the input string is annotated with a symbol from an alphabet size of 2k+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.
2. Background and Motivating Examples Language identification with a color trace can be related to language identification with a list (Charikar, Pabbaraju, and Tewari, 2025), where the algorithm guesses a list of k languages 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, Theorem 2) shows that a language collection C is 6
L ANGUAGE I DENTIFICATION WITH S UCCINCT M ACHINE -I NDEPENDENT T RACES
identifiable in the limit with a list of size k if and only if it can be expressed as a union of k collections, each of which is identifiable in the limit with a single guess. By this characterization, any collection C that is k-list identifiable decomposes as C = ∪ki=1 Ci , where each Ci is identifiable. In this case, we can assign a constant color trace corresponding to a unique color i to every language in Ci . Then, the color traces seen along with the input reveal the specific Ci that the target language K belongs to. Once this is known, one can simply apply any known algorithm that identifies in the limit to the collection Ci ; since Ci is identifiable in the limit, the algorithm will correctly identify the target language. Thus, k-list identifiability always implies identifiability with k colors. 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 Σ. For any finite F ⊆ Σ∗ , let LF = Σ∗ \ F . Now, consider the collection C = {LF : F is a finite subset of Σ∗ }. This collection is not identifiable with a list of any finite size (see Remark 3 in Charikar et al. (2025)). However, there is a simple trace coloring scheme with just two colors that makes the collection identifiable: associate every L ∈ C with the trace coloring function cL (x) = 1[x ∈ L]. We call this the “acceptreject” coloring. Note then that cLF (x) = 0 only if x ∈ F . Thus, an algorithm may initialize F = ∅, and initialize its guess for the target language K to be L∅ . Whenever it sees an input string x whose color trace has 0 in it, it obtains the prefix w of x at which the color 0 was seen (i.e., cK (w) = 0). The algorithm then adds w to F , and updates its guess LF accordingly. If the target language K was L∅ , the algorithm will never see a 0 in any color trace, and its initial guess remains correct throughout. If the target language K was LF for some F ̸= ∅, then for every w ∈ F , the algorithm is guaranteed to see an input x that contains w as its prefix; at this point, the algorithm correctly infers w’s membership in F . Since F is finite, the algorithm identifies LF 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 every L ∈ C, if a string w was not in L, it could be extended by some suffix y such that wy ∈ L. Indeed, this “reject-extendability” property is sufficient for a collection to be identifiable in the limit with the accept-reject coloring. Proposition 6 (Reject-Extendability Sufficient for Accept-Reject Coloring) Let C be a countable language collection over the alphabet Σ, where every L ∈ C satisfies the property: for every w ∈ Σ∗ , if w ∈ / L, then there exists a suffix y ∈ Σ∗ such that wy ∈ L. Then, the collection C is identifiable in the limit with a color trace given by the accept-reject trace coloring. Proof Let K ∈ C = {L1 , L2 , . . . } be the target language. For every L ∈ C, consider the acceptreject coloring given by the trace function cL (x) = 1[x ∈ L]. Consider the algorithm, which at time step t, outputs the smallest index it such that the language Lit is consistent with all the information seen in the input so far. Namely, Lit satisfies that {x1 , . . . , xt } ⊆ Lit , and furthermore, tracecK (xb ) = tracecLi (xb ) for all 1 ≤ b ≤ t. Furthermore, for every j < it , either t {x1 , . . . , xt } ⊈ Lj , or tracecK (xb ) ̸= tracecLj (xb ) for some 1 ≤ b ≤ t. Now, let z be the smallest index in the collection for which Lz = K. We claim that the index it output by the algorithm converges to z. To see this, note that the index z is always a valid candidate for the algorithm to output, since every string in the input is from Lz = K, and furthermore, cLz and cK are identical. Now, consider any j < z for which Lj ⊉ Lz . For each such Lj , there exists some x ∈ Lz \ Lj which shows up in the input at some finite time. At this time, the language Lj becomes inconsistent. Since there are finitely many j < z, we have that beyond some finite time, every Lj satisfying j < z and Lj ⊉ Lz is rendered inconsistent by the algorithm. So, we restrict our attention 7
C HARIKAR K LEINBERG PABBARAJU
to languages Lj that satisfy j < z and Lj ⊋ Lz (note that Lj cannot equal Lz , by our choice of z). Fix any such Lj , and consider any w ∈ Lj \ Lz . By the assumed reject-extendability property, there exists some suffix y ∈ Σ∗ such that wy ∈ Lz ; furthermore, this string wy is guaranteed to show up in the input at some finite time. But now, notice that cK (w) = cLz (w) = 0, but cLj (w) = 1. Thus, tracecLj (wy) ̸= tracecK (wy), and hence, the algorithm will declare Lj to have an inconsistent color trace on wy. In this manner, every proper superset of Lz occurring before it gets invalidated at some finite time, and we conclude that the algorithm’s guess eventually converges to z.
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 1 (Accept-Reject Coloring Doesn’t Always Work) Consider a collection C over the binary alphabet Σ = {0, 1}, which comprises of the regular language L∞ = {0, 1}∗ , together with the regular languages Li = {0, 1}∗ \ 1i {0, 1}∗ for i ≥ 1. Namely, Li excludes strings in {0, 1}∗ that start with i ones. We have that for every i ≥ 1, Li ⊊ Li+1 , Li ⊊ L∞ , and furthermore, ∪i Li = L∞ . Observe that for any i ∈ N ∪ {∞} and x ∈ Li , the accept-reject coloring satisfies tracecLi (x) = (1, 1, 1, . . . , 1). This is because each Li is prefix-closed: every prefix of x ∈ Li is | {z } |x|+1 times
also contained in Li . To see this, note that any x ∈ Li does not start with 1i , and hence no prefix of x starts with 1i as well. In particular, no string ever has 0 in its color trace. Furthermore, for any i > j, tracecLi (x) = tracecLj (x) for every x ∈ Li . Now, fix any identification algorithm, and consider an adversary that starts enumerating the strings in L1 in the order that they appear in a fixed background ordering of L∞ , together with their color traces (according to cL1 , which is always the constant-ones trace). Then, at some finite time, the algorithm must guess L1 to be the target language. At this time, the adversary switches to enumerating the strings in L2 , also in the fixed background ordering of L∞ , and starting from the leftmost string in L2 that has not been enumerated as yet. The adversary continues giving color traces according to L2 , which they can legally do, since L1 ⊊ L2 , and the traces of L2 and L1 matched on all strings in L1 . Now, the algorithm must guess the target language to be L2 at some subsequent finite time, at which time the adversary switches to L3 . The adversary repeats this switching process endlessly, enumerating each Li for a finite phase. As the adversary begins enumerating Li from the leftmost string that has not yet been enumerated in the fixed background ordering of L∞ , the adversary eventually enumerates every string in L∞ , together also with its correct color trace according to cL∞ . But the algorithm guesses an incorrect language infinitely often, and hence does not identify L∞ in the limit.
The structure that enabled the adversarial strategy in Example 1 distills precisely into the characterizing condition of Theorem 1. 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 Proposition 6 to account for trace discrepancies, and tell-tales associated with languages. 8
L ANGUAGE I DENTIFICATION WITH S UCCINCT M ACHINE -I NDEPENDENT T RACES
3. The 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. Lemma 2 (Coloring Lemma) Let C be a language collection over a finite alphabet Σ of size k. There exist trace coloring functions {cL }L∈C mapping to a palette P of size k + 1, that satisfy the following “distinguishable coloring condition”: for every L, L′ ∈ C that satisfy L ⊊ L′ , there exists x ∈ L for which tracecL (x) ̸= tracecL′ (x). Proof For any language L, define the set Pref(L) to be the set of all strings in Σ∗ that can be extended to form a string contained in L. Namely, Pref(L) := {x ∈ Σ∗ : ∃t ∈ Σ∗ such that xt ∈ L}.
(3)
Now, for any L ∈ C, define IsAcceptL : Σ∗ → {0, 1} and NextLiveL : Σ∗ → {0, 1, . . . , k} as: IsAcceptL (x) := 1[x ∈ L],
(4)
NextLiveL (x) := |{a ∈ Σ : xa ∈ Pref(L)}|.
(5)
In words, IsAcceptL (x) is the indicator for x being in L, whereas NextLiveL (x) counts the number of letters a ∈ Σ such that xa can be further extended to form a string contained in L. Now fix the palette P = {1, 2, . . . , k + 1}, and define the trace coloring function cL : Σ∗ → P as follows: ( IsAcceptL (x) + NextLiveL (x) cL (x) = 1
if x ∈ Pref(L), otherwise.
(6)
If x ∈ / Pref(L), cL (x) = 1; otherwise, if x ∈ Pref(L), then either IsAcceptL (x) = 1, or NextLiveL (x) > 0; hence cL (x) ≥ 1. Therefore, cL (x) ∈ {1, 2, . . . , k + 1} for all x ∈ Σ∗ . We now observe that the functions cL satisfy monotonicity on any string x with respect to inclusion. Observation 7 (Monotonicity of Trace Coloring) For any x ∈ Σ∗ , and L ⊆ L′ , it holds that (1) IsAcceptL (x) ≤ IsAcceptL′ (x),
(2) NextLiveL (x) ≤ NextLiveL′ (x),
(3) cL (x) ≤ cL′ (x).
Now, fix any L, L′ ∈ C for which L ⊊ L′ , and fix any z ∈ L′ \ L. Case 1: z ∈ Pref(L). In this case, let t ∈ Σ∗ be such that zt ∈ L (note that t ̸= ε, since z ∈ / L). We claim that x := zt satisfies tracecL (x) ̸= tracecL′ (x). To see this, note that IsAcceptL (z) = 0, but IsAcceptL′ (z) = 1; together with Observation 7, this implies that cL (z) < cL′ (z). Case 2: z ∈ / Pref(L). In this case, let w ∈ Σ∗ be the maximal prefix of z that satisfies w ∈ Pref(L), and let z = wat, where a ∈ Σ, and t ∈ Σ∗ . Here, by maximal, we mean that wa ∈ / Pref(L). Note that w can be ε, but its existence is guaranteed since L is non-empty. Now, since w ∈ Pref(L), there exists y ∈ Σ∗ such that wy ∈ L. We claim that x := wy satisfies that tracecL (x) ̸= tracecL′ (x). To see this, observe that wa ∈ / Pref(L), since w was chosen to be the maximal prefix of z satisfying w ∈ Pref(L). However, wa ∈ Pref(L′ ), since z = wat ∈ L′ \L. Thus, NextLiveL (w) < NextLiveL′ (w). By Observation 7, this implies that cL (w) < cL′ (w). In both cases, we have shown the existence of an x ∈ L satisfying tracecL (x) ̸= tracecL′ (x). The next claim shows that at least for k = 2, the bound achieved by our construction is tight. 9
C HARIKAR K LEINBERG PABBARAJU
Proposition 8 (Coloring Lemma Tight for k = 2) There exists a finite collection C of non-empty languages over the binary alphabet Σ = {0, 1}, such that any family of trace coloring functions {cL }L∈C that satisfies the distinguishable coloring condition must necessarily use 3 colors. Proof Consider the finite collection C = {L1 , L2 , L3 , L4 , L5 }, where L1 = {ε},
L2 = {ε, 0},
L3 = {ε, 1},
L4 = {ε, 0, 1},
L5 = {ε, 0, 1, 01}.
Fix any trace coloring functions cL1 , cL2 , cL3 , cL4 , cL5 that map to the palette {red, blue}, and satisfy the distinguishable coloring condition. Since L1 only contains ε, it must hold that cL1 (ε) ̸= cL2 (ε) = cL3 (ε) = cL4 (ε) = cL5 (ε). Without loss of generality, let cL1 (ε) = red, so that cL2 (ε) = cL3 (ε) = cL4 (ε) = cL5 (ε) = blue. Then, for L2 , it must hold that cL2 (0) ̸= cL4 (0) = cL5 (0). Similarly, for L3 , it must be the case that cL3 (1) ̸= cL4 (1) = cL5 (1). Without loss of generality, suppose cL2 (0) = red and cL3 (1) = red, so that cL4 (0) = cL5 (0) = blue, and cL4 (1) = cL5 (1) = blue. But now, consider the traces of L4 . By the previous assignments, we have that tracecL4 (ε) = (cL4 (ε)) = (blue),
tracecL5 (ε) = (cL5 (ε)) = (blue),
tracecL4 (0) = (cL4 (ε), cL4 (0)) = (blue, blue),
tracecL5 (0) = (cL5 (ε), cL5 (0)) = (blue, blue),
tracecL4 (1) = (cL4 (ε), cL4 (1)) = (blue, blue),
tracecL5 (1) = (cL5 (ε), cL5 (1)) = (blue, blue).
So, even though L4 ⊊ L5 , every x ∈ L4 satisfies tracecL4 (x) = tracecL5 (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). 3.1. Extension to Corrupted Traces We also obtain the guarantee of Lemma 2 in the setting where the color traces seen may be corrupted. Formally, we consider a notion of corrupted traces similar to Peng et al. (2026), where the ] cK (x), a corrupted version of tracecK (x). We restrict trace seen along with an input string x is trace ] cK (x)| = |tracecK (x)| the nature of allowed corruptions as follows. For any x, we require |trace (i.e., the corrupted trace must have the same length as the uncorrupted trace), and that every element ] cK (x) belongs to the same palette P used by cK (i.e., the corrupted trace cannot introduce in trace colors outside the palette). With these restrictions, we consider traces containing a bounded number of corruptions, as measured by the Hamming distance between the corrupted and uncorrupted ] cK (x) = (b1 , b2 , . . . , bn ), we restrict traces. Namely, if tracecK (x) = (a1 , a2 , . . . , an ) and trace d(a, b) = |{i : ai ̸= bi , 1 ≤ i ≤ n}| ≤ ℓ, where ℓ > 0 is an a priori known corruption budget. In this setting, we wish to correctly identify the target language K in the limit for any target lan] cK (x1 )), (x2 , trace ] cK (x2 )), . . . of K with corrupted guage K, and for any enumeration (x1 , trace traces satisfying a corrupted budget ℓ. From the proof of Theorem 1, it is straightforward to verify that a sufficient condition for identifiability of a collection C in this setting is the following: for every L ∈ C, there exists a finite tell-tale TL ⊆ L, such that for every L′ ∈ C satisfying L′ ⊊L, either (1) L′ does not contain TL , or (2) there exists x ∈ L′ such that d tracecL′ (x), tracecL (x) > 2ℓ. 10
L ANGUAGE I DENTIFICATION WITH S UCCINCT M ACHINE -I NDEPENDENT T RACES
Then, just like Lemma 2, we seek trace coloring functions that always satisfy (2) above. This will guarantee identifiability with corrupted traces having at most ℓ corruptions. Indeed, the next lemma constructs trace coloring functions that always satisfy (2) with a palette of size O(k 2ℓ+1 ). Lemma 9 (Robust Coloring Lemma) Let C be a language collection comprising of non-empty languages over a finite alphabet Σ of size k, and fix ℓ > 0. There exist trace coloring functions {cL }L∈C mapping to a palette P of size max(8ℓ + 4, 8k 2ℓ+1 ), such that for any L, L′ ∈ C that satisfy L ⊊ L′ , and L contains some string x having length at least 2ℓ, there exists x ∈ L for which d tracecL (x), tracecL′ (x) > 2ℓ. The proof of this lemma is given in Section A.2. The high-level idea is to propagate the discrepancy at a single location implied by the construction in Lemma 2 to all the 2ℓ locations preceding it.
4. Traces for Regular Languages The trace coloring functions that we constructed in Section 3 satisfy a special property for regular languages. Consider any regular language L, and let M be any Deterministic Finite-State Automaton (DFA)3 that recognizes L. Let Q(M ) be its set of states, δM be the associated state transition function, q0 (M ) be its initial state and F (M ) ⊆ Q(M ) its accepting states. For any state q in Q(M ), let Wq be the set of all the strings that arrive at state q, starting from the initial state. Recall the definition of our trace coloring function cL from (6). We claim that for any state q, for any w, w′ ∈ Wq , cL (w) = cL (w′ ). To see this, note that since w and w′ both end up at the state q, for any suffix y, wy and w′ y also end up in the same state in Q(M ). This implies that w ∈ Pref(L) ⇐⇒ w′ ∈ Pref(L), and also that IsAcceptL (w) = IsAcceptL (w′ ), NextLiveL (w) = NextLiveL (w′ ). We conclude that cL (w) = cL (w′ ). We now restate and prove Lemma 4, which constructs state coloring functions using k +1 colors so as to satisfy the distinguishable coloring condition, and also show that this palette size is optimal. Lemma 4 (State Coloring Lemma) Let C be an automata collection over an alphabet of size k. There exist state coloring functions {cM }M ∈C mapping to a palette P of size k + 1, such that for any M, M ′ ∈ C that satisfy L(M ) ⊊ L(M ′ ), there exists x ∈ L(M ) for which tracecM (x) ̸= tracecM ′ (x). Moreover, for any k, there exists a collection of automata over an alphabet of size k such that any set of state coloring functions requires k + 1 colors to satisfy this condition. Proof For any state q ∈ Q(M ), we say that q is a live state if there exists a suffix y ∈ Σ∗ such that δM (q, y) ∈ F (M ); otherwise, we call q a dead state. Now, similar to the definitions in (4) and (5), define IsAcceptM : Q(M ) → {0, 1} and NextLiveM : Q(M ) → {0, 1, . . . , k} as: IsAcceptM (q) := 1[q ∈ F (M )],
NextLiveM (q) := |{a ∈ Σ : δM (q, a) is live}|.
Then, define the state coloring function cM : Q(M ) → P as follows: ( IsAcceptM (q) + NextLiveM (q) if q is live, cM (q) = 1 otherwise. 3. We give a formal definition of a DFA in Appendix B.
11
(7)
C HARIKAR K LEINBERG PABBARAJU
We can then verify that for any x = x0 x1 . . . xn ∈ L(M ) (where x0 = ε) that traverses the states q0 , q1 , . . . , qn in M , and for any qi , it holds that cM (qi ) = cL(M ) (x0 x1 . . . xi ), where cL(M ) is exactly the trace coloring function defined in (6) in the proof of Lemma 2. The conclusion of that lemma implies that {cM }M ∈C satisfy the required distinguishable coloring condition. We now show that k + 1 colors are optimal. Fix k ≥ 1, and consider C = {M0 , M1 , . . . , Mk }. Each Mi has just two states q0 (Mi ) and q1 (Mi ), where q0 (Mi ) is the initial state, and also the only accepting state, and q1 (Mi ) is a rejecting sink state. Namely, ∀i∀a : δMi (q1 (Mi ), a) = q1 (Mi ). Now, in M0 , we further set δM0 (q0 (M0 ), a) = q1 (M0 ) for every a ∈ Σ. So, it holds that L(M0 ) = {ε}. Next, for i ∈ {1, . . . , k}, we set ( q0 (Mi ) if a ∈ {1, . . . , i}, δMi (q0 (Mi ), a) = q1 (Mi ) otherwise. Thus, L(Mi ) = {1, . . . , i}∗ . Observe that L(M0 ) ⊊ L(M1 ) ⊊ · · · ⊊ L(Mk ). Now, fix any state coloring functions cM0 , cM1 , . . . , cMk that use a palette of size k, and assume that they satisfy: for every Mi , Mj ∈ C with L(Mi ) ⊊ L(Mj ), there exists x ∈ L(Mi ) for which tracecMi (x) ̸= tracecMj (x). Fix any i, j ∈ {0, 1, . . . , k} satisfying i < j. Observe that any x ∈ L(Mi ) simply loops on the state q0 (Mi ), giving tracecMi (x) = (cMi (q0 (Mi )), . . . , cMi (q0 (Mi ))). | {z } |x|+1 times
Thus, for the assumed guarantee to hold, it must be the case that for every i < j, cMi (q0 (Mi )) ̸= cMj (q0 (Mj )). But this is not possible if the state coloring functions use only k colors. In Section B.1, we extend the construction of the state coloring functions above to the setting with corrupted traces, similar to Section 3.1. Here, we show that a palette of size O(k 2ℓ+1 ) suffices to achieve a similar guarantee as Lemma 9, and that k 2ℓ−1 colors are necessary in general. Finally, we restate and prove Theorem 5. Theorem 5 (Two Colors Suffice for Identifying Regular Languages) Let C = {L1 , L2 , . . . } be a countable collection of regular languages, where every Li is infinite. Then, C is identifiable in the limit with color traces given by trace coloring functions {cL }L∈C that use just two colors. Before stating the formal proof, we give some intuition, specifically since the requirement that every Li 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 automata M1 , M2 , . . . that accept L1 , L2 , . . . , 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 Lemma 4, 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 recognize Li , we want to choose Mi with a view to satisfying the following property: for each previous automaton Mj where j < i and Lj is a superset of Li , we can designate a particular state in Mi with a particular color, which helps distinguish it from Mj . In order to choose such a designated state for every j < i, we need enough states (at least i − 1) in Li to begin with. A sufficient condition to ensure this is that every Li 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 12
L ANGUAGE I DENTIFICATION WITH S UCCINCT M ACHINE -I NDEPENDENT T RACES
traces of every language Li from the color traces of every superset of Li that appears before Li . Note that this is a weaker property than the distinguishable coloring condition (which requires such a property for all supersets in the collection, not just the ones appearing before), but is sufficient for identification in the limit (see Remark 10). We now give the formal proof. Proof Fix M1 , M2 , . . . to be any arbitrary DFAs that recognize L1 , L2 , . . . . Now recall the definition of a live state in a DFA: a state q ∈ Q(M ) is live if ∃ a suffix y ∈ Σ∗ such that δM (q, y) ∈ F (M ). Now call a state q reachable if ∃w ∈ Σ∗ such that δM (q0 (M ), w) = q. By Lemma 14 proved in Appendix B, we can assume that every Mi has at least i − 1 live and reachable states. We will now inductively determine a binary state coloring function cMi for every i ≥ 1. To begin with, fix cM1 arbitrarily. Now, for any i > 1, let us assume that cM1 , . . . , cMi−1 have been determined. Consider Mi : there are at least i − 1 live and reachable states in Mi . Pick any i − 1 of these, and denote the set as {qb }b=1,...,i−1 . Associate each qb with a prefix wb ∈ Σ∗ and a suffix yb ∈ Σ∗ , such that δMi (q0 (Mi ), wb ) = qb , and δMi (qb , yb ) ∈ F (Mi ), so that xb = wb yb ∈ Li . Now, consider the set {j < i : Lj ⊋ Li }: this set has size at most i − 1. Thus, we can map every j in this set to a distinct live qb in Mi . Consider traversing the prefix wb associated with qb in Mj , and let qb′ = δMj (q0 (Mj ), wb ). We will set cMi (qb ) = 1 − cMj (qb′ ). After doing this for every j, we assign cMi (q) for the remaining states in Mi arbitrarily. This completes the specification of cMi (q). Now consider any i ≥ 1. We claim that: (⋆) for every j < i, if Lj ⊋ Li , then there exists x in Li for which tracecMi (x) ̸= tracecMj (x). Indeed, fix any such Lj , and let qb be the distinct live state in Mi that we had associated Lj with in the inductive construction of cMi above. Now consider the string xb = wb yb ∈ Li associated with the state qb in Mi . Note that the prefix wb reaches the state qb′ = δMj (q0 (Mj ), wb ) in Mj , whereas it reaches the state qb in Mi ; our construction above guarantees that cMi (qb ) = 1 − cMj (qb′ ). Thus, tracecMi (xb ) ̸= tracecMj (xb ), as claimed. Finally, by Remark 10 in the proof of Theorem 1, the property (⋆) is sufficient for the algorithm considered in that proof to identify the collection in the limit with traces.
5. Conclusion 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 size k. Do constantly many colors always suffice for any arbitrary collection? Or must the number of colors grow linearly with k? 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 Theorem 5, 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 of arbitrary languages that are all infinite. In fact, while trace coloring 13
C HARIKAR K LEINBERG PABBARAJU
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 are collectiondependent (as are the trace coloring functions from Theorem 5). Note, in contrast, that our generalpurpose trace-coloring functions from Theorem 3 which use k+1 colors, are collection-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 Theorem 3 of the present paper: the new result is quantitatively stronger (using 2 colors instead of k + 1), but it markedly lacks the constructive, natural formulation of Theorem 3. 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).
Acknowledgments 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 Dana Angluin. Inductive inference of formal languages from positive data. Information and control, 45(2):117–135, 1980. 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. URL https://openreview.net/forum?id=L8SMNWsxfK. Moses Charikar, Chirag Pabbaraju, and Ambuj Tewari. A characterization of list language identification in the limit. arXiv preprint arXiv:2511.04103, 2025. Moses Charikar, Jon Kleinberg, and Chirag Pabbaraju. Globally consistent coloring schemes for language identification. arXiv preprint arXiv:2607.11606, 2026. E Mark Gold. Language identification in the limit. Information and control, 10(5):447–474, 1967. John E Hopcroft, Rajeev Motwani, and Jeffrey D Ullman. Introduction to automata theory, languages, and computation. Acm Sigact News, 32(1):60–65, 2001. 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. URL https://proceedings.mlr.press/v291/papazov25a.html. 14
L ANGUAGE I DENTIFICATION WITH S UCCINCT M ACHINE -I NDEPENDENT T RACES
Binghui Peng, Amin Saberi, and Grigoris Velegkas. Language identification in the limit with computational trace. In The Fourteenth International Conference on Learning Representations, 2026. URL https://openreview.net/forum?id=1OAGf7ntSE. Michael Sipser. Introduction to the Theory of Computation. International Thomson Publishing, 1st edition, 1996. ISBN 053494728X. 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. URL http://papers.nips.cc/paper_files/paper/2022/ hash/9d5609613524ecf4f15af0f7b31abca4-Abstract-Conference.html.
Appendix A. Omitted Proofs from Section 3 A.1. Characterization of Identification in the Limit with Color Traces Theorem 1 (Characterization of Identification in the Limit with Color Traces) Let C be a countable language collection. Then, C is identifiable in the limit with a color trace given by the trace coloring functions {cL }L∈C if and only if for every language L ∈ C, there exists a finite “tell-tale” subset TL ⊆ L, such that for every language L′ ∈ C that is a proper subset of L, either (1) L′ does not contain TL , or (2) there exists x ∈ L′ such that tracecL′ (x) ̸= tracecL (x). Proof If direction. Suppose that the stated condition holds for the collection C = {L1 , L2 , . . . } and the associated trace coloring functions {cL }L∈C . Furthermore, let TL be the finite tell-tale subset associated with language L in the collection. Denote the unknown target language by K, and consider the following identification algorithm: at time step t, upon seeing (x1 , tracecK (x1 )), . . . , (xt , tracecK (xt )), the algorithm outputs the smallest index it , which satisfies: (1) {x1 , . . . , xt } ⊆ Lit , (2) TLit ⊆ {x1 , . . . , xt }, and (3) tracecLi (xj ) = tracecK (xj ) for every 1 ≤ j ≤ t. We remark that without t the check in (3), the algorithm would be identical to Angluin’s algorithm for identification in the limit (Angluin, 1980). Let z be any index in the collection for which Lz = K, and tracecLz (x) = tracecK (x) for every x ∈ K. Note that such an index exists since K ∈ C. Note also that requirements (1) and (3) hold for index z at all time steps. Furthermore, since TLz is a finite subset of K, and the input eventually enumerates every string in K, there exists a finite time at which requirement (2) gets satisfied as well. Thus, beyond this time, z is a valid candidate index for the algorithm to output. We proceed assuming that we are beyond this time. Now, consider any j < z for which Lj ⊉ Lz . For each such Lj , there exists some x ∈ Lz \ Lj which is guaranteed to show up in the input at some finite time. At this time and beyond, index j violates (1). Since there are only finitely many j < z, we have that beyond some finite time, every j satisfying j < z and Lj ⊉ Lz violates (1). So, we assume being beyond this time as well, and next restrict our attention to indices j that satisfy j < z and Lj ⊋ Lz . Suppose in one case that 15
C HARIKAR K LEINBERG PABBARAJU
TLj ⊆ Lz holds. Then, at some finite time, all of TLj will show up in the input, and hence (2) will always be satisfied beyond this time by index j. But now observe that we are in a position where Lz and Lj satisfy: Lz ⊊ Lj and TLj ⊆ Lz . By the condition in the theorem, it must then hold that there exists x ∈ Lz for which tracecLz (x) = tracecK (x) ̸= tracecLj (x). Such an x is guaranteed to show up in the input at some finite time, together with tracecK (x); at this time and beyond, index j violates (3). In the other case, suppose that TLj ⊈ Lz . In this case, at least one element in TLj will never show up in the input, and hence (2) will never be satisfied by index j. In all cases, we have shown that there exists a finite time beyond which index j stops being a candidate for the algorithm. Since there are only finitely many j < z, we conclude that the algorithm eventually always outputs some j ≤ z for which Lj = Lz = K. Remark 10 (Weaker Condition Sufficient) We remark that the analysis of the algorithm requires only the following weaker condition on the the countable collection C = {L1 , L2 , . . . } and trace coloring functions {cLj }j∈N : for every language Lj ∈ C, there exists a finite tell-tale subset TLj ⊆ Lj such that for every language Li ∈ C that is a proper subset of Lj and i > j, either (1) Li does not contain TLj , or (2) there exists x ∈ Li such that tracecLi (x) ̸= tracecLj (x). Only if direction. Fix a set of trace coloring functions {cL }L∈C , and suppose that there exists a language L ∈ C such that for every finite T ⊆ L, there exists a language L′ ∈ C that is a proper subset of L, such that L′ contains T and also tracecL′ (x) = tracecL (x) for every x ∈ L′ . 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 in L, together with their color traces according to cL , in the order that they appear in a fixed background ordering of L. Then, at some finite time, the algorithm must guess an index i such that Li = L. Suppose that the input strings enumerated so far by the adversary comprise of the set T . Then, by assumption, there exists a language L′ ∈ C that is a proper subset of L, such that L′ contains T , and furthermore, tracecL′ (x) = tracecL (x) for every x ∈ L′ (including T ). Thus, the adversary switches to enumerating strings in L′ with their color traces (which they can legally do, since T ⊆ L′ , and the traces of L′ and L match on all strings in L′ ). Now, the algorithm must guess an index i satisfying Li = L′ at some subsequent finite time. At this time, the adversary switches back to enumerating L (they can do this since traces of L′ and L match at all strings in L′ ), starting from the leftmost string that has not yet been enumerated in the fixed background ordering of L. Again, at some subsequent finite time, the algorithm must guess an index i such that Li = L. Suppose that the input strings enumerated so far by the adversary comprise of the set T ′ . Then, by assumption again, there exists a language L′′ ∈ C that is a proper subset of L, such that L′′ contains T ′ , and furthermore, tracecL′′ (x) = tracecL (x) for every x ∈ L′′ (including T ′ ). Thus, the adversary switches to enumerating strings in L′′ . The adversary thus continues switching back and forth between L and some other language L̃ ⊊ L endlessly. Since at each switch back to L, the adversary begins with the leftmost string in L that has not yet been enumerated in its fixed background ordering, the adversary eventually enumerates every string in L along with its trace according to cL . But also, each switch back to L follows a time step at which the algorithm guesses an index i for which Li = L̃ ⊊ L, and hence the algorithm guesses an incorrect index infinitely often. Thus, the algorithm does not identify L in the limit.
16
L ANGUAGE I DENTIFICATION WITH S UCCINCT M ACHINE -I NDEPENDENT T RACES
A.2. Robust Coloring Lemma Lemma 9 (Robust Coloring Lemma) Let C be a language collection comprising of non-empty languages over a finite alphabet Σ of size k, and fix ℓ > 0. There exist trace coloring functions {cL }L∈C mapping to a palette P of size max(8ℓ + 4, 8k 2ℓ+1 ), such that for any L, L′ ∈ C that satisfy L ⊊ L′ , and L contains some string x having length at least 2ℓ, there exists x ∈ L for which d tracecL (x), tracecL′ (x) > 2ℓ. Proof For any language L ∈ C, we extend the definitions of IsAcceptL and NextLiveL from the proof of Lemma 2, and also consider some global quantities for the language. Namely, consider the functions IsAcceptL and NextLiveL that map Σ∗ to a non-negative integer, and the quantities ShortAcceptL and ShortPrefixL , defined as follows: IsAcceptL (x) := |{y ∈ Σ{0,...,2ℓ} : xy ∈ L}|,
(8)
NextLiveL (x) := |{y ∈ Σ{1,...,2ℓ+1} : xy ∈ Pref(L)}|,
(9)
ShortAcceptL := |{y ∈ Σ ShortPrefixL := |{y ∈ Σ
{0,...,2ℓ−1}
{0,...,2ℓ}
: y ∈ L}|,
(10)
: y ∈ Pref(L)}|.
(11)
Here, Σ{i,i+1,...,j } denotes the set {y ∈ Σ∗ : i ≤ |y| ≤ j}, with |y| = 0 implying the empty string y = ε. In words, IsAcceptL (x) counts the number of suffixes y having length |y| ∈ {0, 1, . . . , 2ℓ} for which xy is in L, NextLiveL (x) counts the number of suffixes y having length |y| ∈ {1, . . . , 2ℓ+1} such that xy can be extended further to form a string in L, ShortAcceptL counts the number of strings y having length |y| ∈ {0, . . . , 2ℓ − 1} such that y belongs to L, and ShortPrefixL counts the number of prefixes y having length |y| ∈ {0, . . . , 2ℓ} such that y can be extended further to form a string in L. Note that ShortAcceptL and ShortPrefixL are global properties of the language L. Furthermore, for any x, 0 ≤ IsAcceptL (x), NextLiveL (x), ShortAcceptL , ShortPrefixL ≤
2ℓ+1 X
k i ≤ max(2ℓ + 1, 2k 2ℓ+1 ).
i=1
(12) Now fix the palette P = {1, 2, . . . , B}, where B = max(8ℓ + 4, 8k 2ℓ+1 ), and define the trace coloring function cL : Σ∗ → P as follows: ( IsAcceptL (x) + NextLiveL (x) + ShortAcceptL + ShortPrefixL cL (x) = 1
if x ∈ Pref(L), otherwise. (13)
If x ∈ / Pref(L), cL (x) = 1; otherwise, if x ∈ Pref(L), then either IsAcceptL (x) > 0, or NextLiveL (x) > 0, and hence cL (x) ≥ 1. Together with (12), this implies that cL (x) ∈ P for all x ∈ Σ∗ . Similar to the proof of Lemma 2, we now observe that the quantities defined above satisfy monotonicity on any string x with respect to inclusion. 17
C HARIKAR K LEINBERG PABBARAJU
Observation 11 (Monotonicity of Trace Coloring) Let L, L′ be languages satisfying L ⊆ L′ . Then, for any x ∈ Σ∗ , it holds that: (1) IsAcceptL (x) ≤ IsAcceptL′ (x),
(2) NextLiveL (x) ≤ NextLiveL′ (x),
(3) ShortAcceptL ≤ ShortAcceptL′ ,
(4) ShortPrefixL ≤ ShortPrefixL′ ,
(5) cL (x) ≤ cL′ (x).
Now, fix any L, L′ ∈ C for which L ⊊ L′ , and L contains some string x having length at least 2ℓ. Case 1: ShortAcceptL < ShortAcceptL′ or ShortPrefixL < ShortPrefixL′ . In this case, using Observation 11, note that cL (x) < cL′ (x) for every x ∈ L. Then, choose any x ∈ L having length at least 2ℓ, which is guaranteed to exist by assumption. We have that each of cL (ε), cL (x≤1 ), . . . , cL (x) is strictly smaller than cL′ (ε), cL′ (x≤1 ), . . . , cL′ (x) respectively, and hence, d tracecL (x), tracecL′ (x) > 2ℓ as required. Case 2: ShortAcceptL = ShortAcceptL′ and ShortPrefixL = ShortPrefixL′ . Since L ⊊ L′ , y ∈ L =⇒ y ∈ L′ , and y ∈ Pref(L) =⇒ y ∈ Pref(L′ ). Therefore, this case implies the stronger properties that {y ∈ Σ{0,...,2ℓ−1} : y ∈ L} = {y ∈ Σ{0,...,2ℓ−1} : y ∈ L′ }, {y ∈ Σ
{0,...,2ℓ}
{0,...,2ℓ}
: y ∈ Pref(L)} = {y ∈ Σ
(14) ′
: y ∈ Pref(L )}.
(15)
Now, fix any z ∈ L′ \ L. Note that by (14), it must be the case that |z| ≥ 2ℓ. We then have the following two subcases: Subcase 2a: z ∈ Pref(L). In this case, let t ∈ Σ∗ be such that zt ∈ L (note that t ̸= ε, since z∈ / L). We claim that x := zt satisfies that d tracecL (x), tracecL′ (x) > 2ℓ. To see this, let z = z0 z1 , . . . , zn , where z0 = ε and n ≥ 2ℓ. For any p ≤ q, denote zp:q := zp zp+1 . . . , zq . We then observe that for any i ∈ {0, 1, . . . , 2ℓ}, IsAcceptL (z0:n−i ) is strictly smaller than IsAcceptL′ (z0:n−i ); this is because there exists a suffix y = zn−i+1:n having length |y| ∈ {0, . . . , 2ℓ}, for which z0:n−i y ∈ / L but z0:n−i y ∈ L′ (note that z0:n−i y is simply equal to z). This implies that d tracecL (x), tracecL′ (x) > 2ℓ. Subcase 2b: z ∈ / Pref(L). In this case, let w ∈ Σ∗ be the maximal prefix of z that satisfies w ∈ Pref(L), and let z = wat, where a ∈ Σ, and t ∈ Σ∗ . Here, by maximal, we mean that wa ∈ / Pref(L). We first claim that |w| ≥ 2ℓ. To see this, suppose that |w| < 2ℓ. In this case, |wa| ≤ 2ℓ. But it also holds that wa ∈ / Pref(L), and wa ∈ Pref(L′ ) (since z = wat ∈ L′ ). This contradicts (15). Thus, |w| ≥ 2ℓ. So, let w = w0 w1 , . . . , wn , where w0 = ε. We now argue that for every i ∈ {0, 1, . . . , 2ℓ}, NextLiveL (w0:n−i ) is strictly smaller than NextLiveL′ (w0:n−i ). Again, this holds because there exists a suffix y = wn−i+1:n a having length |y| ∈ {1, . . . , 2ℓ + 1}, for which w0:n−i y ∈ / Pref(L) but w0:n−i y ∈ / Pref(L′ ) (note that w y is simply equal to wa). This then implies that 0:n−i d tracecL (x), tracecL′ (x) > 2ℓ. In both cases, we have shown the existence of an x ∈ L satisfying d tracecL (x), tracecL′ (x) > 2ℓ, as required.
18
L ANGUAGE I DENTIFICATION WITH S UCCINCT M ACHINE -I NDEPENDENT T RACES
Appendix B. Traces for Regular Languages We give a formal definition of a DFA following the textbooks Sipser (1996); Hopcroft et al. (2001): Definition 12 (Deterministic Finite-State Automaton (DFA) A DFA M over a finite alphabet Σ is a 5-tuple M = (Q(M ), Σ, δM , q0 (M ), F (M )), where Q(M ) is a finite set of states, δM : Q(M ) × Σ → Q(M ) is a state transition function, q0 (M ) ∈ Q(M ) is the initial state, and F (M ) ⊆ Q(M ) is the set of accepting states. The regular language L(M ) that is accepted by the DFA M is defined as the set L(M ) = {x ∈ Σ∗ : δM (q0 (M ), x) ∈ F (M )}. We can extend the domain of the transition function δM from Σ to Σ∗ by defining δM (q, ε) = q, and recursively defining δM (q, ay) = δM (δM (q, a), y), for every q ∈ Q(M ), a ∈ Σ and y ∈ Σ∗ . B.1. Corrupted State Traces As we did in Section 4, we describe how we can derive state coloring functions that are robust to corruptions in state traces from the trace coloring functions constructed in Lemma 9 above. Consider any DFA M in a given collection C = {M1 , M2 , . . . }, and fix ℓ > 0. For any q ∈ Q(M ), define IsAcceptM (q) := |{y ∈ Σ{0,...,2ℓ} : δM (q, y) ∈ F (M )}|,
(16)
NextLiveM (q) := |{y ∈ Σ{1,...,2ℓ+1} : δM (q, y) is live}|,
(17)
ShortAcceptM := |{y ∈ Σ ShortPrefixM := |{y ∈ Σ
{0,...,2ℓ−1}
{0,...,2ℓ}
: δM (q0 (M ), y) ∈ F (M )}|,
: δM (q0 (M ), y) is live}|.
(18) (19)
Note that ShortAcceptM and ShortPrefixM are global properties of the DFA M . Now fix the palette P = {1, 2, . . . , B}, where B = max(8ℓ + 4, 8k 2ℓ+1 ), and define the state coloring function cM : Q(M ) → P as follows: ( IsAcceptM (q) + NextLiveM (q) + ShortAcceptM + ShortPrefixM cM (q) = 1
if q is live, otherwise. (20)
For any x = x0 x1 . . . xn ∈ L(M ) (where x0 = ε), which traverses the states q0 , q1 , . . . , qn in M , we have that cM (qi ) = cL(M ) (x0 x1 . . . xi ), where cL(M ) is exactly the trace coloring function defined in (13) in the proof of Lemma 9. Thus, we have that for any M, M ′ ∈ C satisfying L(M ) ⊊ L(M ′ ), there exists an x ∈ L(M ) for which d tracecM (x), tracecM ′ (x) > 2ℓ, and we can identify C in the limit using state color traces having at most ℓ corruptions. Analogous to Lemma 4, we next show that the palette size used above is optimal in order for state coloring functions in general. 19
C HARIKAR K LEINBERG PABBARAJU
Claim 13 (k 2ℓ−1 Colors Necessary for Corrupted State Traces) For any k ≥ 1 and ℓ > 0, there exists a finite collection C of DFAs over the alphabet Σ = {1, 2, . . . , k}, such that any family of state coloring functions {cM }M ∈C which satisfies: for every pair of DFAs M, M ′ ∈ C satisfying that L(M ) ⊊ L(M ′ ), there exists x ∈ L(M ) for which d tracecM (x), tracecM ′ (x) > 2ℓ, necessarily requires a palette of size k 2ℓ−1 . Proof Let N = k 2ℓ−1 , and S = {s1 , . . . , sN } be an ordering of all strings of size 2ℓ − 1 in Σ2ℓ−1 . Consider the collection C = {M1 , . . . , MN }, where each Mi accepts the regular language L(Mi ) = {wy : w ∈ {s1 , . . . , si }, y ∈ Σ∗ }.
(21)
Namely, L(Mi ) has strings of the form wy, where w is any of the first i strings in S, and y is any suffix in Σ∗ . We have that L(M1 ) ⊊ L(M2 ) ⊊ · · · ⊊ L(MN ). Now observe that each Mi can be specified by a DFA that first builds a prefix tree over the set {s1 , . . . , si }, followed by an accepting sink state. Namely, for any x, the prefix tree part checks whether the first 2ℓ−1 characters of x belong to {s1 , . . . , si }—if they do, then the string is accepted. Let q0 (Mi ) be the initial state of Mi (i.e., the root of the prefix tree), and let qF (Mi ) be the single accepting sink state. Note then that any x ∈ L(Mi ) traverses a sequence of states of the form q0 (Mi ) → qj1 (Mi ) → · · · → qj2ℓ−1 (Mi ) → qF (Mi ) → · · · → qF (Mi ) . | {z } | {z }
(22)
loop on accepting sink state
prefix tree
Now, fix any state coloring functions cM1 , . . . , cMN that use a palette P of size N − 1, and satisfy that for every Mi , Mj with L(Mi ) ⊊ L(Mj ), there exists x ∈ L(Mi ) for which d tracecMi (x), tracecMj (x) > 2ℓ. Fix any i, j ∈ {1, . . . , N } satisfying i < j. For any x ∈ L(Mi ), by the characterization (22) of the sequence of states traversed by x in Mi , we get that tracecMi (x) is some sequence in P 2ℓ , followed by the sequence (cMi (qF (Mi )), . . . , cMi (qF (Mi ))). Similarly, we have that tracecMj (x) | {z } |x|−2ℓ+1 times 2ℓ is some sequence in P , followed by the sequence c
Mj (qF (Mj ), . . . , cMj (qF (Mj ))).
|
{z
|x|−2ℓ+1 times
Thus, in
}
order for d tracecMi (x), tracecMj (x) > 2ℓ to hold, we necessarily require that cMi (qF (Mi )) ̸= cMj (qF (Mj )). But this is not possible for every i < j, if the state coloring functions use only N − 1 colors.
B.2. Identifying Regular Languages with Two Colors Lemma 14 (Increasing Live, Reachable States in DFA) Let M be a DFA satisfying |L(M )| = ∞, and let M have n states that are live and reachable. Then, for any k > 0, there exists a DFA M ′ satisfying L(M ′ ) = L(M ), such that M ′ has n + k states that are live and reachable. Proof Since L(M ) is infinite, it must contain strings of arbitrarily large length. Let x = x1 x2 . . . xt be any string in L(M ) having length t ≥ n. Then, consider the sequence of states q0 , q1 , . . . , qt traversed by x in M : note that every state in this sequence is live and reachable. Then, since there 20
L ANGUAGE I DENTIFICATION WITH S UCCINCT M ACHINE -I NDEPENDENT T RACES
are only n live and reachable states in M , and the number of states in this sequence is t + 1 > n, by the pigeonhole principle, there exists at least one live and reachable state that appears twice in the sequence. Let s be the smallest index for which there exists i < s such that qi = qs (i.e., this is the first time a state got repeated in the sequence), and consider the intermediate sequence of transitions qi → qi+1 → · · · → qs−1 → qs , together with the symbols xi+1 , . . . , xs−1 , xs that effected these transitions. Note that by the choice of s, the states q0 , . . . , qs−1 are all distinct. Now, consider a DFA M ′ that operates on the same alphabet Σ. M ′ has a copy q ′ of every state ′ q in M , plus an additional state qnew . The state transitions for all the states in M ′ are identical to ′ ′ their copies in M , except for the states qs−1 and qnew , where qs−1 is the copy of the state qs−1 , ′ ′ and qnew is the additional new state. The state transitions for qs−1 and qnew are as follows. First, ′ ′ we make the transitions out of qnew to be identical to those out of qs , i.e., set δM ′ (qnew , a) to be xs ′ the copy of δM (qs , a) for every a ∈ Σ. Next, we redirect the single transition qs−1 −→ qs′ to be xs ′ ′ ′ qs−1 −→ qnew instead; namely, for any a ̸= xs , we set δM ′ (qs−1 , a) to be the copy of the state ′ ′ ′ δM (qs−1 , a), and we make qnew reachable by setting δM ′ (qs−1 , xs ) = qnew . In essence, we have ′ ′ ′ , whose redirected the transition from qs−1 which was looping back into qs to the new state qnew ′ outward transitions are then identical to qs . The initial state in M is set to the copy of the initial state in M , and the accepting states in M ′ are set to the copies of the accepting states in M , plus the ′ state qnew if qs was an accepting state. This completes the specification of M ′ . We now argue that M ′ has n + 1 live and reachable states, and that L(M ′ ) = L(M ); the lemma is then established by inducting this k times. First, it is clear that for any state q in M that was either not live or reachable in M , its copy q ′ has the same status in M ′ . Now, by construction, the ′ newly added state qnew and the state qs′ are both live and reachable, as witnessed by the traversal ′ ′ of x through M , which passes through both qs′ and qnew on the way to an accepting state. Finally, for every state q ̸= qs that was live and reachable in M , its copy q ′ remains live and reachable in M ′ . This can be seen by tracing out the sequence of states traversed by any y ∈ L(M ) that passed through q on the way to an accepting state in M . In its traversal through M ′ , the only notable change xs xs ′ ′ −→ qnew . But since the transitions is that a transition of the form qs−1 −→ qs gets replaced by qs−1 ′ out of qnew are identical to qs , y continues on its path to an accepting state, and any occurrences of q in the traversal through M overlap with occurrences of q ′ in the traversal through M ′ ; thus, q ′ remains live and reachable in M ′ . Thus, we have argued that M ′ has n + 1 live and reachable states. It remains to argue that L(M ′ ) = L(M ). Again, this is made clear by tracing out the traversal of xs ′ ′ −→ qnew , any x through M and M ′ : if the traversal never uses the single redirected transition qs−1 then the end outcomes are clearly identical; if it does use this transition, then in M , the transition ′ leads into the state qs , whereas in M ′ , the transition leads into the state qnew ; however, since the ′ transitions out of qnew and qs are identical, the end outcome is identical as well.
21