Nombre de classes d'équivalence dans les langues régulières en fonction de la taille de DFA

Cette question est liée à une question récente de Janoma .

Contexte

Dans la programmation par contraintes, une régulière contrainte globale $c$ sur un domaine $D$ est une paire $(s, M)$ avec $s$ un tuple de variables (la portée) et $M$ DFA sur le domaine $D$ . Une affectation $\theta$ à $s$ satisfait $c$ si $M$ accepte la chaîne $\theta(s_1)\theta(s_2)\ldots\theta(s_n)$ .

Ci-dessous, supposons que le domaine $D$ est fixe. Définissons une relation d'équivalence $\sim$ sur l'ensemble des chaînes $T = D^{|s|}$tel que $a \sim b$ si pour chaque DFA $M$ soit $a, b \in L(M)$ ou $a, b \not\in L(M)$ . Intuitivement, deux chaînes sont équivalentes si aucun DFA ne peut les distinguer. Si cela est vrai, ils satisfont également aux mêmes contraintes régulières .

Si nous ne restreignons en aucune façon les DFA, alors l'ensemble des classes d'équivalence $T/{\sim}$ n'est que $T$ lui-même. Je suis intéressé par le nombre de classes d'équivalence par rapport à. $\sim$ en fonction du nombre d'états $n$ que l'on admet pour le DFA. Clairement, si $n = |D|^{|s|}$(ignorer les constantes) alors $|T/{\sim}| = |T|$. (Bien sûr, $n$ ici sera lui-même fonction de $|s|$ .)

Des questions

1. Quel est le plus petit $n$ pour lequel $|T/{\sim}| = |T|$?
2. Que se passe-t-il en dessous? En particulier,
   • y a-t-il un $n$ tel que $|T/{\sim}| = O(|s|^{|D|})$ ?
   • y a-t-il un $n$ tel que $|T/{\sim}| = O(|s| \times |D|)$ ?

$|s|^{|D|}$

$k$$\geq k$

Réponse à la question 1,

Quel est le plus petit n pour lequel | T / ∼ | = | T | $n$$|T/{\sim}|=|T|$

$$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})$ .

qui a été obtenu en

Robson, JM , Séparation des chaînes avec de petits automates , Inf. Processus. Lett. 30, n ° 4, 209-214 (1989). ZBL0666.68051 .