Talk:Trace monoid

Latest comment: 2 years ago by EmilJ in topic As Syntactic Monoids

Properties

edit

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   for strings u, v, x, y, then there exist strings   and   such that  , and

 
 

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

@SiamakT: Yes, there is, but it is not what you think it is. The problem is that the article leaves   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   should be   where function   yields the set of symbols in a word. --RichardW57m (talk) 12:50, 3 February 2022 (UTC)Reply

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

Universal property?

edit

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)Reply

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

Concurrent computation

edit

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)Reply

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)Reply

As Syntactic Monoids

edit

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)Reply

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)Reply
It is, in fact, easy to show that any equivalence relation on   that satisfies   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)Reply