Talk:Trace monoid

Properties

There is a problem with the current statement of Levi's lemma. It reads

A strong form of Levi's lemma holds for traces. Specifically, if $uv\equiv xy$ for strings u, v, x, y, then there exist strings $z_{1},z_{2},z_{3}$ and $z_{4}$ such that $(z_{2},z_{3})\in I_{D}$, and

$u\equiv z_{1}z_{2}\qquad v=z_{3}z_{4}$

$x\equiv z_{1}z_{3}\qquad y=z_{2}z_{4}$

which cannot be correct, because it implies that u and v have the same length. In particular, when $I_{D}$ is empty, it should say the same thing as the string version of Levi's lemma. Algernon (talk) 14:52, 2 June 2010 (UTC)

@SiamakT: Yes, there is, but it is not what you think it is. The problem is that the article leaves $I_{D}$ as a relationship on the alphabet. Confusingly, some authors extend it to the free monoid on the alphabet and even the trace itself. Without this extension, the condition $(z_{2},z_{3})\in I_{D}$ should be $alph(z_{2})\times alph(z_{3})\subset I_{D}$ where function $alph()$ yields the set of symbols in a word. --RichardW57m (talk) 12:50, 3 February 2022 (UTC)

Given the brevity of the article, I'm inclined to just add a definition of $alph()$ and use that in the condition rather than complicate the concept of the independence relationship. --RichardW57m (talk) 12:50, 3 February 2022 (UTC)

Universal property?

The article currently contains the following sentence: "The trace monoid is universal, in that all homomorphic monoids are in fact isomorphic." This does not seem to be a meaningful mathematical sentence. Does anyone know what was intended by this remark?

See Universal property ? 67.198.37.16 (talk) 03:37, 21 July 2019 (UTC)

This was fixed on 21 November 2019. --RichardW57m (talk) 14:02, 3 February 2022 (UTC)

Concurrent computation

The paragraph in the introduction beginning "Trace monoids are commonly used to model concurrent computation, forming the foundation for process calculi" does not refer to anything in the rest of the artucle and is unsourced. Can anyone expand on this? Deltahedron (talk) 21:58, 13 September 2014 (UTC)

I think the references support this claim, unless you want to argue about how "commonly" this might be, or the degree to which it is "foundational"...? 67.198.37.16 (talk) 03:39, 21 July 2019 (UTC)

As Syntactic Monoids

Are all trace monoids syntactic monoids? The construction for non-commutative free monoids, as the syntactic monoid of the even-length palindromes, fails dramatically for free commutative monoids, as their syntactic monoids are then finite groups! The assertion "Thus, the trace monoid is a syntactic monoid." needs some justification. --RichardW57 (talk) 20:41, 2 April 2022 (UTC)

I've managed to prove that trace monoids are syntactic monoids, but nothing in the proof leads me to summarise as "Thus, the trace monoid is a syntactic monoid." The proof is described on Stack Exchange ([1]), but that is my original research. The direct proof goes:

1. True for the free monoid on a single symbol.
2. True for trace monoids with trivial centre - this generalises a proof for free monoids that uses '(semi-)discrete dense' sets as the disjunctive sets.
3. Get universal coverage by noting that the result holds for direct (not 'free') products of trace monoids for which it holds, and that trace monoids are direct products of free monoids on a single symbol (often multiple copies) and trace monoids with trivial centre. --RichardW57 (talk) 21:53, 10 April 2022 (UTC)

It is, in fact, easy to show that any equivalence relation on $\Sigma ^{*}$ that satisfies $\forall w,v,x,y\,(w\equiv v\leftrightarrow xwy\equiv xvy)$ is a syntactic congruence, hence the reason given on this page is correct (even if lacking a proper citation). See my answer at Stack Exchange.—Emil J. 08:22, 18 April 2022 (UTC)