Número de clases de equivalencia en idiomas regulares en función del tamaño de DFA

Esta pregunta está relacionada con una pregunta reciente de Janoma .

Antecedentes

En la programación de restricción, un regular de restricción global sobre un dominio es un par con una tupla de variables (el alcance) y un DFA sobre el dominio . Una asignación a satisface si acepta la cadena .$c$$D$$(s, M)$$s$$M$$D$$\theta$$s$$c$$M$$\theta(s_1)\theta(s_2)\ldots\theta(s_n)$

A continuación, suponga que el dominio es fijo. Defina una relación de equivalencia sobre el conjunto de cadenas modo que si para cada DFA sea o . Intuitivamente, dos cadenas son equivalentes si ningún DFA puede distinguirlas. Si eso es cierto, entonces también satisfacen las mismas restricciones regulares .$D$$\sim$$T = D^{|s|}$$a \sim b$$M$$a, b \in L(M)$$a, b \not\in L(M)$

Si no restringimos los DFA de ninguna manera, entonces el conjunto de clases de equivalencia es solo sí. Estoy interesado en el número de clases de equivalencia wrt. en función del número de estados que permitimos para el DFA. Claramente, si (ignorar las constantes) entonces. (Por supuesto, aquí será una función de .)$T/{\sim}$$T$$\sim$$n$$n = |D|^{|s|}$$|T/{\sim}| = |T|$$n$$|s|$

Preguntas

1. ¿Cuál es la más pequeña para la cual?$n$$|T/{\sim}| = |T|$
2. ¿Qué pasa debajo de eso? En particular,
   • ¿hay una tal que ?$n$$|T/{\sim}| = O(|s|^{|D|})$
   • ¿hay una tal que ?$n$$|T/{\sim}| = O(|s| \times |D|)$

Mi motivación para esta pregunta es que tener un número polinómico ( ) de clases de equivalencia como esta me dio un caso manejable de problemas de restricción con restricciones de cardinalidad. Ahora estoy tratando de ver si se puede hacer algo en esta línea para la restricción regular.$|s|^{|D|}$

Editar : Tenga en cuenta también esta respuesta de Hermann Gruber a la pregunta mencionada en la parte superior. Los límites en el papel de los enlaces de respuesta deberían arrojar una tal que la respuesta a la pregunta 1 debe ser , pero no es obvio para mí.$k$$\geq k$

Respuesta a la pregunta 1,

¿Cuál es la más pequeña para la cual?$n$$|T/{\sim}|=|T|$

Tenemos donde es el número más pequeño de estados en cualquier DFA que acepte uno de y , pero no el otro. El límite superior más conocido en es entonces (ver algunas diapositivas de Jeffrey Shallit )

$$n=\max_{|w|=|x|=s,\\ w\ne x}\mathrm{sep}(w,x)$$ $\mathrm{sep}(w,x)$$w$$x$$n$

$n=O(s^{2/5}(\log s)^{3/5})$ .

que se obtuvo en

Robson, JM , Separación de cuerdas con pequeños autómatas , Inf. Proceso. Letón. 30, núm. 4, 209-214 (1989). ZBL0666.68051 .