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.