Crescimento comparado do número de classes sintáticas e de Nerode.

Para uma linguagem L ⊆ Σ ^ * , defina a congruência sintática ≡ de L como a menor congruência em Σ ^ * que satura L , ou seja:

u ≡ v ⇔ (∀ x, y) [xuy ∈ L ↔ xvy ∈ L].

Agora defina a equivalência de Nerode como a seguinte congruência correta:

u ∼ v ⇔ (∀ x) [ux ∈ L ↔ vx ∈ L].

Seja [u] a classe de equivalência de u em relação a ≡ e 〈u〉 em relação a ∼ . Agora defina i (n) como o número de [u] diferente para u de tamanho n e defina j (n) de maneira semelhante para ∼ .

Agora, a pergunta é: como as duas funções se relacionam?

Por exemplo, um teorema padrão (Kleene-Schützenberger, acredito) diz que i (n) é limitado por uma constante sempre que j (n) é e reciprocamente.

Pergunta: Existe algum outro resultado nessa tendência? E se um deles for polinomial, por exemplo?

Parece que este artigo http://arxiv.org/abs/1010.3263 pode ser relevante para sua pergunta.

O resumo declara:

$n$$n^{n-1}$$n^{n-1}+n-1$$n^{n-2}+(n-2)2^{n-2}+1$

Assim, até onde eu entendo, isso responde à sua pergunta sobre os tamanhos do semigrupo sintático e de Myhill-Nerode: em geral, a congruência sintática pode ter exponencialmente muitas classes do que a relação Myhill-Nerode.

$n^n$$n$