The equational theory of pomsets (Q1119012)

A labeled partial order is a partially ordered set together with a labeling of each element (by a symbol from some alphabet). A partially- ordered multiset, or pomset, is an isomorphism class of some labeled partial order. Pomsets have been used as a model of concurrency and as an aid in understanding the semantics of parallel programs The author investigates the axiomatic properties of pomsets, sets of pomsets and ideals of pomsets. He shows, for example, that the equational theory of pomsets under the operations of concatenation, parallel composition and union is finitely axiomatizable. Similar results are obtained for ideals of pomsets.