Number of equivalence classes in regular languages as a function of DFA size

Question

This question is related to a recent question by Janoma.

Background

In constraint programming, a regular global constraint $c$ over a domain $D$ is a pair $(s, M)$ with $s$ a tuple of variables (the scope) and $M$ a DFA over the domain $D$. An assignment $\theta$ to $s$ satisfies $c$ if $M$ accepts the string $\theta(s_1)\theta(s_2)\ldots\theta(s_n)$.

Below, assume that the domain $D$ is fixed. Define an equivalence relation $\sim$ over the set of strings $T = D^{|s|}$ such that $a \sim b$ if for every DFA $M$ either $a, b \in L(M)$ or $a, b \not\in L(M)$. Intuitively, two strings are equivalent iff no DFA can distinguish them. If that is true, then they also satisfy the same regular constraints.

If we do not restrict the DFAs in any way, then the set of equivalence classes $T/{\sim}$ is just $T$ itself. I am interested in the number of equivalence classes wrt. $\sim$ as a function of the number of states $n$ that we allow for the DFA. Clearly, if $n = |D|^{|s|}$ (ignore constants) then $|T/{\sim}| = |T|$. (Of course, $n$ here will itself be a function of $|s|$.)

Questions

1. What is the smallest $n$ for which $|T/{\sim}| = |T|$?
2. What happens below that? In particular,
   • is there an $n$ such that $|T/{\sim}| = O(|s|^{|D|})$?
   • is there an $n$ such that $|T/{\sim}| = O(|s| \times |D|)$?

My motivation for this question is that having a polynomial ($|s|^{|D|}$) number of equivalence classes like this gave me a tractable case of constraint problems with cardinality constraints. I am now trying to see if something along these lines can be done for the regular constraint.

Edit: Note also this answer by Hermann Gruber to the question referenced at the top. The bounds in the paper the answer links should yield a $k$ such that the answer to question 1 must be $\geq k$, but it is not obvious to me.

Answer 1

Answer to Question 1,

What is the smallest $n$ for which $|T/{\sim}|=|T|$?

We have $$n=\max_{|w|=|x|=s,\\ w\ne x}\mathrm{sep}(w,x)$$ where $\mathrm{sep}(w,x)$ is the smallest number of states in any DFA that accepts one of $w$ and $x$, but not the other. The best known upper bound on $n$ is then (see some slides by Jeffrey Shallit)

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

which was obtained in

Robson, J. M., Separating strings with small automata, Inf. Process. Lett. 30, No. 4, 209-214 (1989). ZBL0666.68051.