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
- What is the smallest $n$ for which $|T/{\sim}| = |T|$?
- 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.