<p>This is not my area so I may be missing something, but it seems to me that the reason given on Wikipedia is sound in principle (though a proper citation would be good):</p>
<ol>
<li><p>It is, indeed, not particularly difficult to show that trace equivalence has the property
<span class="math-container">$$\forall x,y,w,v\:(w\equiv v\iff xwy\equiv xvy).\tag1$$</span></p>
</li>
<li><p>If <span class="math-container">${\equiv}\let\sset\subseteq\sset\Sigma^*\times\Sigma^*$</span> is an equivalence relation satisfying (1), then there is a language <span class="math-container">$L$</span> whose syntactic congruence is <span class="math-container">$\equiv$</span>, thus <span class="math-container">$\Sigma^*/{\equiv}$</span> is the syntactic monoid of <span class="math-container">$L$</span>.</p>
</li>
</ol>
<p>Proof of 2: If <span class="math-container">$\Sigma^*/{\equiv}$</span> is finite, it is cancellative by (1), hence a group, hence a syntactic monoid of <span class="math-container">$L=\{w:w\equiv\epsilon\}$</span>. Thus, we may assume <span class="math-container">$\equiv$</span> has infinitely many equivalence classes. Using (1), this implies that for every <span class="math-container">$w\in\Sigma^*$</span>, <span class="math-container">$\{xw:x\in\Sigma^*\}$</span> hits infinitely many equivalence classes.</p>
<p>Let <span class="math-container">$\{(w_n,v_n):n\in\omega\}$</span> be an enumeration of <span class="math-container">$(\Sigma^*\times\Sigma^*)\smallsetminus{\equiv}$</span>. We build two increasing sequences <span class="math-container">$L_0^+\sset L_1^+\sset L_2^+\sset\cdots$</span> and <span class="math-container">$L_0^-\sset L_1^-\sset L_2^-\sset\cdots$</span> of finite subsets of <span class="math-container">$\Sigma^*$</span> such that <span class="math-container">$[L_n^+]_\equiv\cap[L_n^-]_\equiv=\varnothing$</span>, where <span class="math-container">$[X]_\equiv$</span> denotes the closure of <span class="math-container">$X$</span> under <span class="math-container">$\equiv$</span>.</p>
<p>If <span class="math-container">$L_n^+$</span> and <span class="math-container">$L_n^-$</span> have already been defined, we construct <span class="math-container">$L_{n+1}^+$</span> and <span class="math-container">$L_{n+1}^-$</span> as follows: since <span class="math-container">$L_n^+\cup L_n^-$</span> is finite, but <span class="math-container">$\{[xw_n]_\equiv:x\in\Sigma^*\}$</span> is infinite, we can find <span class="math-container">$x\in\Sigma^*$</span> such that <span class="math-container">$xw_n\notin[L_n^+\cup L_n^-]_\equiv$</span>. By (1), we have <span class="math-container">$xw_n\not\equiv xv_n$</span>. If <span class="math-container">$xv_n\in[L_n^+]_\equiv$</span>, we put <span class="math-container">$L_{n+1}^+=L_n^+$</span>, <span class="math-container">$L_{n+1}^-=L_n^-\cup\{xw_n\}$</span>; otherwise,
<span class="math-container">\begin{align*}
L_{n+1}^+&amp;=L_n^+\cup\{xw_n\},\\
L_{n+1}^-&amp;=L_n^-\cup\{xv_n\}.
\end{align*}</span></p>
<p>We define <span class="math-container">$L=\bigcup_{n\in\omega}[L_n^+]_\equiv$</span>, and claim that <span class="math-container">$\equiv$</span> is the syntactic congruence of <span class="math-container">$L$</span>. On the one hand, <span class="math-container">$L$</span> is closed under <span class="math-container">$\equiv$</span>, hence
<span class="math-container">\begin{align*}
w\equiv v&amp;\implies\forall x,y\in\Sigma^*\:(xwy\equiv xvy)\\
&amp;\implies\forall x,y\in\Sigma^*\:(xwy\in L\iff xvy\in L)
\end{align*}</span>
using (1). On the other hand, if <span class="math-container">$w\not\equiv v$</span>, then <span class="math-container">$w=w_n$</span> and <span class="math-container">$v=v_n$</span> for some <span class="math-container">$n\in\omega$</span>, thus there is <span class="math-container">$x$</span> such that <span class="math-container">$xw\in[L_{n+1}^+]_\equiv\sset L$</span> and <span class="math-container">$xv\in[L_{n+1}^-]_\equiv\sset\Sigma^*\smallsetminus L$</span>, or vice versa.</p>

