×

Some properties of commutation in free partially commutative monoids. (English) Zbl 0582.20035

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)\).
Reviewer: I.Peák

MSC:

20M05 Free semigroups, generators and relations, word problems
Full Text: DOI

References:

[1] Cori, R.; Perrin, D., Sur la reconnaissabilité dans les monoides partiellement commutatifs libres, Rapport Interne de l’U.E.R. de Bordeaux No. 8404 (1984)
[2] Eilenberg, S., (Automata, Languages and Machines, Vol. A (1974), Academic Press: Academic Press New York/London) · Zbl 0317.94045
[3] Knuth, D. E., The Art of Computer Programming, Vol 1: Fundamental Algorithms, ((1973), Addison-Wesley: Addison-Wesley Reading, MA), 258-265 · Zbl 0191.17903
[4] Lallement, G., Semigroups and combinatorial applications, (Pure and Applied Mathematics (1979), Wiley: Wiley New York) · Zbl 0421.20025
[5] Lentin, A., Equations dans les Monoides Libres (1972), Gauthier-Villars et Mouton: Gauthier-Villars et Mouton Paris-La Haye · Zbl 0258.20058
[6] Lothaire, Combinatorics on Words (1982), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 1001.68093
[7] Ore, O., (Theory of Graphs, Colloquium Publications, Vol. XXXVIII (1962), American Mathematical Society) · Zbl 0105.35401
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.