# Useful equivalence relations on $X^{\ast}$ (like the Nerode and syntactic equivalence relations)

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

• 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. – J.-E. Pin May 30 '16 at 6:50

• Green's relations on $X^*$ are the equality relation, so I don't think they are relevant to this question. – J.-E. Pin May 30 '16 at 6:46
• 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. – Peter Leupold May 30 '16 at 8:17