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

Volker Diekert

Transitive Orientations, Möbius Functions, and Complete Semi-Thue Systems for Free Partially Commutative Monoids

Abstract. Let I \subseteq XxX be an independence relation over a finite alphabet X and M=X*/{(ab,ba): (a,b)\in I} the associated free partially commutative monoid. The Möbius function of M is a polynomial in the ring of formal power series Z<<M>>. Taking representatives we may view it as a polynomial in Z<<X*>>. We call it unambiguous if its formal inverse in Z<<X*>> is the characteristic series over a set of representatives of M. The main result states that there is an unambiguous Möbius function of M in Z<<X*>> if and only if there is a transitive orientation of I. It is known that transitive orientations correspond exactly to finite complete semi-Thue systems S \subseteq X*x X* which define M. We obtain a one-to-one correspondence between unambiguous Möbius functions, transitive orientations and finite (normalized) complete semi-Thue systems.

The paper has been finally published under the same title in Automata, languages and programming (Tampere, 1988), pp. 176-187, Lecture Notes in Comput. Sci., 317, Springer, Berlin, 1988.