Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 Jan 3 '12 at 12:19
    
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 Jan 3 '12 at 13:24
    
Yes, I think I understand the question as you intended. I have just posted a little more detail as an answer. –  Tsuyoshi Ito Jan 3 '12 at 14:19

2 Answers 2

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, uxLuyL. 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:

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

share|improve this answer
    
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 Jan 3 '12 at 19:43
up vote 3 down vote accepted

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

share|improve this answer
    
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 Jan 3 '12 at 20:32
    
... 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 Jan 3 '12 at 20:38
    
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 Jan 3 '12 at 20:40
    
@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 Jan 4 '12 at 2:51
    
@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 Jan 4 '12 at 4:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.