Some properties of commutation in free partially commutative monoids (Q1068945): Difference between revisions

Let A be a finite alphabet, denote by \(\theta\) the commutation relation on A and let \(A^*\) be the free monoid over A. For any \(u,v\in A^*\) let \(u=v| \theta |\) iff there exist \(u_ 1,...,u_ n\in A^*\) such that \(u_ 1=u\), \(u_ n=v\) and for all \(i=1,...,n-1\), \(u_ i=g_ iabd_ i\) and \(u_{i+1}=g_ ibad_ i\) with (a,b)\(\in \theta\) holds. This relation on \(A^*\) is a congruence and the quotient monoid \(M_{\theta}(A)\) is the free partially commutative monoid. The canonical morphism of \(A^*\) onto \(M_{\theta}(A)\) is denoted by f. The author determines the set \(C(u)=\{v\in A^*|\) \(uv=vu| \theta | \}\) for all \(u\in A^*\), which is equivalent to determining the set \(C(m)=\{m'\in M_{\theta}(A)|\) \(mm'=m'm\}\) for every \(m=f(u)\).