<p>Your assertion is wrong, the congruence $\equiv$ is not cancellable from the right: for instance $\bar a a \bar a \equiv \bar a$, but $\bar a a \not\equiv 1$.</p>

<p>By the way the quotient $\Sigma^*/{\equiv}$ is not a group, but a monoid, called the <em>polycyclic monoid</em>, first introduced in [1].</p>

<p>[1] M. Nivat and J-F. Perrot, Une généralisation du monoïde bicyclique, <em>Comptes Rendus de l'Academie des Sciences de Paris</em> <strong>271</strong> (1970), 824-827.</p>

CC BY-SA 3.0
2017-08-25T13:59:14.607Z
I did not expect that. Thank you for the correction, and for the reference!
qbert
CC BY-SA 3.0
2017-08-24T11:24:20.830Z
2017-08-24T11:24:20.830Z
J.-E. Pin
<p>I consider the Dyck congruence $\equiv$ on a parenthesis alphabet $\Sigma = \{a, \bar a, b, \bar b\}$, i.e. the least congruence on $\Sigma^*$ such that $a \bar a \equiv \varepsilon $ and $b \bar b \equiv \varepsilon$.</p>

<p>It appears that $\equiv$ can be cancelled, i.e. for every $v$, $w_1$, $w_2 \in \Sigma^*$, if $vw_1 \equiv vw_2$, then $w_1 \equiv w_2$ (and analogously for cancellation from the right).</p>

<p>Does someone know a literature reference for this property?  I wasn't able to find anything along those lines.</p>

CC BY-SA 3.0
2017-08-16T14:13:06.803Z
I would check Lyndon and Schupp's [_Combinatorial Group Theory_](http://www.springer.com/us/book/9783540411581), but it's really not hard to prove by induction.
Jeffε
CC BY-SA 3.0
2017-08-16T14:24:49.963Z
You're right. I just wanted to omit the proof. Thank you for the suggestion!
qbert
CC BY-SA 3.0
2017-08-27T06:38:53.323Z
Ah, crap. I thought you meant the usual semigroup conguence.
Jeffε
<co.combinatorics><fl.formal-languages>
Reference: Cancellability of the Dyck congruence
qbert
# Reference: Cancellability of the Dyck congruence

(Asked by: username_0 on 2017-08-15)

I consider the Dyck congruence $\equiv$ on a parenthesis alphabet $\Sigma = \{a, \bar a, b, \bar b\}$, i.e. the least congruence on $\Sigma^\*$ such that $a \bar a \equiv \varepsilon $ and $b \bar b \equiv \varepsilon$.

It appears that $\equiv$ can be cancelled, i.e. for every $v$, $w\_1$, $w\_2 \in \Sigma^\*$, if $vw\_1 \equiv vw\_2$, then $w\_1 \equiv w\_2$ (and analogously for cancellation from the right).

Does someone know a literature reference for this property? I wasn't able to find anything along those lines.

**Tags:** co.combinatorics, fl.formal-languages
> **Comments:**
> **username_1**: I would check Lyndon and Schupp's [_Combinatorial Group Theory_](http://www.springer.com/us/book/9783540411581), but it's really not hard to prove by induction.  
> **username_0**: You're right. I just wanted to omit the proof. Thank you for the suggestion!  
> **username_1**: Ah, crap. I thought you meant the usual semigroup conguence.  

---

## 1 answers

### Answer by username_2 on 2017-08-24. Score: 6 | Accepted answer

Your assertion is wrong, the congruence $\equiv$ is not cancellable from the right: for instance $\bar a a \bar a \equiv \bar a$, but $\bar a a \not\equiv 1$.

By the way the quotient $\Sigma^\*/{\equiv}$ is not a group, but a monoid, called the *polycyclic monoid*, first introduced in [1].

[1] M. Nivat and J-F. Perrot, Une généralisation du monoïde bicyclique, *Comptes Rendus de l'Academie des Sciences de Paris* **271** (1970), 824-827.

> **Comments:**
> **username_0**: I did not expect that. Thank you for the correction, and for the reference!  

---

