Résumé technique : Identification de langage avec des traces succinctes et indépendantes de la machine

1. Énoncé du problème

L'article traite du problème de l'identification de langage dans la limite, un cadre initialement proposé par Gold (1967). Dans ce cadre, un algorithme tente d'identifier un langage cible $K$ à partir d'une collection dénombrable de langages candidats $\mathcal{L} = \{L_1, L_2, \dots\}$ en observant une énumération de chaînes appartenant à $K$. Le théorème original de Gold a établi que pour la plupart des familles non triviales de langages, l'identification dans la limite est impossible sans informations supplémentaires.

Des travaux récents ont cherché à surmonter ces résultats négatifs en introduisant des traces computationnelles ou des annotations (par exemple, Papazov et Flammarion, 2025 ; Bhattamishra et al., 2026 ; Peng et al., 2026). Ces travaux postulent que si les données d'entraînement sont augmentées de traces générées par le modèle de machine sous-jacent (par exemple, les états d'un automate fini ou les configurations d'une machine de Turing), l'identification devient possible. Cependant, ces approches existantes souffrent de deux limitations :

1. Dépendance à la machine : Elles nécessitent la connaissance du modèle de machine spécifique générant le langage.
2. Taille de l'alphabet : Les traces nécessitent souvent de grands alphabets (par exemple, l'ensemble complet des états de la machine ou les ensembles de puissances des vocabulaires), ce qui est peu pratique pour les modèles à grande échelle.

Les auteurs se posent la question suivante : Peut-on obtenir des résultats positifs pour l'identification de langage en utilisant des traces qui sont (a) indépendantes de tout modèle de machine sous-jacent, et (b) définies sur un alphabet petit et succinct ?

2. Méthodologie et définitions

Le modèle de trace

Les auteurs définissent une fonction de coloration de trace $c$ sur un ensemble fini de couleurs (une « palette ») $P$. Pour une chaîne $x = x_1 x_2 \dots x_n$, la trace de couleur est définie comme la séquence de couleurs appliquées à chaque préfixe de la chaîne :
$$\text{trace}_c(x) := (c(\epsilon), c(x_{\le 1}), c(x_{\le 2}), \dots, c(x_{\le n}))$$
où $x_{\le i}$ est le préfixe de longueur $i$. Contrairement aux traces basées sur des machines, cette définition s'applique à n'importe quel langage sans supposer l'existence d'un automate générateur.

Condition d'identification

L'article établit une condition nécessaire et suffisante pour qu'une collection $\mathcal{C}$ soit identifiable dans la limite avec des traces de couleur (Théorème 1). Cette condition généralise les ensembles « tell-tale » d'Angluin : pour tout langage $L \in \mathcal{C}$, il doit exister un sous-ensemble fini $T_L \subseteq L$ tel que pour tout sous-ensemble propre $L' \subset L$, soit $L'$ ne contient pas $T_L$, soit il existe une chaîne $x \in L'$ où la trace de $x$ sous $L'$ diffère de la trace de $x$ sous $L$.

