<p>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).$$</p>

<p>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).</p>

<p>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$.</p>

CC BY-SA 3.0
2012-01-03T20:32:04.150Z
You can define the automaton $\mathcal{A}_{\times}$ to have $2^n$ states instead, each state corresponding to a subset (rather than an array) of the states of $\mathcal{A}$.  Everything else goes through as before.
mjqxxxx
CC BY-SA 3.0
2012-01-03T20:38:55.450Z
... The advantage is that this bound is, I think, logarithmically tight, as shown by Tsuyoshi's answer.  That is, the size of minimal representatives is $O^{*}(e^n)$, and Tsuyoshi gave an example where minimal representatives have size $\Omega^{*}(e^n)$.
mjqxxxx
CC BY-SA 3.0
2012-01-03T20:40:37.950Z
I don't think everything else remains the same. How do you define $\delta_{\times}$ in that case? I think that if $\delta_{\times}(\mathbf{q},x)$ is defined as $\{\hat\delta(q,x):q\in\mathbf{q}\}$, then you don't have the equivalence $x\star y$ iff $x\sim_L y$.
Janoma
CC BY-SA 3.0
2012-01-04T02:51:30.660Z
@mjqxxxx: I think that the lower bound I gave is something like $\exp(n^{1/2-o(1)})$.  (I do not know the meaning of the notation $\Omega^*(e^n)$, and therefore I might be saying the same thing as what you said.)
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-04T04:25:15.687Z
@Tsuyoshi: It means the logarithm is $\Omega(n)$, which it isn't if it's only $\Omega(\sqrt{n})$, so I guess I'm wrong.  But that's okay, because as Janoma correctly points out, I'm wrong about the automaton with $2^n$ states too :).
mjqxxxx
CC BY-SA 3.0
2012-01-04T04:31:15.723Z
@mjqxxxx: Oh, I see.  Thanks for the explanation!
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-03T20:25:21.610Z
2012-01-03T20:25:21.610Z
Janoma
<p>It seems to me that your question is too general to answer.  Let me focus on the case of ∼<sub><i>L</i></sub>.  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 <i>n</i> is the number of states of the minimum DFA.</p>

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

<p><strong>Number-theoretic preparations</strong>.  Let <i>p</i><sub><i>K</i></sub> be the <i>K</i>th prime number.  We write the <a href="http://mathworld.wolfram.com/PrimeSums.html" rel="nofollow noreferrer">sum of the first <i>K</i> primes</a> as Σ(<i>K</i>).  We also write the product of the primes that are less than or equal to <i>N</i> as <i>N</i># (the <a href="http://mathworld.wolfram.com/Primorial.html" rel="nofollow noreferrer">primorial</a> of <i>N</i>).  Then the following facts are known:</p>

<ul>
<li><i>p</i><sub><i>K</i></sub> ∼ <i>K</i> ln <i>K</i> (from the <a href="http://en.wikipedia.org/wiki/Prime_number_theorem" rel="nofollow noreferrer">prime number theorem</a>).</li>
<li>Σ(<i>K</i>) ∼ <i>K</i><sup>2</sup> ln <i>K</i> (see the <a href="http://mathworld.wolfram.com/PrimeSums.html" rel="nofollow noreferrer">MathWorld article on prime sums</a>).</li>
<li>ln(<i>N</i>#) ∼ <i>N</i> (see the <a href="http://mathworld.wolfram.com/ChebyshevFunctions.html" rel="nofollow noreferrer">MathWorld article on Chebyshev functions</a>).</li>
</ul>

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

<p>(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 <a href="https://cstheory.stackexchange.com/questions/3496/conditions-for-nfa-universality/3502#3502">this post</a>.)</p>

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

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

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

CC BY-SA 3.0
2012-01-03T19:43:56.663Z
I see what you meant before, but I still need an upper bound for the smallest representative. With my adviser we came up with a solution, I will post it as soon as I finish with other stuff.
Janoma
CC BY-SA 3.0
2012-01-03T14:17:30.367Z
2012-01-04T12:50:44.887Z
2017-04-13T12:32:28.053Z
Tsuyoshi Ito
<h2>Background</h2>

<p>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$.</p>

<p>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.</p>

<h2>Question</h2>

<p>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^*$).</p>

<p>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.</p>

<p>Thanks in advance for your guidance.</p>

