I am looking for past results on interleaving of heaps (in the sense of Viennot). For a very simplified example, suppose I have two pieces, (b1 a1 b1), and (b2 c2 b2), where the letter represents a resource used and the number represents which piece is being considered. In the classical heaps-of-pieces work by Viennot, the stack of pieces would result in a stack of one on top of the other to give (b1 a1 b1 b2 c2 b2), with height of six pieces. However, an interleaving would give (b1 (a1||b2) (b1 || c2) b2), which would be a height of only four pieces (the "||" notation is meant to indicate simultaneous operations on different resources). Another example would be repeatedly stacking a single piece that is reentrant: (a3, b3, a3). My goal is to find the minimal stacking, considering multiple possible interleavings.
I am not tied to the "heaps-of-pieces" formalism. I am open to using Cartier-Foata monoids, Mazurkiewicz' Theory of Traces, max-plus, timed Petri Nets, or any other formalism that would help me in analyzing such interleaved traces. I am sure there are many applications that would have motivated research on such things before, but perhaps I am just not searching in the right directions with the right keywords.
Any guidance you could provide would be very helpful. Thanks.