CC BY-SA 4.0
2022-04-18T18:28:17.917Z
So every countable cancellative monoid is a syntactic monoid.  I wonder if we can drop the requirement to be countable.
jrwdupl-youtubeyahoocouk
CC BY-SA 4.0
2022-04-15T09:32:16.457Z
2022-04-15T10:45:18.640Z
2022-04-15T10:45:18.640Z
Emil Jeřábek
<p>The answer to the question in the title is 'yes'.  I'd still like to find a published proof, though.  The argument for the result being true given in Wikipedia seems to simply be wrong.</p>
<p>My proof goes as follows, at least for finite alphabets:</p>
<ol>
<li><p>The free monoid on a single symbol is the syntactic module of any non-regular set.  The proof is that there is only one infinite monoid generated by a single element, the free monoid itself.</p>
</li>
<li><p>If M(<em>Σ</em><sub>1</sub>, <em>I</em><sub>1</sub>) has disjunctive set <em>J</em><sub>1</sub> and M(<em>Σ</em><sub>2</sub>, <em>I</em><sub>2</sub>) has disjunctive set <em>J</em><sub>2</sub>, then its direct product M(<em>Σ</em><sub>1</sub>∪<em>Σ</em><sub>2</sub>, <em>I</em><sub>1</sub>∪<em>I</em><sub>2</sub>∪<em>Σ</em><sub>1</sub>⨯<em>Σ</em><sub>2</sub>∪<em>Σ</em><sub>2</sub>⨯<em>Σ</em><sub>1</sub>) has disjunctive set <em>J</em><sub>1</sub>⨯<em>J</em><sub>2</sub>, so the set of trace monoids that are syntactic modules is closed under direct product.  In particular, it includes the commutative trace monoids, which are direct products of the free monoid on a single symbol.</p>
</li>
<li><p>If a trace monoid M(<em>Σ</em>, <em>I</em>) has non-trivial centre Z, it is the direct product of M(<em>Σ</em>\<em>Z</em>, <em>I</em> \ <em>Σ</em>⨯<em>Z</em> \ <em>Z</em>⨯<em>Σ</em>) and M(<em>Σ</em>∩<em>Z</em>, <em>I</em>∩<em>Z</em>⨯<em>Z</em>).  The former has trivial centre and the latter is commutative.</p>
</li>
<li><p>If the centre of a trace monoid M(<em>Σ</em>, <em>I</em>) is trivial, then it has a disjunctive set.  The proof proceeds as in Shyr et al's work, extending the result that a semi-discrete dense subset is a disjunctive set.</p>
</li>
</ol>
<p>The first extension is to Proposition 2.2 of Reis and Shyr's <em>Some properties of disjunctive languages on a free monoid</em>, which appeared on pp334-344 of Inform. Contr. 37, (1978).  The generalisation is:</p>
<p>Proposition: If trace monoid M = M(<em>Σ</em>, <em>I</em>) has trivial centre, then for a monoid morphism <em>ϕ</em> on it, the following are equivalent:
(1) <em>ϕ</em> is faithful;
(2) If <em>u</em> and <em>v</em> are words of the same length and <em>ϕ</em>(<em>u</em>) = <em>ϕ</em>(<em>v</em>) then <em>u</em> = <em>v</em>.</p>
<p>Change to Proof:
Instead of proceeding directly from <em>xwyw</em> = <em>ywxw</em>, I use the projections  π<sub><em>ab</em></sub> for (<em>a</em>, <em>b</em>) in the dependency relation <em>D</em> = <em>Σ</em>⨯<em>Σ</em> - <em>I</em> defined as the monoid morphism with  π<sub><em>ab</em></sub>(a) = a, π<sub><em>ab</em></sub>(b) = b and π<sub><em>ab</em></sub>(z) = 1 for other letters.  Taken collectively, they are a faithful representation of the trace monoid (Cori and Perrin, 1985, Prop. 1.1, in <em>Automates et commutations partielles</em> in RAIRO Inform.Thtor. 19, on pp21-32).  I then use the original arguments to show that for <em>a</em> ≠ <em>b</em>, π<sub><em>ab</em></sub>(x) = π<sub><em>ab</em></sub>(y).  For π<sub><em>aa</em></sub>(x), I use π<sub><em>aa</em></sub>(x) = π<sub><em>a</em></sub>(π<sub><em>ab</em></sub>(x)).  (As <em>M</em> has trivial centre, every letter is a member of a pair (<em>a</em>, <em>b</em>) in <em>D</em> with <em>a</em> ≠ <em>b</em>.)  As this set of projections is faithful, <em>x</em> = <em>y</em>.</p>
<p>The next extension is to Proposition 4.2 in Kunze M., Shyr H.J., Thierrin G., <em>H-Bounded and Semi-discrete Languages</em>, Information and Control 51, 174-187 (1981).
The proposition generalises to, &quot;If L is a dense semi-discrete language of a trace monoid with trivial centre, then L is disjunctive&quot;.  The proof is the same, except that it is no longer immediately obvious that the <em>u</em><sup><em>i</em></sup><em>v</em><sup><em>k-i</em></sup> are distinct.  However, if any were the same, then we have an equation <em>u</em><sup><em>n</em></sup> = <em>v</em><sup><em>n</em></sup>, which by a result of Christine Duboc and |<em>u</em>|=|<em>v</em>|, gives us <em>u</em> = <em>v</em>, contrary to hypothesis.</p>
<p>Finally, we can formally use the same dense semi-discrete language as for the free monoid on the same number of symbols as our disjunctive set if we want it in the trace monoid.  Alternatively, we can take its preimage under the trace monoid's congruence.  The preimage is not semi-discrete, which is how the syntactic monoid can be a trace monoid rather than a free monoid.</p>

