Smallest representatives of a quotient by an equivalence relation

Question

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.

Answer 1

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 R_L on strings defined as: x R_L y if and only if for all strings u, ux∈L ⇔ uy∈L. Because equivalence relation R_L is coarser than ∼_L, any complete set of representatives with respect to ∼_L must contain a complete set of representatives with respect to R_L, and therefore a lower bound shown for R_L applies also to ∼_L.

Number-theoretic preparations. Let p_K 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:

• p_K ∼ K ln K (from the prime number theorem).
• Σ(K) ∼ K² 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 M_k on the alphabet {0, 1} as follows. Let K=2^k. First, there is a complete binary tree of depth k rooted at the initial state. Label the K leaves of this binary tree as q₁, …, q_K. At each q_i, we add a cycle of length p_i, labeling each edge of the cycle with both 0 and 1 (that is, once you reach state q_i, only the length of the rest of the string matters). Mark the K states q₁, …, q_K as accepting states.

If x R_L y, then we have that |x|≡|y| (mod p_i) 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 R_L contains at least one string with length at least p_K#−1.

The number of the states in DFA M_k is K−1+∑_i=1^K p_i = Σ(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}}$.

Answer 2

Consider a minimal DFA $\mathcal{A}=(Q,\Sigma,\delta,q_0,F)$ and its accepted language $L$. Assume that $Q=\{q_0,\ldots,q_{n-1}\}$, and consider the automaton $\mathcal{A}_{\times}=(Q^n,\Sigma,\delta_{\times},q_{\times},F^n)$, with $q_{\times}=(q_0,\ldots,q_{n-1})$ and $\delta_{\times}$ given by $$\delta_{\times}\left((q_{i_1},\ldots,q_{i_n}),a\right)=\left(\delta(q_{i_1},a),\ldots,\delta(q_{i_n},a)\right).$$ On input $w$, $\mathcal{A}_{\times}$ simulates $\mathcal{A}$ processing $w$ starting from all possible states, so, in particular, $$\hat\delta_{\times}\left(q_{\times},w\right)=\left(\hat\delta(q_0,w),\ldots,\hat\delta(q_{n-1},w)\right).$$

We define now a relation on $\Sigma^*$ by $x\star y$ if $\hat\delta_{\times}(q_{\times},x)=\hat\delta_{\times}(q_{\times},y)$. It is easy to see that $\star$ is an equivalence relation. Moreover, for $x,y\in\Sigma^*$, $$x\star y$$ if and only if $$\hat\delta_{\times}(q_{\times},x)=\hat\delta_{\times}(q_{\times},y)$$ if and only if $$\hat\delta(q_i,x)=\hat\delta(q_i,y)\text{ for all }i=0,\ldots,n-1$$ if and only if $$x\sim_L y,$$ so $\Sigma^*/\sim_L=\Sigma^*/\star$. In particular, since $\mathcal{A}_{\times}$ has $n^n$ states, we can choose a representative for each element of $\Sigma^*/\star$ (and therefore of $\Sigma^*/\sim_L$) whose length is at most $n^n$ (a representative for the class $[w]_{\star}=[w]_{\sim_L}$ is a shortest word that takes $q_{\times}$ to $\hat\delta_{\times}(q_{\times},w)$, and the length of that word is at most the number of states).

Thus, any algorithm that processes all strings of length at most $n^n$ will cover all equivalence classes of $\sim_L$ by means of at least one representative per class, which is what I wanted. In other words, $n^n$ is an upper bound for the length of the smallest representative of an arbitrary class in $\Sigma^*/\sim_L$.