Séminaire Lotharingien de Combinatoire, B19b (1988).
[Formerly: Publ. I.R.M.A. Strasbourg, 1988, 361/S-19, p. 5-12.]

Christian Choffrut

A Remark on the Representation of the Free Partial Commutative Monoid

Abstract. We consider free partially commutative monoids, i.e., free monoids where some pairs of letters are allowed to commute. We show that such a monoid can be faithfully represented by 2x2 matrices with integer entries if and only if iit is the direct product of a free commutative monoid with a free product of free commutative monoids.

The paper has been finally published under the title "A remark on the representation of trace monoids" in Semigroup Forum 40 (1990), 143-152.