In ordertheoretic mathematics, a seriesparallel partial order is a partially ordered set built up from smaller seriesparallel partial orders by two simple composition operations.^{[1]}^{[2]}
The seriesparallel partial orders may be characterized as the Nfree finite partial orders; they have order dimension at most two.^{[1]}^{[3]} They include weak orders and the reachability relationship in directed trees and directed seriesparallel graphs.^{[2]}^{[3]} The comparability graphs of seriesparallel partial orders are cographs.^{[2]}^{[4]}
Seriesparallel partial orders have been applied in job shop scheduling,^{[5]} machine learning of event sequencing in time series data,^{[6]} transmission sequencing of multimedia data,^{[7]} and throughput maximization in dataflow programming.^{[8]}
Seriesparallel partial orders have also been called multitrees;^{[4]} however, that name is ambiguous: multitrees also refer to partial orders with no fourelement diamond suborder^{[9]} and to other structures formed from multiple trees.
Definition
Consider P and Q, two partially ordered sets. The series composition of P and Q, written P; Q,^{[7]} P * Q,^{[2]} or P ⧀ Q,^{[1]}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.^{[1]}
The parallel composition of P and Q, written P  Q,^{[7]} P + Q,^{[2]} or P ⊕ Q,^{[1]} 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. In P  Q, a pair x, y is incomparable whenever x belongs to P and y belongs to Q. Parallel composition is both commutative and associative.^{[1]}
The class of seriesparallel partial orders is the set of partial orders that can be built up from singleelement partial orders using these two operations. Equivalently, it is the smallest set of partial orders that includes the singleelement partial order and is closed under the series and parallel composition operations.^{[1]}^{[2]}
A weak order is the series parallel partial order obtained from a sequence of composition operations in which all of the parallel compositions are performed first, and then the results of these compositions are combined using only series compositions.^{[2]}
Forbidden suborder characterization
The partial order N with the four elements a, b, c, and d and exactly the three order relations a ≤ b ≥ c ≤ d is an example of a fence or zigzag poset; its Hasse diagram has the shape of the capital letter "N". It is not seriesparallel, because there is no way of splitting it into the series or parallel composition of two smaller partial orders. A partial order P is said to be Nfree if there does not exist a set of four elements in P such that the restriction of P to those elements is orderisomorphic to N. The seriesparallel partial orders are exactly the nonempty finite Nfree partial orders.^{[1]}^{[2]}^{[3]}
It follows immediately from this (although it can also be proven directly) that any nonempty restriction of a seriesparallel partial order is itself a seriesparallel partial order.^{[1]}
Order dimension
The order dimension of a partial order P is the minimum size of a realizer of P, a set of linear extensions of P with the property that, for every two distinct elements x and y of P, x ≤ y in P if and only if x has an earlier position than y in every linear extension of the realizer. Seriesparallel partial orders have order dimension at most two. If P and Q have realizers {L_{1}, L_{2}} and {L_{3}, L_{4}}, respectively, then {L_{1}L_{3}, L_{2}L_{4}} is a realizer of the series composition P; Q, and {L_{1}L_{3}, L_{4}L_{2}} is a realizer of the parallel composition P  Q.^{[2]}^{[3]} A partial order is seriesparallel if and only if it has a realizer in which one of the two permutations is the identity and the other is a separable permutation.
It is known that a partial order P has order dimension two if and only if there exists a conjugate order Q on the same elements, with the property that any two distinct elements x and y are comparable on exactly one of these two orders. In the case of series parallel partial orders, a conjugate order that is itself series parallel may be obtained by performing a sequence of composition operations in the same order as the ones defining P on the same elements, but performing a series composition for each parallel composition in the decomposition of P and vice versa. More strongly, although a partial order may have many different conjugates, every conjugate of a series parallel partial order must itself be series parallel.^{[2]}
Connections to graph theory
Any partial order may be represented (usually in more than one way) by a directed acyclic graph in which there is a path from x to y whenever x and y are elements of the partial order with x ≤ y. The graphs that represent seriesparallel partial orders in this way have been called vertex series parallel graphs, and their transitive reductions (the graphs of the covering relations of the partial order) are called minimal vertex series parallel graphs.^{[3]} Directed trees and (twoterminal) series parallel graphs are examples of minimal vertex series parallel graphs; therefore, series parallel partial orders may be used to represent reachability relations in directed trees and series parallel graphs.^{[2]}^{[3]}
The orientation of each edge. The comparability graph of a seriespartial order is a cograph: the series and parallel composition operations of the partial order give rise to operations on the comparability graph that form the disjoint union of two subgraphs or that connect two subgraphs by all possible edges; these two operations are the basic operations from which cographs are defined. Conversely, every cograph is the comparability graph of a seriesparallel partial order. If a partial order has a cograph as its comparability graph, then it must be a seriesparallel partial order, because every other kind of partial order has an N suborder that would correspond to an induced fourvertex path in its comparability graph, and such paths are forbidden in cographs.^{[2]}^{[4]}
Computational complexity
It is possible to use the forbidden suborder characterization of seriesparallel partial orders as a basis for an algorithm that tests whether a given binary relation is a seriesparallel partial order, in an amount of time that is linear in the number of related pairs.^{[2]}^{[3]} Alternatively, if a partial order is described as the reachability order of a directed acyclic graph, it is possible to test whether it is a seriesparallel partial order, and if so compute its transitive closure, in time proportional to the number of vertices and edges in the transitive closure; it remains open whether the time to recognize seriesparallel reachability orders can be improved to be linear in the size of the input graph.^{[10]}
If a seriesparallel partial order is represented as an expression tree describing the series and parallel composition operations that formed it, then the elements of the partial order may be represented by the leaves of the expression tree. A comparison between any two elements may be performed algorithmically by searching for the lowest common ancestor of the corresponding two leaves; if that ancestor is a parallel composition, the two elements are incomparable, and otherwise the order of the series composition operands determines the order of the elements. In this way, a seriesparallel partial order on n elements may be represented in O(n) space with O(1) time to determine any comparison value.^{[2]}
It is NPcomplete to test, for two given seriesparallel partial orders P and Q, whether P contains a restriction isomorphic to Q.^{[3]}
Although the problem of counting the number of linear extensions of an arbitrary partial order is #Pcomplete,^{[11]} it may be solved in polynomial time for seriesparallel partial orders. Specifically, if L(P) denotes the number of linear extensions of a partial order P, then L(P; Q) = L(P)L(Q) and

