scientific article; zbMATH DE number 1047892
Factorials, binomial coefficients, combinatorial functions (05A10) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Connections of semigroups with homological algebra and category theory (20M50) Grammars and rewriting systems (68Q42)
Free partially commutative monoids were first studied by Cartier and Foata from a view point of combinatorics. Mazurkiewicz used such monoids to describe the behavior of concurrent systems, and since then many theoretical computer scientists have studied the subject extensively. An element of a free partially commutative monoid is called a trace and is used to describe a concurrent process. The theory of traces is now a very fruitful field of investigation. In the combinatorial theory of traces the Möbius function plays an important role. Diekert found a relation between the (unambiguous) Möbius functions and the confluence of semi-Thue systems. In this note we study the Möbius functions by means of homological algebra. This study seems to suggest some deep relations among homology, combinatorics and the theory of rewriting systems. For the entire collection see [Zbl 0868.00047].
- Combinatorics on traces
- Möbius inversion formula for the trace group
- Non-commutative extensions of the MacMahon Master Theorem
- Cubical homology and the Leech dimension of free partially commutative monoids
- The homology of partial monoid actions and Petri nets
- scientific article; zbMATH DE number 522832 (Why is no real title available?)
- Commutation and rearrangements. An electronic reedition of the monograph `Problèmes combinatoires de commutation et réarrangements' published by Springer 1969. With three new appendices by D. Foata, B. Lass and Ch. Krattenthaler
- Transitive orientations, Möbius functions, and complete semi-Thue systems for free partially commutative monoids
- Möbius functions and confluent semi-commutations
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4347971)
