Series-parallel partial order

In order-theoretic mathematics, a series-parallel partial order is a partially ordered set built up from smaller series-parallel partial orders by two simple composition operations.

The series-parallel partial orders may be characterized as the N-free finite partial orders; they have order dimension at most two. They include weak orders and the reachability relationship in directed trees and directed series-parallel graphs. The comparability graphs of series-parallel partial orders are cographs.

Series-parallel partial orders have been applied in job shop scheduling,machine learning of event sequencing in time series data, transmission sequencing of multimedia data, and throughput maximization in dataflow programming.

Series-parallel partial orders have also been called multitrees; however, that name is ambiguous: multitrees also refer to partial orders with no four-element diamond suborder and to other structures formed from multiple trees.

Consider P and Q, two partially ordered sets. The series composition of P and Q, written P; Q,P * Q, or P ⧀ Q,is the partially ordered set whose elements are the disjoint union of the elements of P and Q. In P; Q, two elements x and y that both belong to P or that both belong to Q have the same order relation that they do in P or Q respectively. However, for every pair x, y where x belongs to P and y belongs to Q, there is an additional order relation x ≤ y in the series composition. Series composition is an associative operation: one can write P; Q; R as the series composition of three orders, without ambiguity about how to combine them pairwise, because both of the parenthesizations (P; Q); R and P; (Q; R) describe the same partial order. However, it is not a commutative operation, because switching the roles of P and Q will produce a different partial order that reverses the order relations of pairs with one element in P and one in Q.

...
Wikipedia