×

Symmetries of the partial order of traces. (English) Zbl 0954.06013

Free partially commutative monoids, also called trace monoids, were introduced by P. Cartier and D. Foata [Problèmes combinatoires de commutation et réarrangements (Lect. Notes Math. 85) (Springer, Berlin) (1969; Zbl 0186.30101)]. There is a broad research on this topic in theoretical computer science. The main results of the author are the following. If \(G\) is a group, there exists a trace monoid whose partial order has the automorphism group isomorphic to \(G\). In the case of finitely generated trace monoids these groups are profinite and possess only finitely many finite simple decomposition factors. Also the partial order associated with the Rado graph as dependence alphabet does not give rise to a homogeneous domain, which answers an open question of P. Boldi, F. Cardone and N. Sabadini [in: M. Droste et al. (eds.), Semantics of programming languages and model theory (Gordon and Breach Sci. Publ., Yverdon), Algebra Log. Appl. 5, 89-108 (1993; Zbl 0803.68035)].

MSC:

06F05 Ordered semigroups and monoids
20B27 Infinite automorphism groups
20M14 Commutative semigroups
06A07 Combinatorics of partially ordered sets
Full Text: DOI