#####
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 X*x*X* 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.