Pour simplifier la construction, les auteurs se concentrent sur une condition plus forte de « coloration distinguable » : pour tout $L, L' \in \mathcal{C}$ où $L \subsetneq L'$, il existe un $x \in L$ tel que $\text{trace}_{c_L}(x) \neq \text{trace}_{c_{L'}}(x)$. Si cette condition est remplie, les ensembles « tell-tale » ne sont pas nécessaires et l'identification est garantie.

3. Contributions clés et résultats

A. Collections de langages généraux (Théorème 3)

Le résultat principal démontre que pour n'importe quelle collection dénombrable de langages sur un alphabet fini $\Sigma$ de taille $k$, il existe des fonctions de coloration de trace utilisant une palette de taille $k+1$ qui satisfont la condition de coloration distinguable.

• Construction : La fonction de coloration $c_L(x)$ est définie sur la base de deux propriétés de la chaîne $x$ par rapport au langage $L$ :
  1. $IsAccept_L(x)$ : Si $x \in L$.
  2. $NextLive_L(x)$ : Le compte des caractères $a \in \Sigma$ tels que $xa$ peut être étendu pour former une chaîne dans $L$.
     La couleur est assignée comme étant $IsAccept_L(x) + NextLive_L(x)$ (avec une valeur par défaut de 1 pour les chaînes non extensibles).
• Signification : Cette construction est indépendante de la machine (elle repose uniquement sur le langage lui-même) et utilise un alphabet dont la taille est linéaire par rapport à la taille de l'alphabet d'entrée, indépendamment de la complexité de toute machine sous-jacente.

B. Étroitesse de la taille de la palette

• Borne inférieure : Les auteurs prouvent que pour un alphabet binaire ($k=2$), 2 couleurs sont insuffisantes pour satisfaire la condition de coloration distinguable pour toutes les collections de langages (Proposition 8). Une collection finie spécifique de 5 langages nécessite 3 couleurs. Ainsi, $k+1$ est optimal pour le cas général sur un alphabet binaire.
• Coloration d'état pour les automates : Pour les collections d'automates finis, les auteurs définissent des fonctions de coloration d'état (mappant les états vers des couleurs). Ils montrent que $k+1$ couleurs sont également nécessaires et suffisantes pour la condition de distinction dans ce contexte (Lemme 4).

C. Langages réguliers (Théorème 5)

Un raffinement significatif est présenté pour le cas particulier des langages réguliers.

• Résultat : Si la collection $\mathcal{C}$ est composée de langages réguliers infinis, l'identification dans la limite est possible en utilisant seulement 2 couleurs.
• Mécanisme : Les auteurs construisent une séquence de DFA (automates finis déterministes) pour les langages et assignent des couleurs d'état de manière inductive. Pour chaque langage $L_i$, ils sélectionnent des états « vivants » spécifiques pour distinguer $L_i$ de tout sur-ensemble $L_j$ ($j < i$) apparaissant plus tôt dans l'énumération. L'infinitude des langages garantit l'existence de suffisamment d'états pour effectuer cette distinction.
• Optimalité : 2 couleurs sont optimales car 1 couleur ne fournit aucune information (équivalent à l'absence de trace), et les résultats de Gold montrent que certaines collections de langages réguliers infinis ne sont pas identifiables sans traces.

D. Robustesse à la corruption

L'article étend ces résultats à des contextes où les traces peuvent être corrompues (Section 3.1).

• Lemme de coloration robuste : Pour un budget de corruption $\ell$ (distance de Hamming), les auteurs montrent qu'une palette de taille $O(k \cdot 2^\ell)$ suffit pour assurer l'identification dans la limite.
• Coloration d'état : Pour les langages réguliers avec des traces corrompues, une palette de taille $O(k \cdot 2^\ell)$ est suffisante, et $k \cdot 2^{\ell-1}$ est nécessaire.

4. Signification et affirmations

L'article prétend résoudre deux questions fondamentales laissées ouvertes par les travaux précédents sur les traces computationnelles :

1. Indépendance vis-à-vis de la machine : Il démontre que les résultats positifs d'identification ne nécessitent pas l'accès au modèle de machine génératrice sous-jacent ; les traces peuvent être définies directement à partir de la structure du langage.
2. Succinctness (Succinctité) : Il prouve que l'identification peut être réalisée avec un alphabet de jetons très petit (linéaire par rapport à la taille de l'alphabet d'entrée, ou même constant pour les langages réguliers), contrastant avec les travaux précédents qui nécessitaient des alphabets exponentiels ou dépendants de l'état.

Les auteurs soulignent que leur approche est informationnelle. Bien qu'ils spécifient l'existence de fonctions de coloration et d'algorithmes d'identification, ils ne revendiquent pas d'efficacité computationnelle pour le cas général (notant que le test d'appartenance pour des langages arbitraires est indécidable). L'accent est mis sur la possibilité théorique d'identification avec un surcoût d'annotation minimal.

L'article conclut en notant un développement récent et distinct (Charikar et al., 2026) montrant que pour les collections de langages infinis, la coloration à 2 couleurs est possible même avec une « coloration terminale » (coloration de la chaîne entière) en utilisant des méthodes non constructives impliquant la récursion transfinie, soulignant que la borne constructive de $k+1$ de cet article reste le standard naturel indépendant de la machine.