<p>The article by Thomas Colcombet on <a href="https://www.google.es/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=1&amp;cad=rja&amp;uact=8&amp;ved=0ahUKEwiRloWj1__MAhWDrRoKHTgaC74QFggdMAA&amp;url=https%3A%2F%2Fwww.irif.univ-paris-diderot.fr%2F~colcombe%2FPublications%2FLATA11-colcombet.pdf&amp;usg=AFQjCNE3JhlDagIb7FJWI8aKSL3muXmBCQ&amp;bvm=bv.123325700,d.d2s">Green's Relations and Their Use in Automata Theory</a> might be interesting for you. These relations are very common in the algebra of semigroups. </p>

<p>See also Section 2.8 in Chapter 10 of the Handbook of Formal Languages.</p>

CC BY-SA 3.0
2016-05-30T06:46:04.287Z
Green's relations on $X^*$ are the equality relation, so I don't think they are relevant to this question.
J.-E. Pin
CC BY-SA 3.0
2016-05-30T08:17:50.910Z
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
CC BY-SA 3.0
2016-06-03T10:30:20.270Z
I think your answer is a valuable addition, as my question is rather broad.
StefanH
CC BY-SA 3.0
2016-05-29T16:23:07.447Z
2016-05-29T16:23:07.447Z
Peter Leupold
<p>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!?</p>

<p>Common equivalence relations on $X^{\ast}$ are
\begin{align*}
 u \equiv_L v &amp; :\Leftrightarrow
  \forall w \in X^{\ast} : uw \in L \leftrightarrow vw \in L \\
 u \equiv_R v &amp; :\Leftrightarrow
  \forall w \in X^{\ast} : wu \in L \leftrightarrow wv \in L \\
 u \equiv_S v &amp; :\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 &amp; \Leftrightarrow \delta(q_0, u) \equiv^L \delta(q_0,v) \\
 u \equiv_R v &amp; \Leftrightarrow \forall q \in Q : \delta(q, u) \in F \leftrightarrow \delta(q, v) \in F \\
 u \equiv_S v &amp; \Leftrightarrow \forall q \in Q : \delta(q, u) \equiv^L \delta(q,v) \\
 u \equiv_h v &amp; \Rightarrow u \equiv_S v \\
 u \equiv_S v &amp; \Rightarrow u \equiv_L v \land u \equiv_R v \\
 u \equiv_A v &amp; \Rightarrow u \equiv_L v \\
 \varphi_u = \varphi_v &amp; \Rightarrow u \equiv_S v \\
 u \equiv_S v &amp; \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$).</p>

CC BY-SA 3.0
2016-05-30T06:50:36.290Z
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
<fl.formal-languages><automata-theory><regular-language>
Useful equivalence relations on $X^{\ast}$ (like the Nerode and syntactic equivalence relations)
StefanH
# Useful equivalence relations on $X^{\ast}$ (like the Nerode and syntactic equivalence relations)

(Asked by: username_0 on 2016-05-27)

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

**Tags:** fl.formal-languages, automata-theory, regular-language
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2016-05-29. Score: 4 | Accepted answer

The article by Thomas Colcombet on [Green's Relations and Their Use in Automata Theory](https://www.google.es/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0ahUKEwiRloWj1__MAhWDrRoKHTgaC74QFggdMAA&url=https%3A%2F%2Fwww.irif.univ-paris-diderot.fr%2F~colcombe%2FPublications%2FLATA11-colcombet.pdf&usg=AFQjCNE3JhlDagIb7FJWI8aKSL3muXmBCQ&bvm=bv.123325700,d.d2s) 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.

> **Comments:**
> **username_1**: Green's relations on $X^*$ are the equality relation, so I don't think they are relevant to this question.  
> **username_2**: 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.  
> **username_0**: I think your answer is a valuable addition, as my question is rather broad.  

---

