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. The parallel composition of P and Q, written P Q, P + Q, or P ⊕ Q, is defined similarly, from the disjoint union of the elements in P and the elements in Q, with pairs of elements that both belong to P or both to Q having the same order as they do in P or Q respectively.