CC BY-SA 4.0
2022-04-10T20:44:32.933Z
2022-04-13T19:58:23.437Z
2022-04-13T19:58:23.437Z
jrwdupl-youtubeyahoocouk
<p>There's an assertion on <a href="https://en.wikipedia.org/wiki/Trace%20monoid" rel="nofollow noreferrer">Wikipedia</a> that a trace monoid is a syntactic monoid because <span class="math-container">$x w y \equiv x v y$</span> implies that <span class="math-container">$w \equiv v$</span>.  I don't see how that follows as a consequence, and I can't find any mention of this claim outside of Wikipedia and its copies.</p>
<p>Now, I can find claims and proofs that the free monoids are syntactic monoids.  The relevant language is called a disjunctive set (or disjunctive language), and I have found a recipe for disjunctive sets for a free monoid <span class="math-container">$X^*$</span> (with <span class="math-container">$|X| \geq 2$</span>) - any 'semi-discrete' 'dense' set will serve. <span class="math-container">$L$</span> is 'semi-discrete' if there is a constant bound on the number of its elements of each length, and is 'dense' if the bi-ideal <span class="math-container">$X^* u X^*$</span> meets <span class="math-container">$L$</span> for each string <span class="math-container">$u$</span>.  I haven't found an analogue to this recipe for traces, though it might work if one works with the language in the trace monoid rather than the free monoid - the disjunctive set in the free monoid cannot be semi-discrete for a non-trivial independence relationship.  The proofs for the free monoid case lean heavily on 'primitive' strings (i.e. those that aren't multiple repeats of some other string), and the basic results for them fail heavily for traces.  One might get somewhere with <em>connected</em> traces (those <strong>not</strong> writable as <span class="math-container">$vu=uv$</span>), but I am not sure that such an approach would work.</p>
<p>I have made some slight progress - the direct product of disjunctive sets for different trace monoids is a disjunctive set for the direct product of the trace monoids, so the class of trace monoids that are syntactic monoids is closed under direct product.</p>
<p>I've made some progress in aping Proposition 2.2 of Reis and Shyr's <em>Some properties of disjunctive languages on a free
monoid</em>.  The stumbling block is to show that <span class="math-container">$\forall w \in X^*, xwy=ywx$</span> implies that <span class="math-container">$x$</span> and <span class="math-container">$y$</span> have the same length.   This assertion isn't always true - it fails if <span class="math-container">$y = xz$</span> and <span class="math-container">$z$</span> commutes with everything.  However, if there is a letter that commutes with nothing, and <span class="math-container">$|X| \geq 2$</span>, then it does hold and so dense semi-discrete sets in the trace monoid are disjunctive.  Thus I've now shown that the trace monoid of Unicode strings under canonical equivalence is a syntactic monoid.</p>

<fl.formal-languages>
Are trace monoids always syntactic monoids?
jrwdupl-youtubeyahoocouk
# Are trace monoids always syntactic monoids?

(Asked by: username_0 on 2022-04-08)

There's an assertion on [Wikipedia](https://en.wikipedia.org/wiki/Trace%20monoid) that a trace monoid is a syntactic monoid because $x w y \equiv x v y$ implies that $w \equiv v$. I don't see how that follows as a consequence, and I can't find any mention of this claim outside of Wikipedia and its copies.