<p><strong>Update:</strong> to be a bit more precise, what I want is an upper bound $M$ for the <em>smallest</em> 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.</p>

CC BY-SA 3.0
2012-01-03T12:19:59.013Z
In the case of $\sim_L$, the length of a representative can be at least exponential in the number of states of the minimum DFA: consider a DFA which contains cycles of different prime lengths.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-03T13:24:33.830Z
Can you elaborate a bit? So you are saying that for some of the classes, the length of the *smallest* representative is exponential in the number of states? Just to be clear: I'm looking for an upper bound to the smallest representative of a class.
Janoma
CC BY-SA 3.0
2012-01-03T14:19:21.550Z
Yes, I think I understand the question as you intended.  I have just posted a little more detail as an answer.
Tsuyoshi Ito
<fl.formal-languages><automata-theory><algebra>
Smallest representatives of a quotient by an equivalence relation
Janoma
# Smallest representatives of a quotient by an equivalence relation

(Asked by: username_0 on 2012-01-03)

## 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.

**Tags:** fl.formal-languages, automata-theory, algebra

> **Comments:**
> **username_1**: In the case of $\sim_L$, the length of a representative can be at least exponential in the number of states of the minimum DFA: consider a DFA which contains cycles of different prime lengths.  
> **username_0**: Can you elaborate a bit? So you are saying that for some of the classes, the length of the *smallest* representative is exponential in the number of states? Just to be clear: I'm looking for an upper bound to the smallest representative of a class.  
> **username_1**: Yes, I think I understand the question as you intended.  I have just posted a little more detail as an answer.  

---

## 2 answers

### Answer by username_0 on 2012-01-03. Score: 3 | Accepted answer

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

> **Comments:**
> **username_2**: You can define the automaton $\mathcal{A}_{\times}$ to have $2^n$ states instead, each state corresponding to a subset (rather than an array) of the states of $\mathcal{A}$.  Everything else goes through as before.  
> **username_2**: ... The advantage is that this bound is, I think, logarithmically tight, as shown by Tsuyoshi's answer.  That is, the size of minimal representatives is $O^{*}(e^n)$, and Tsuyoshi gave an example where minimal representatives have size $\Omega^{*}(e^n)$.  
> **username_0**: I don't think everything else remains the same. How do you define $\delta_{\times}$ in that case? I think that if $\delta_{\times}(\mathbf{q},x)$ is defined as $\{\hat\delta(q,x):q\in\mathbf{q}\}$, then you don't have the equivalence $x\star y$ iff $x\sim_L y$.  
> **username_1**: @username_2: I think that the lower bound I gave is something like $\exp(n^{1/2-o(1)})$.  (I do not know the meaning of the notation $\Omega^*(e^n)$, and therefore I might be saying the same thing as what you said.)  
> **username_2**: @Tsuyoshi: It means the logarithm is $\Omega(n)$, which it isn't if it's only $\Omega(\sqrt{n})$, so I guess I'm wrong.  But that's okay, because as username_0 correctly points out, I'm wrong about the automaton with $2^n$ states too :).  
> **username_1**: @username_2: Oh, I see.  Thanks for the explanation!  

---

### Answer by username_1 on 2012-01-03. Score: 7

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 *K*th prime number. We write the [sum of the first *K* primes](http://mathworld.wolfram.com/PrimeSums.html) as Σ(*K*). We also write the product of the primes that are less than or equal to *N* as *N*# (the [primorial](http://mathworld.wolfram.com/Primorial.html) of *N*). Then the following facts are known:

* *p**K* ∼ *K* ln *K* (from the [prime number theorem](http://en.wikipedia.org/wiki/Prime_number_theorem)).
* Σ(*K*) ∼ *K*2 ln *K* (see the [MathWorld article on prime sums](http://mathworld.wolfram.com/PrimeSums.html)).
* ln(*N*#) ∼ *N* (see the [MathWorld article on Chebyshev functions](http://mathworld.wolfram.com/ChebyshevFunctions.html)).

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](https://cstheory.stackexchange.com/questions/3496/conditions-for-nfa-universality/3502#3502).)

**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*1, …, *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*1, …, *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}}$.

> **Comments:**
> **username_0**: I see what you meant before, but I still need an upper bound for the smallest representative. With my adviser we came up with a solution, I will post it as soon as I finish with other stuff.  

---

