Are trace monoids always syntactic monoids?

Question

There's an assertion on Wikipedia 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.

Answer 1

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.

Answer 2

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(Σ₁, I₁) has disjunctive set J₁ and M(Σ₂, I₂) has disjunctive set J₂, then its direct product M(Σ₁∪Σ₂, I₁∪I₂∪Σ₁⨯Σ₂∪Σ₂⨯Σ₁) has disjunctive set J₁⨯J₂, 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ⁱv^k-i are distinct. However, if any were the same, then we have an equation uⁿ = vⁿ, 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.