Möbius functions and confluent semi-commutations
type: Item
instance of: scholarly article
title: Möbius functions and confluent semi-commutations
zbMATH Open document ID: 0777.68052
DOI: 10.1016/0304-3975(93)90229-M
author: Volker Diekert
published in: Theoretical Computer Science
publication date: 1993-12-20T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q42
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D03
zbMATH DE Number: 417376
zbMATH Keywords: Möbius functions
zbMATH Keywords: commutative monoids
zbMATH Keywords: liftings
zbMATH Keywords: confluence
MaRDI profile type: Publication
cites work: Theory of traces
cites work: Combinatorial problems of commutation and rearrangements
cites work: A remark on the representation of trace monoids
cites work: Q3736919
cites work: Q3489462
cites work: Combinatorics on traces
cites work: Q4036566
cites work: Q3328583
cites work: Complete rewriting systems and homology of monoid algebras
cites work: Q4347971
cites work: Graphs and free partially commutative monoids
cites work: Q4347974
cites work: Q3771629
cites work: On lexicographic semi-commutations
cites work: On theories with a combinatorial definition of 'equivalence'
cites work: Q4734770
cites work: Finite canonical rewriting systems for congruences generated by concurrency relations
cites work: Q4035263
cites work: Word problems and a homological finiteness condition for monoids
description: scientific article; zbMATH DE number 417376