Now, I can find claims and proofs that the free monoids are syntactic monoids. The relevant language is called a disjunctive set (or disjunctive language), and I have found a recipe for disjunctive sets for a free monoid $X^\*$ (with $|X| \geq 2$) - any 'semi-discrete' 'dense' set will serve. $L$ is 'semi-discrete' if there is a constant bound on the number of its elements of each length, and is 'dense' if the bi-ideal $X^\* u X^\*$ meets $L$ for each string $u$. I haven't found an analogue to this recipe for traces, though it might work if one works with the language in the trace monoid rather than the free monoid - the disjunctive set in the free monoid cannot be semi-discrete for a non-trivial independence relationship. The proofs for the free monoid case lean heavily on 'primitive' strings (i.e. those that aren't multiple repeats of some other string), and the basic results for them fail heavily for traces. One might get somewhere with *connected* traces (those **not** writable as $vu=uv$), but I am not sure that such an approach would work.

I have made some slight progress - the direct product of disjunctive sets for different trace monoids is a disjunctive set for the direct product of the trace monoids, so the class of trace monoids that are syntactic monoids is closed under direct product.

I've made some progress in aping Proposition 2.2 of Reis and Shyr's *Some properties of disjunctive languages on a free
monoid*. The stumbling block is to show that $\forall w \in X^\*, xwy=ywx$ implies that $x$ and $y$ have the same length. This assertion isn't always true - it fails if $y = xz$ and $z$ commutes with everything. However, if there is a letter that commutes with nothing, and $|X| \geq 2$, then it does hold and so dense semi-discrete sets in the trace monoid are disjunctive. Thus I've now shown that the trace monoid of Unicode strings under canonical equivalence is a syntactic monoid.

**Tags:** fl.formal-languages

---

## 2 answers

### Answer by username_1 on 2022-04-15. Score: 2

This is not my area so I may be missing something, but it seems to me that the reason given on Wikipedia is sound in principle (though a proper citation would be good):

1. It is, indeed, not particularly difficult to show that trace equivalence has the property
   $$\forall x,y,w,v\:(w\equiv v\iff xwy\equiv xvy).\tag1$$
2. If ${\equiv}\let\sset\subseteq\sset\Sigma^\*\times\Sigma^\*$ is an equivalence relation satisfying (1), then there is a language $L$ whose syntactic congruence is $\equiv$, thus $\Sigma^\*/{\equiv}$ is the syntactic monoid of $L$.

Proof of 2: If $\Sigma^\*/{\equiv}$ is finite, it is cancellative by (1), hence a group, hence a syntactic monoid of $L=\{w:w\equiv\epsilon\}$. Thus, we may assume $\equiv$ has infinitely many equivalence classes. Using (1), this implies that for every $w\in\Sigma^\*$, $\{xw:x\in\Sigma^\*\}$ hits infinitely many equivalence classes.

Let $\{(w\_n,v\_n):n\in\omega\}$ be an enumeration of $(\Sigma^\*\times\Sigma^\*)\smallsetminus{\equiv}$. We build two increasing sequences $L\_0^+\sset L\_1^+\sset L\_2^+\sset\cdots$ and $L\_0^-\sset L\_1^-\sset L\_2^-\sset\cdots$ of finite subsets of $\Sigma^\*$ such that $[L\_n^+]\_\equiv\cap[L\_n^-]\_\equiv=\varnothing$, where $[X]\_\equiv$ denotes the closure of $X$ under $\equiv$.

If $L\_n^+$ and $L\_n^-$ have already been defined, we construct $L\_{n+1}^+$ and $L\_{n+1}^-$ as follows: since $L\_n^+\cup L\_n^-$ is finite, but $\{[xw\_n]\_\equiv:x\in\Sigma^\*\}$ is infinite, we can find $x\in\Sigma^\*$ such that $xw\_n\notin[L\_n^+\cup L\_n^-]\_\equiv$. By (1), we have $xw\_n\not\equiv xv\_n$. If $xv\_n\in[L\_n^+]\_\equiv$, we put $L\_{n+1}^+=L\_n^+$, $L\_{n+1}^-=L\_n^-\cup\{xw\_n\}$; otherwise,
\begin{align\*}
L\_{n+1}^+&=L\_n^+\cup\{xw\_n\},\\
L\_{n+1}^-&=L\_n^-\cup\{xv\_n\}.
\end{align\*}

