Resumo Técnico: Identificação de Linguagem com Traços Sucintos e Independentes de Máquina

1. Declaração do Problema

O artigo aborda o problema da identificação de linguagem no limite, um framework originalmente proposto por Gold (1967). Neste cenário, um algoritmo tenta identificar uma linguagem alvo $K$ a partir de uma coleção enumerável de linguagens candidatas $\mathcal{L} = \{L_1, L_2, \dots\}$ através da observação de uma enumeração de strings em $K$. O teorema original de Gold estabeleceu que, para a maioria das famílias não triviais de linguagens, a identificação no limite é impossível sem informações adicionais.

Trabalhos recentes buscaram superar esses resultados negativos introduzindo traços computacionais ou anotações (ex: Papazov e Flammarion, 2025; Bhattamishra et al., 2026; Peng et al., 2026). Esses trabalhos postulam que, se os dados de treinamento forem aumentados com traços gerados pelo modelo de máquina subjacente (ex: estados de um autômato finito ou configurações de uma máquina de Turing), a identificação torna-se possível. No entanto, essas abordagens existentes sofrem de duas limitações:

1. Dependência de Máquina: Elas requerem o conhecimento do modelo de máquina específico que gera a linguagem.
2. Tamanho do Alfabeto: Os traços frequentemente exigem alfabetos grandes (ex: o conjunto completo de estados da máquina ou conjuntos de potência de vocabulários), o que é impraticável para modelos de larga escala.

Os autores perguntam: Podemos obter resultados positivos para a identificação de linguagem usando traços que são (a) independentes de qualquer modelo de máquina subjacente e (b) definidos sobre um alfabeto pequeno e sucinto?

2. Metodologia e Definições

O Modelo de Traço

Os autores definem uma função de coloração de traço $c$ sobre um conjunto finito de cores (uma "paleta") $P$. Para uma string $x = x_1 x_2 \dots x_n$, o traço de cor é definido como a sequência de cores aplicadas a cada prefixo da string:
$$\text{trace}_c(x) := (c(\epsilon), c(x_{\le 1}), c(x_{\le 2}), \dots, c(x_{\le n}))$$
onde $x_{\le i}$ é o prefixo de comprimento $i$. Diferente dos traços baseados em máquinas, esta definição aplica-se a qualquer linguagem sem assumir um autômato gerador.

Condição de Identificação

O artigo estabelece uma condição necessária e suficiente para que uma coleção $\mathcal{C}$ seja identificável no limite com traços de cor (Teorema 1). Esta condição generaliza os conjuntos "tell-tale" de Angluin: para toda linguagem $L \in \mathcal{C}$, deve existir um subconjunto finito $T_L \subseteq L$ tal que, para qualquer subconjunto próprio $L' \subset L$, ou $L'$ não contém $T_L$, ou existe uma string $x \in L'$ onde o traço de $x$ sob $L'$ difere do traço de $x$ sob $L$.