L(PQ)=\frac{(P+Q)!}{P!Q!} L(P)L(Q),
so the number of linear extensions may be calculated using an expression tree with the same form as the decomposition tree of the given seriesparallel order.^{[2]}
Applications
Mannila & Meek (2000) use seriesparallel partial orders as a model for the sequences of events in time series data. They describe machine learning algorithms for inferring models of this type, and demonstrate its effectiveness at inferring course prerequisites from student enrollment data and at modeling web browser usage patterns.^{[6]}
Amer et al. (1994) argue that seriesparallel partial orders are a good fit for modeling the transmission sequencing requirements of multimedia presentations. They use the formula for computing the number of linear extensions of a seriesparallel partial order as the basis for analyzing multimedia transmission algorithms.^{[7]}
Choudhary et al. (1994) use seriesparallel partial orders to model the task dependencies in a dataflow model of massive data processing for computer vision. They show that, by using seriesparallel orders for this problem, it is possible to efficiently construct an optimized schedule that assigns different tasks to different processors of a parallel computing system in order to optimize the throughput of the system.^{[8]}
A class of orderings somewhat more general than seriesparallel partial orders is provided by PQ trees, data structures that have been applied in algorithms for testing whether a graph is planar and recognizing interval graphs.^{[12]} A P node of a PQ tree allows all possible orderings of its children, like a parallel composition of partial orders, while a Q node requires the children to occur in a fixed linear ordering, like a series composition of partial orders. However, unlike seriesparallel partial orders, PQ trees allow the linear ordering of any Q node to be reversed.
See also
References

^ ^{a} ^{b} ^{c} ^{d} ^{e} ^{f} ^{g} ^{h} ^{i} Bechet, Denis; De Groote, Philippe; Retoré, Christian (1997), "A complete axiomatisation for the inclusion of seriesparallel partial orders", Rewriting Techniques and Applications, Lecture Notes in Computer Science 1232, SpringerVerlag, pp. 230–240, .

^ ^{}a ^{b} ^{c} ^{d} ^{e} ^{f} ^{g} ^{h} ^{i} ^{j} ^{k} ^{l} ^{m} ^{n} ^{o} Möhring, Rolf H. (1989), "Computationally tractable classes of ordered sets", in .

^ ^{}a ^{b} ^{c} ^{d} ^{e} ^{f} ^{g} ^{h} Valdes, Jacobo; .

^ ^{}a ^{b} ^{c} Jung, H. A. (1978), "On a class of posets and the corresponding comparability graphs", .

^ .

^ ^{}a ^{b} .

^ ^{}a ^{b} ^{c} ^{d} Amer, Paul D.; Chassot, Christophe; Connolly, Thomas J.; Diaz, Michel; Conrad, Phillip (1994), "Partialorder transport service for multimedia and other applications", IEEE/ACM Transactions on Networking 2 (5): 440–456, .

^ ^{}a ^{b} Choudhary, A. N.; Narahari, B.; Nicol, D. M.; Simha, R. (1994), "Optimal processor assignment for a class of pipelined computations", IEEE Transactions on Parallel and Distributed Systems 5 (4): 439–445, .

^ Furnas, George W.; Zacks, Jeff (1994), "Multitrees: enriching and reusing hierarchical structure", Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94), pp. 330–336, .

^ Ma, TzeHeng; Spinrad, Jeremy (1991), "Transitive closure for restricted classes of partial orders", Order 8 (2): 175–183, .

^ Brightwell, Graham R.; .

^ Booth, Kellogg S.; Lueker, George S. (1976), "Testing for the consecutive ones property, interval graphs, and graph planarity using PQtree algorithms", .
This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.