Smallest representatives of a quotient by an equivalence relation Background

Let $\mathcal{A}=(Q,\Sigma,\delta,q_0,F)$ be a minimal DFA for a regular language $L$ such that $|Q|=n$, and let $\equiv_L$ be the relation given by $$x\equiv_Ly\text{ iff for all $u$: }xu\in L\Leftrightarrow yu\in L.$$ It is known we can identify the states of $\mathcal{A}$ with the elements of the quotient $\Sigma^*/\equiv_L$. Moreover, since $\equiv_L$ can be characterized by $$x\equiv_Ly\text{ iff }\hat\delta(q_0,x)=\hat\delta(q_0,y),$$ we know we can choose elements $w_1,\ldots,w_n\in\Sigma^*$ such that $$Q=\big\{[w_i]_{\equiv_L}: i\in\{1,\ldots,n\}\big\},$$ and $|w_i|\leq n$ for all $i$, that is, we can choose representatives for $\Sigma^*/\equiv_L$ of length at most $n$.

This is useful because, given the minimal DFA $\mathcal{A}$ (whose states might be given in an abstract way, not necessarily with elements of $\Sigma^*/\equiv_L$), we can obtain a set of representatives of $\Sigma^*/\equiv_L$ by running $\mathcal{A}$ with all inputs of length at most $n$ and marking the states that have already been reached with a flag. Whenever an unmarked state is reached with a string $w$, we flag the state and add $w$ to the list of representatives. This might not be the most elegant or efficient algorithm, but thanks to the upper bound we can be sure it finished and it computes what we want.

Question

Is there a general method of estimating a minimal length of representatives of an equivalence relation? I'm assuming, of course, that the universe consists of elements of finite length (e.g. $\Sigma^*$).

In particular, I'm looking for a similar upper bound for the relation $\sim_L$ given by $$x\sim_Ly\text{ iff for all $u,v$: }uxv\in L\Leftrightarrow uyv\in L,$$ which can be characterized by $$x\sim_Ly\text{ iff for all $q\in Q$: }\hat\delta(q,x)=\hat\delta(q,y),$$ where the automaton is minimal.

Thanks in advance for your guidance.

Update: to be a bit more precise, what I want is an upper bound $M$ for the smallest representative of a class, so I can do an algorithm of the form: ``check all the words of length at most $M$...'' and be sure that all classes are covered by some representative at least once.
It seems to me that your question is too general to answer.  Let me focus on the case of ∼L.  Then here is an example which shows a lower bound; namely, the length of a representative can be at least $e^{(1-o(1))\sqrt{n \ln n}}$, where n is the number of states of the minimum DFA.

We will actually show a lower bound on the length of a representative with respect to the right-equivalence relation RL on strings defined as: x RL y if and only if for all strings u, ux∈L ⇔ uy∈L.  Because equivalence relation RL is coarser than ∼L, any complete set of representatives with respect to ∼L must contain a complete set of representatives with respect to RL, and therefore a lower bound shown for RL applies also to ∼L.

Number-theoretic preparations.  Let pK be the Kth prime number.  We write the sum of the first K primes as Σ(K).  We also write the product of the primes that are less than or equal to N as N# (the primorial of N).  Then the following facts are known:


pK ∼ K ln K (from the prime number theorem).
Σ(K) ∼ K2 ln K (see the MathWorld article on prime sums).
ln(N#) ∼ N (see the MathWorld article on Chebyshev functions).


By combining these facts, we obtain that $\lim_{K\to\infty}\frac{\ln(p_K \#)}{\sqrt{\Sigma(K) \ln \Sigma(K)}} = 1$, and therefore $p_K \# = e^{(1-o(1))\sqrt{\Sigma(K) \ln \Sigma(K)}}$.

(I think that this final statement is a standard fact in the number theory, but I do not know a good reference for it.  See a related discussion in comments to this post.)

Construction and analysis.  For k∈ℕ, construct a DFA Mk on the alphabet {0, 1} as follows.  Let K=2k.  First, there is a complete binary tree of depth k rooted at the initial state.  Label the K leaves of this binary tree as q1, …, qK.  At each qi, we add a cycle of length pi, labeling each edge of the cycle with both 0 and 1 (that is, once you reach state qi, only the length of the rest of the string matters).  Mark the K states q1, …, qK as accepting states.

If x RL y, then we have that |x|≡|y| (mod pi) for every i≤K by prepending the binary notation of i−1 and some string of an appropriate length to both x and y.  This means that any complete set of representatives with respect to the relation RL contains at least one string with length at least pK#−1.

The number of the states in DFA Mk is K−1+∑i=1K pi = Σ(K)+K−1.  If we denote this number as n, then n ∼ Σ(K), and the length of at least one representative must be at least $p_K \# - 1 = e^{(1-o(1))\sqrt{n \ln n}}$.