Para simplificar a construção, os autores focam em uma "condição de coloração distinguível" mais forte: para quaisquer $L, L' \in \mathcal{C}$ onde $L \subsetneq L'$, existe um $x \in L$ tal que $\text{trace}_{c_L}(x) \neq \text{trace}_{c_{L'}}(x)$. Se esta condição for satisfeita, os conjuntos "tell-tale" não são necessários, e a identificação é garantida.

3. Principais Contribuições e Resultados

A. Coleções de Linguagens Gerais (Teorema 3)

O principal resultado demonstra que, para qualquer coleção enumerável de linguagens sobre um alfabeto finito $\Sigma$ de tamanho $k$, existem funções de coloração de traço usando uma paleta de tamanho $k+1$ que satisfazem a condição de coloração distinguível.

• Construção: A função de coloração $c_L(x)$ é definida com base em duas propriedades da string $x$ em relação à linguagem $L$:
  1. $IsAccept_L(x)$: Se $x \in L$.
  2. $NextLive_L(x)$: A contagem de caracteres $a \in \Sigma$ tais que $xa$ pode ser estendida para formar uma string em $L$.
     A cor é atribuída como $IsAccept_L(x) + NextLive_L(x)$ (com um padrão de 1 para strings não extensíveis para $L$).
• Significância: Esta construção é independente de máquina (depende apenas do conjunto da linguagem) e utiliza um tamanho de alfabeto linear ao tamanho do alfabeto de entrada, independente da complexidade de qualquer máquina subjacente.

B. Rigidez do Tamanho da Paleta

• Limite Inferior: Os autores provam que, para um alfabeto binário ($k=2$), 2 cores são insuficientes para satisfazer a condição de coloração distinguível para todas as coleções de linguagens (Proposição 8). Uma coleção finita específica de 5 linguagens requer 3 cores. Assim, $k+1$ é ótimo para o caso geral sobre um alfabeto binário.
• Coloração de Estado para Autômatos: Para coleções de autômatos finitos, os autores definem funções de coloração de estado (mapeando estados para cores). Eles mostram que $k+1$ cores também são necessárias e suficientes para a condição distinguível neste cenário (Lema 4).

C. Linguagens Regulares (Teorema 5)

Uma simplificação significativa é apresentada para o caso especial de linguagens regulares.

• Resultado: Se a coleção $\mathcal{C}$ consiste de linguagens regulares infinitas, a identificação no limite é possível usando apenas 2 cores.
• Mecanismo: Os autores constroem uma sequência de DFAs para as linguagens e atribuem cores de estado indutivamente. Para cada linguagem $L_i$, eles selecionam estados "vivos" específicos para distinguir $L_i$ de qualquer superconjunto $L_j$ ($j < i$) que apareça anteriormente na enumeração. A infinitude das linguagens garante que existam estados suficientes para realizar essa distinção.
• Otimalidade: 2 cores são ótimas porque 1 cor não fornece informação (equivalente a nenhum traço), e os resultados de Gold mostram que algumas coleções de linguagens regulares infinitas não são identificáveis sem traços.

D. Robustez à Corrupção

O artigo estende estes resultados para cenários onde os traços podem ser corrompidos (Seção 3.1).

• Lema de Coloração Robusta: Para um orçamento de corrupção $\ell$ (distância de Hamming), os autores mostram que uma paleta de tamanho $O(k \cdot 2^\ell)$ é suficiente para garantir a identificação no limite.
• Coloração de Estado: Para linguagens regulares com traços corrompidos, uma paleta de tamanho $O(k \cdot 2^\ell)$ é suficiente, e $k \cdot 2^{\ell-1}$ é necessária.

4. Significância e Alegações

O artigo afirma resolver duas questões fundamentais deixadas por trabalhos anteriores sobre traços computacionais:

1. Independência de Máquina: Demonstra que resultados positivos de identificação não requerem acesso ao modelo de máquina geradora subjacente; os traços podem ser definidos diretamente da estrutura da linguagem.
2. Sucintude: Prova que a identificação pode ser alcançada com um alfabeto de tokens muito pequeno (linear ao tamanho do alfabeto de entrada, ou até constante para linguagens regulares), contrastando com trabalhos anteriores que exigiam alfabetos exponenciais ou dependentes de estado.

Os autores enfatizam que sua abordagem é teórica da informação. Embora especifiquem a existência de funções de coloração e algoritmos de identificação, eles não alegam eficiência computacional para o caso geral (notando que o teste de pertinência para linguagens arbitrárias é indecidível). O foco é na possibilidade teórica de identificação com o mínimo de sobrecarga de anotação.

O artigo conclui observando que um desenvolvimento recente e separado (Charikar et al., 2026) mostra que, para coleções de linguagens infinitas, a coloração de 2 cores é possível mesmo com "coloração terminal" (colorindo a string inteira de uma vez) usando métodos não construtivos envolvendo recursão transfinita, destacando que o limite construtivo de $k+1$ deste artigo permanece como o padrão natural e independente de máquina.