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

Volker Diekert

Séminaire lotharingien de combinatoire, Tome 19 (1988)

Résumé

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 ZM>>. Taking representatives we may view it as a polynomial in ZX^*>>. We call it unambiguous if its formal inverse in ZX^*>> 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 ZX^*>> 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.