We define $L=\bigcup\_{n\in\omega}[L\_n^+]\_\equiv$, and claim that $\equiv$ is the syntactic congruence of $L$. On the one hand, $L$ is closed under $\equiv$, hence
\begin{align\*}
w\equiv v&\implies\forall x,y\in\Sigma^\*\:(xwy\equiv xvy)\\
&\implies\forall x,y\in\Sigma^\*\:(xwy\in L\iff xvy\in L)
\end{align\*}
using (1). On the other hand, if $w\not\equiv v$, then $w=w\_n$ and $v=v\_n$ for some $n\in\omega$, thus there is $x$ such that $xw\in[L\_{n+1}^+]\_\equiv\sset L$ and $xv\in[L\_{n+1}^-]\_\equiv\sset\Sigma^\*\smallsetminus L$, or vice versa.

> **Comments:**
> **username_0**: So every countable cancellative monoid is a syntactic monoid.  I wonder if we can drop the requirement to be countable.  

---

### Answer by username_0 on 2022-04-10. Score: 1

The answer to the question in the title is 'yes'. I'd still like to find a published proof, though. The argument for the result being true given in Wikipedia seems to simply be wrong.

My proof goes as follows, at least for finite alphabets:

1. The free monoid on a single symbol is the syntactic module of any non-regular set. The proof is that there is only one infinite monoid generated by a single element, the free monoid itself.
2. If M(*Σ*1, *I*1) has disjunctive set *J*1 and M(*Σ*2, *I*2) has disjunctive set *J*2, then its direct product M(*Σ*1∪*Σ*2, *I*1∪*I*2∪*Σ*1⨯*Σ*2∪*Σ*2⨯*Σ*1) has disjunctive set *J*1⨯*J*2, so the set of trace monoids that are syntactic modules is closed under direct product. In particular, it includes the commutative trace monoids, which are direct products of the free monoid on a single symbol.
3. If a trace monoid M(*Σ*, *I*) has non-trivial centre Z, it is the direct product of M(*Σ*\*Z*, *I* \ *Σ*⨯*Z* \ *Z*⨯*Σ*) and M(*Σ*∩*Z*, *I*∩*Z*⨯*Z*). The former has trivial centre and the latter is commutative.
4. If the centre of a trace monoid M(*Σ*, *I*) is trivial, then it has a disjunctive set. The proof proceeds as in Shyr et al's work, extending the result that a semi-discrete dense subset is a disjunctive set.

The first extension is to Proposition 2.2 of Reis and Shyr's *Some properties of disjunctive languages on a free monoid*, which appeared on pp334-344 of Inform. Contr. 37, (1978). The generalisation is:

Proposition: If trace monoid M = M(*Σ*, *I*) has trivial centre, then for a monoid morphism *ϕ* on it, the following are equivalent:
(1) *ϕ* is faithful;
(2) If *u* and *v* are words of the same length and *ϕ*(*u*) = *ϕ*(*v*) then *u* = *v*.

Change to Proof:
Instead of proceeding directly from *xwyw* = *ywxw*, I use the projections π*ab* for (*a*, *b*) in the dependency relation *D* = *Σ*⨯*Σ* - *I* defined as the monoid morphism with π*ab*(a) = a, π*ab*(b) = b and π*ab*(z) = 1 for other letters. Taken collectively, they are a faithful representation of the trace monoid (Cori and Perrin, 1985, Prop. 1.1, in *Automates et commutations partielles* in RAIRO Inform.Thtor. 19, on pp21-32). I then use the original arguments to show that for *a* ≠ *b*, π*ab*(x) = π*ab*(y). For π*aa*(x), I use π*aa*(x) = π*a*(π*ab*(x)). (As *M* has trivial centre, every letter is a member of a pair (*a*, *b*) in *D* with *a* ≠ *b*.) As this set of projections is faithful, *x* = *y*.

The next extension is to Proposition 4.2 in Kunze M., Shyr H.J., Thierrin G., *H-Bounded and Semi-discrete Languages*, Information and Control 51, 174-187 (1981).
The proposition generalises to, "If L is a dense semi-discrete language of a trace monoid with trivial centre, then L is disjunctive". The proof is the same, except that it is no longer immediately obvious that the *u**i**v**k-i* are distinct. However, if any were the same, then we have an equation *u**n* = *v**n*, which by a result of Christine Duboc and |*u*|=|*v*|, gives us *u* = *v*, contrary to hypothesis.

Finally, we can formally use the same dense semi-discrete language as for the free monoid on the same number of symbols as our disjunctive set if we want it in the trace monoid. Alternatively, we can take its preimage under the trace monoid's congruence. The preimage is not semi-discrete, which is how the syntactic monoid can be a trace monoid rather than a free monoid.


---

