Computing the average parallelism in trace monoids

Daniel Krob, Jean Mairesse, Ioannis Michos

The {\em height} of a trace is the height of the corresponding heap of pieces in Viennot's representation, or equivalently the number of factors in its Cartier-Foata decomposition.…