I want to have an overview of all the meaningful equivalence relations defined on $X^{\ast}$, in particular when the languages in question are regular. They typically arise in connection with the minimization of automata. Further I want to know all the relations among them. Below I write what I know, I encourage everyone to add useful facts to this list, give other equivalence relations and how they relate to the given ones!?

Common equivalence relations on $X^{\ast}$ are \begin{align*} u \equiv_L v & :\Leftrightarrow \forall w \in X^{\ast} : uw \in L \leftrightarrow vw \in L \\ u \equiv_R v & :\Leftrightarrow \forall w \in X^{\ast} : wu \in L \leftrightarrow wv \in L \\ u \equiv_S v & :\Leftrightarrow \forall w_1, w_2 \in X^{\ast} : w_1uw_2 \in L \leftrightarrow w_1vw_2 \in L \end{align*} If we have some deterministic and complete automaton $\mathcal A = (X,Q,\delta,q_0,F)$ with $L = L(\mathcal A)$, then every $u \in X^{\ast}$ corresponds to a function $\varphi_u : Q \to Q$. Then we can define $$ u \equiv_A v :\Leftrightarrow \delta(q_0, u) = \delta(q_0,v) \Leftrightarrow \varphi_u(q_0) = \varphi_v(q_0). $$ Also for states $q, q' \in Q$ we could define $$ q \equiv q' :\Leftrightarrow \forall u \in X^{\ast} : \delta(q, u) = \delta(q',u) \Leftrightarrow \varphi_u(q) = \varphi_v(q') $$ and by incorporating the final states (and thereby fitting it more to the conrete language $L$) we could define $$ q \equiv^L q' :\Leftrightarrow \forall u \in X^{\ast} : \delta(q, u) \in F \leftrightarrow \delta(q', u) \in F. $$ And if we have some recognizing monoid $M$ with homomorphism $\varphi : X^{\ast} \to M$ we could define $$ u \equiv_h v :\Leftrightarrow h(u) = h(v). $$ We have (the automaton is arbitrary) \begin{align*} u \equiv_L v & \Leftrightarrow \delta(q_0, u) \equiv^L \delta(q_0,v) \\ u \equiv_R v & \Leftrightarrow \forall q \in Q : \delta(q, u) \in F \leftrightarrow \delta(q, v) \in F \\ u \equiv_S v & \Leftrightarrow \forall q \in Q : \delta(q, u) \equiv^L \delta(q,v) \\ u \equiv_h v & \Rightarrow u \equiv_S v \\ u \equiv_S v & \Rightarrow u \equiv_L v \land u \equiv_R v \\ u \equiv_A v & \Rightarrow u \equiv_L v \\ \varphi_u = \varphi_v & \Rightarrow u \equiv_S v \\ u \equiv_S v & \Leftrightarrow \forall q \in Q : \varphi_u(q) \in F \leftrightarrow \varphi_v(q) \in F \end{align*} And we have that the syntactic monoid is precisely the transformation monoid of the minimal automaton (which could be constructed with $\equiv_L$). Also the above notions could be described in terms of language quotients $u^{-1}L := \{ w : uw \in L \}, Lu^{-1} := \{ w : wu \in L \}$ (and the minimal automaton could also be constructed with the quotients $u^{-1}L$) or the sets $L_q(\mathcal A) := (X,Q,\delta,q,F)$ (i.e. the language accepted if $\mathcal A$ is started at $q$).

  • 1
    $\begingroup$ This does not seem to be a research level question, or it is too broad: what is a "meaningful equivalence relation"? Take a monoid morphism from $X^*$ to another monoid, then its nuclear congruence will be an equivalence relation. $\endgroup$
    – J.-E. Pin
    May 30, 2016 at 6:50

1 Answer 1


The article by Thomas Colcombet on Green's Relations and Their Use in Automata Theory might be interesting for you. These relations are very common in the algebra of semigroups.

See also Section 2.8 in Chapter 10 of the Handbook of Formal Languages.

  • 1
    $\begingroup$ Green's relations on $X^*$ are the equality relation, so I don't think they are relevant to this question. $\endgroup$
    – J.-E. Pin
    May 30, 2016 at 6:46
  • 1
    $\begingroup$ Sorry! Reading so much about the automaton of a specific automaton in the question, I forgot that it was only about $X^*$... But the "when the languages in question are regular" might indicate that the real intention of the question is a bit different. So I will not delete my answer for the moment. $\endgroup$ May 30, 2016 at 8:17
  • 2
    $\begingroup$ I think your answer is a valuable addition, as my question is rather broad. $\endgroup$
    – StefanH
    Jun 3, 2016 at 10:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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