Möbius functions and confluent semi-commutations (Q685454): Difference between revisions

The paper studies liftings of Möbius functions of free partially commutative monoids. These functions have been of central interest since the beginning of the theory of partial commutativity by \textit{D. Foata} and \textit{P. Cartier} [Problèmes combinatoires de commutation et réarrangements, Lect. Notes Math. 85 (1969)]. The paper shows that their is a canonical one-to-one correspondence between unambiguous liftings and confluent semi-commutations. Thereby it establishes a new bridge from combinatorics on Mazurkiewicz traces to the theory of rewriting systems. The result has been conjectured by the author [Lect. Notes Comput. Sci. 317, 176-187 (1988; Zbl 0707.68049)], but it was solved only when a graph theoretical characterization of the confluence of semi-commutation became available by \textit{V. Diekert}, \textit{E. Ochmanski} and \textit{K. Reinhardt} [On confluent semi-commutation systems -- decidability and complexity results, in: \textit{J. L. Albert}, \textit{B. Monien} and \textit{M. Rodriguez Artalejo}, eds., Lect. Notes Comput. Sci. 510, Springer-Verlag (1991; Zbl 0753.00027)]. The paper concludes with complexity results showing that various decision problems about liftings of Möbius functions are complete for natural complexity classes.