Crecimiento comparado del número de clases sintácticas y clases de Nerode.

Para un lenguaje L ⊆ Σ ^ * , defina la congruencia sintáctica ≡ de L como la menor congruencia en Σ ^ * que satura L , es decir:

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

Ahora defina la equivalencia de Nerode como la siguiente congruencia correcta:

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

Sea [u] la clase de equivalencia de u con respecto a ≡ y 〈u〉 con respecto a ∼ . Ahora defina i (n) como el número de [u] diferentes para u de tamaño n , y defina j (n) de manera similar para ∼ .

Ahora la pregunta es, ¿cómo se relacionan las dos funciones?

Por ejemplo, un teorema estándar (Kleene-Schützenberger, creo) dice que i (n) está limitado por una constante siempre que j (n) es, y recíprocamente.

Pregunta: ¿Hay algún otro resultado en esta tendencia? ¿Qué pasa si uno de ellos es polinómico, por ejemplo?

Parece que este documento http://arxiv.org/abs/1010.3263 puede ser relevante para su pregunta.

El resumen dice:

La complejidad del estado de un lenguaje regular es el número de estados en el autómata determinista mínimo que acepta el lenguaje. La complejidad sintáctica de un lenguaje regular es la cardinalidad de su semigrupo sintáctico. La complejidad sintáctica de una subclase de idiomas regulares es la peor complejidad sintáctica tomada en función de la complejidad del estado de los idiomas en esa clase. Estudiamos la complejidad sintáctica de la clase de idiomas ideales regulares y sus complementos, los idiomas cerrados. Demostramos que es un límite superior ajustado a la complejidad de los ideales correctos y los idiomas cerrados con prefijo, y que existen ideales izquierdos y lenguajes cerrados de complejidad sintáctican n - 1 n n - 1 + n - 1 n n - 2 + ( n - 2 ) 2 n - 2 + $n$$n^{n-1}$$n^{n-1}+n-1$, e ideales de dos lados y lenguajes cerrados de factor de complejidad sintáctica .$n^{n-2}+(n-2)2^{n-2}+1$

Por lo tanto, hasta donde yo entiendo, esto responde a su pregunta sobre los tamaños del semigrupo sintáctico y de Myhill-Nerode: en general, la congruencia sintáctica puede tener exponencialmente muchas clases que la relación de Myhill-Nerode.

El ultimo comentario. Por lo general, la finitud de ambos semigrupos para los idiomas regulares se atribuye a M.Rabin y D.Scott (autómatas finitos y sus problemas de decisión. IBM Jourmal. Abril de 1959). En particular, del texto de Rabin y Scott se deduce que el número de clases sintácticas no excede , donde es el número de clases de Myhill-Nerode.$n^n$$n$