Series-parallel partial order
Encyclopedia
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 graph
s. The comparability graph
s of series-parallel partial orders are cograph
s.
Series-parallel partial orders have been applied in 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: multitree
s also refer to partial orders with no four-element diamond suborder and to other structures formed from multiple trees.
of the elements of P and Q. In , 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 in the series composition. Series composition is an associative operation: one can write as the series composition of three orders, without ambiguity about how to combine them pairwise, because both of the parenthesizations and 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, , or , 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.
The class of series-parallel partial orders is the set of partial orders that can be built up from single-element partial orders using these two operations. Equivalently, it is the smallest set of partial orders that includes the single-element partial order and is closed
under the series and parallel composition operations.
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.
or zigzag poset; its Hasse diagram
has the shape of the capital letter "N". It is not series-parallel, 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 N-free if there does not exist a set of four elements in P such that the restriction of P to those elements is order-isomorphic to N. The series-parallel partial orders are exactly the nonempty finite N-free partial orders.
It follows immediately from this (although it can also be proven directly) that any nonempty restriction of a series-parallel partial order is itself a series-parallel partial order.
of a partial order P is the minimum size of a realizer of P, a set of linear extension
s of P with the property that, for every two distinct elements x and y of P, in P if and only if x has an earlier position than y in every linear extension of the realizer. Series-parallel partial orders have order dimension at most two. If P and Q have realizers {L1, L2} and {L3, L4}, respectively, then {L1L3, L2L4} is a realizer of the series composition , and {L1L3, L4L2} is a realizer of the parallel composition P || Q.
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.
The transitive closure
of directed trees and (two-terminal) series parallel graphs are minimal vertex series parallel graphs; therefore, series parallel partial orders may be used to represent reachability relations in directed trees and series parallel graphs.
The comparability graph
of a partial order is the undirected graph with a vertex for each element and an undirected edge for each pair of distinct elements x, y with either or . The comparability graph of a series-partial 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, if a partial order has a cograph as its comparability graph, then it must be a series-parallel partial order, for otherwise its N suborder would correspond to an induced four-vertex path in the comparability graph, and such paths are forbidden in cographs.
order of a directed acyclic graph
, it is possible to test whether it is a series-parallel 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 recognizer series-parallel reachability orders can be improved to be linear in the size of the input graph.
If a series-parallel 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 series-parallel partial order on n elements may be represented in O(n) space with O(1) time to determine any comparison value.
It is NP-complete
to test, for two given series-parallel partial orders P and Q, whether P contains a restriction isomorphic to Q.
Although the problem of counting the number of linear extensions of an arbitrary partial order is #P-complete, it may be solved in polynomial time for series-parallel 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
so the number of linear extensions may be calculated using an expression tree with the same form as the decomposition tree of the given series-parallel order.
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.
argue that series-parallel 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 series-parallel partial order as the basis for analyzing multimedia transmission algorithms.
use series-parallel partial orders to model the task dependencies in a dataflow
model of massive data processing for computer vision
. They show that, by using series-parallel 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.
A class of orderings somewhat more general than series-parallel partial orders is provided by PQ tree
s, data structures that have been applied in algorithms for testing whether a graph is planar
and recognizing interval graph
s. 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 series-parallel partial orders, PQ trees allow the linear ordering of any Q node to be reversed.
Order theory
Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...
mathematics, a series-parallel partial order is a partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
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
Order dimension
In mathematics, the dimension of a partially ordered set is the smallest number of total orders the intersection of which gives rise to the partial order....
at most two. They include weak orders and the reachability
Reachability
In graph theory, reachability is the notion of being able to get from one vertex in a directed graph to some other vertex. Note that reachability in undirected graphs is trivial — it is sufficient to find the connected components in the graph, which can be done in linear time.- Definition :For a...
relationship in directed trees
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
and directed series-parallel graph
Series-parallel graph
In graph theory, series-parallel graphs are graphs with two distinguished vertices called terminals, formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits.-Definition and terminology:...
s. The comparability graph
Comparability graph
In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order...
s of series-parallel partial orders are cograph
Cograph
In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union...
s.
Series-parallel partial orders have been applied in machine learning
Machine learning
Machine learning, a branch of artificial intelligence, is a scientific discipline concerned with the design and development of algorithms that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases...
of event sequencing in time series
Time series
In statistics, signal processing, econometrics and mathematical finance, a time series is a sequence of data points, measured typically at successive times spaced at uniform time intervals. Examples of time series are the daily closing value of the Dow Jones index or the annual flow volume of the...
data, transmission sequencing of multimedia
Multimedia
Multimedia is media and content that uses a combination of different content forms. The term can be used as a noun or as an adjective describing a medium as having multiple content forms. The term is used in contrast to media which use only rudimentary computer display such as text-only, or...
data, and throughput maximization in dataflow programming.
Series-parallel partial orders have also been called multitrees; however, that name is ambiguous: multitree
Multitree
In combinatorics and order-theoretic mathematics, a multitree may describe either of two equivalent structures: a directed acyclic graph in which the set of nodes reachable from any node form a tree, or a partially ordered set that does not have four items a, b, c, and d forming a diamond suborder...
s also refer to partial orders with no four-element diamond suborder 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 , , or ,is the partially ordered set whose elements are the disjoint unionDisjoint union
In mathematics, the term disjoint union may refer to one of two different concepts:* In set theory, a disjoint union is a modified union operation that indexes the elements according to which set they originated in; disjoint sets have no element in common.* In probability theory , a disjoint union...
of the elements of P and Q. In , 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 in the series composition. Series composition is an associative operation: one can write as the series composition of three orders, without ambiguity about how to combine them pairwise, because both of the parenthesizations and 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, , or , 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.
The class of series-parallel partial orders is the set of partial orders that can be built up from single-element partial orders using these two operations. Equivalently, it is the smallest set of partial orders that includes the single-element partial order and is closed
Closure (mathematics)
In mathematics, a set is said to be closed under some operation if performance of that operation on members of the set always produces a unique member of the same set. For example, the real numbers are closed under subtraction, but the natural numbers are not: 3 and 8 are both natural numbers, but...
under the series and parallel composition operations.
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.
Forbidden suborder characterization
The partial order N with the four elements a, b, c, and d and the three order relations is an example of a fenceFence (mathematics)
In mathematics, a fence, also called a zigzag poset, is a partially ordered set in which the order relations form a path with alternating orientations:orA fence may be finite, or it may be formed by an infinite alternating sequence extending in both directions.A linear extension of a fence is...
or zigzag poset; its Hasse diagram
Hasse diagram
In order theory, a branch of mathematics, a Hasse diagram is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction...
has the shape of the capital letter "N". It is not series-parallel, 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 N-free if there does not exist a set of four elements in P such that the restriction of P to those elements is order-isomorphic to N. The series-parallel partial orders are exactly the nonempty finite N-free partial orders.
It follows immediately from this (although it can also be proven directly) that any nonempty restriction of a series-parallel partial order is itself a series-parallel partial order.
Order dimension
The order dimensionOrder dimension
In mathematics, the dimension of a partially ordered set is the smallest number of total orders the intersection of which gives rise to the partial order....
of a partial order P is the minimum size of a realizer of P, a set of linear extension
Linear extension
In order theory, a branch of mathematics, a linear extension of a partial order is a linear order that is compatible with the partial order.-Definitions:...
s of P with the property that, for every two distinct elements x and y of P, in P if and only if x has an earlier position than y in every linear extension of the realizer. Series-parallel partial orders have order dimension at most two. If P and Q have realizers {L1, L2} and {L3, L4}, respectively, then {L1L3, L2L4} is a realizer of the series composition , and {L1L3, L4L2} is a realizer of the parallel composition P || Q.
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.
Connections to graph theory
One may represent a series-parallel partial order by a graph, with a vertex for each element and an edge from x to y whenever x and y are distinct elements of the partial order with . These graphs have been called minimal vertex series parallel graphs.The transitive closure
Transitive closure
In mathematics, the transitive closure of a binary relation R on a set X is the transitive relation R+ on set X such that R+ contains R and R+ is minimal . If the binary relation itself is transitive, then the transitive closure will be that same binary relation; otherwise, the transitive closure...
of directed trees and (two-terminal) series parallel graphs are minimal vertex series parallel graphs; therefore, series parallel partial orders may be used to represent reachability relations in directed trees and series parallel graphs.
The comparability graph
Comparability graph
In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order...
of a partial order is the undirected graph with a vertex for each element and an undirected edge for each pair of distinct elements x, y with either or . The comparability graph of a series-partial order is a cograph
Cograph
In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union...
: 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, if a partial order has a cograph as its comparability graph, then it must be a series-parallel partial order, for otherwise its N suborder would correspond to an induced four-vertex path in the comparability graph, and such paths are forbidden in cographs.
Computational complexity
It is possible to use the forbidden suborder characterization of series-parallel partial orders as a basis for an algorithm that tests whether a given binary relation is a series-parallel partial order, in an amount of time that is linear in the number of related pairs. Alternatively, if a partial order is described as the reachabilityReachability
In graph theory, reachability is the notion of being able to get from one vertex in a directed graph to some other vertex. Note that reachability in undirected graphs is trivial — it is sufficient to find the connected components in the graph, which can be done in linear time.- Definition :For a...
order of a directed acyclic graph
Directed acyclic graph
In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...
, it is possible to test whether it is a series-parallel 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 recognizer series-parallel reachability orders can be improved to be linear in the size of the input graph.
If a series-parallel 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
Lowest common ancestor
The lowest common ancestor is a concept in graph theory and computer science. Let T be a rooted tree with n nodes. The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants .The LCA of v and w in T is the shared ancestor of v...
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 series-parallel partial order on n elements may be represented in O(n) space with O(1) time to determine any comparison value.
It is NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
to test, for two given series-parallel partial orders P and Q, whether P contains a restriction isomorphic to Q.
Although the problem of counting the number of linear extensions of an arbitrary partial order is #P-complete, it may be solved in polynomial time for series-parallel 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
so the number of linear extensions may be calculated using an expression tree with the same form as the decomposition tree of the given series-parallel order.
Applications
use series-parallel partial orders as a model for the sequences of events in time seriesTime series
In statistics, signal processing, econometrics and mathematical finance, a time series is a sequence of data points, measured typically at successive times spaced at uniform time intervals. Examples of time series are the daily closing value of the Dow Jones index or the annual flow volume of the...
data. They describe machine learning
Machine learning
Machine learning, a branch of artificial intelligence, is a scientific discipline concerned with the design and development of algorithms that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases...
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.
argue that series-parallel partial orders are a good fit for modeling the transmission sequencing requirements of multimedia
Multimedia
Multimedia is media and content that uses a combination of different content forms. The term can be used as a noun or as an adjective describing a medium as having multiple content forms. The term is used in contrast to media which use only rudimentary computer display such as text-only, or...
presentations. They use the formula for computing the number of linear extensions of a series-parallel partial order as the basis for analyzing multimedia transmission algorithms.
use series-parallel partial orders to model the task dependencies in a dataflow
Dataflow
Dataflow is a term used in computing, and may have various shades of meaning. It is closely related to message passing.-Software architecture:...
model of massive data processing for computer vision
Computer vision
Computer vision is a field that includes methods for acquiring, processing, analysing, and understanding images and, in general, high-dimensional data from the real world in order to produce numerical or symbolic information, e.g., in the forms of decisions...
. They show that, by using series-parallel orders for this problem, it is possible to efficiently construct an optimized schedule that assigns different tasks to different processors of a parallel computing
Parallel computing
Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
system in order to optimize the throughput of the system.
A class of orderings somewhat more general than series-parallel partial orders is provided by PQ tree
PQ tree
A PQ tree is a tree-based data structure that represents a family of permutations on a set of elements, discovered and named by Kellogg S. Booth and George S. Lueker in 1976. It is a rooted, labeled tree, in which each element is represented by one of the leaf nodes, and each non-leaf node is...
s, data structures that have been applied in algorithms for testing whether a graph is planar
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
and recognizing interval graph
Interval graph
In graph theory, an interval graph is the intersection graph of a multiset of intervals on the real line. It has one vertex for each interval in the set, and an edge between every pair of vertices corresponding to intervals that intersect.-Definition:...
s. 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 series-parallel partial orders, PQ trees allow the linear ordering of any Q node to be reversed.