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