A serial-parallel partial order is a partially ordered set constructed of smaller series-parallel partial orders by using two simple join operations [1] [2] .
Sequentially parallel partial orders can be described as N-order-free finite partial orders. They have an maximum of two [1] [3] . These orders include and the relation in oriented trees and oriented parallel-consecutive graphs [2] [3] . Comparability graphs of sequentially parallel partial orders are cographs [2] [4] .
Sequentially parallel partial orders are used in scheduling theory [5] , machine learning of sequences of events in time series of data [6] , transmission sequences of multimedia data [7] and maximizing throughput in data streams [8] .
Sequentially parallel partial orders are also called multi-trees [4] . However, this name is ambiguous - - also called partial orders without four-element suborders (“diamonds”) [9] , as well as other structures formed from several trees.
Definition
Let P and Q be two partially ordered sets. Serial connection of P and Q , P is written ; Q [7] , P * Q [2] , or P ⧀ Q [1] , is a partially ordered set whose elements are a disjoint union of the elements P and Q. In P ; Q , two elements x and y belonging simultaneously to P or Q have the same order relationship that they had in P or Q, respectively. However, for any pair x , y in which x belongs to P and y belongs to Q , there is an additional relation of order x ≤ y defined by the series connection. Serial connection is an associative operation - you can write P ; Q ; R as a series connection of three orders without introducing ambiguity on how to combine them in pairs, since taking in brackets ( P ; Q ); R and P ; ( Q ; R ) describes the same partial order. However, this connection is not a commutative operation , since the permutation of the roles of P and Q will give another partial order in which the order relations for pairs of elements, one of P , the other of Q , are inverted [1] .
Parallel connection of P and Q , written P || Q [7] , P + Q [2] or P ⊕ Q [1] , is determined from a disconnected union of elements P and elements Q in a similar way. If a pair of elements belongs entirely to P or Q , the order remains the same as it was in P or Q, respectively. If an element x belongs to P and an element y belongs to Q , the elements x and y are not comparable. Parallel connection is associative and commutative [1] .
The class of series-parallel partial orders is a set of partial orders that can be constructed from singleton partial orders using these two operations. Equivalently, a class is the smallest set of partial orders, which includes a singleton partial order and which is closed by the operations of serial and parallel connections [1] [2] .
is a sequentially parallel partial order obtained as a result of a sequence of connection operations in which all parallel connection operations are performed first, and then the results of these operations are combined with only sequential operations [2] .
Description of Prohibited Sub-Orders
The partial order N with four elements a , b , c and d and exactly three relations of order a ≤ b ≥ c ≤ d is an example of a or zigzag order]. His Hasse diagram has the form of a capital Latin letter "N". This order is not serial-parallel, since there is no way to break it into sequences of parallel connections of two smaller partial orders. It is said that the partial order P is free from the N-order if there is no set of four elements in P such that the restriction of P to these elements is isomorphic to N in the sense of the partial order. Sequentially parallel partial orders are exactly those nonempty finite N-order free partial orders [1] [2] [3] .
It immediately follows (although this can be proved directly) that any nonempty restriction of a series-parallel partial order is itself a series-parallel partial order [1] .
Ordinal Dimension
partial order P is the minimum size of realizations P , the set of (linearizations) of order P with the property that for any two different elements x and y of order P , x ≤ y holds if and only if x preceded by y in any linear continuation of the implementation.
An alternative definition can be found on the Internet: “The smallest number of linear orders giving a given partially ordered set at the intersection is called its (ordinal dimension)”, for example, in SI Gurov’s lectures [10] or Kuznetsova S.O. [11] .
Sequentially parallel partial orders have a dimension not exceeding two. If P and Q have implementers { L 1 , L 2 } and { L 3 , L 4 }, respectively, then { L 1 L 3 , L 2 L 4 } is an implementor of the serial connection P ; Q , and { L 1 L 3 , L 4 L 2 } is a parallelizer P || Q [2] [3] . A partial order is sequentially parallel if and only if it has an implementer in which one of the two permutations is identical and the second is .
It is known that the partial order P has an ordinal dimension of two if and only if there is a conjugate order Q on the same elements with the property that any two different elements x and y are comparable in exactly one of these orders. In the case of serial-parallel partial orders, the conjugate order, which is itself serial-parallel, can be obtained by performing the sequence of operations of the connection in the same order as for P on the same elements, but instead of serial connection in P , parallel connection is used and vice versa. More strictly, although a partial order can have different conjugate orders, any conjugate order of a series-parallel partial order must also be series-parallel [2] .
Relationship with Graph Theory
Any partial order can be represented (usually not uniquely) by a directed acyclic graph in which there is a path from x to y for all elements of partial order x and y for which x ≤ y . Graphs that represent sequentially parallel partial orders in the described way are called vertex serial-parallel graphs and their transitive contractions (graphs of partial order) are called minimal vertex serial-parallel graphs [3] . Oriented trees and (with one terminal pair) parallel-serial graphs are examples of minimal serial-parallel graphs. Thus, sequentially parallel partial orders can be used to represent reachability relations in oriented trees and parallel graphs [2] [3] .
The partial order comparability graph is an undirected graph with vertices for each element and an undirected edge for each pair of distinct elements x , y if x ≤ y or y ≤ x . That is, it is formed from a minimal series-parallel graph by getting rid of the orientation of the edges. The comparability graph of serial-parallel order is a cograf - sequential and parallel operations of joining parallel order give operations on the comparability graph that form an incoherent union of two subgraphs or connect two subgraphs with all possible edges. These two operations are basic operations in the definition of cographs. Conversely, any cograph is a graph of comparability of series-parallel partial order. If the partial order has a cograph as a graph of comparability, then it must be sequentially parallel partial order, since any other kind of partial order has an N-order that must correspond to a path generated with four vertices in its graph of comparability, and such paths are prohibited in cographs [2] [4] .
Computational complexity
It is possible to use the description of forbidden suborders of series-parallel partial orders as a basis for an algorithm that checks in a time linearly depending on the number of pairs in the relation whether the given binary relation is series-parallel partial order [2] [3] . Alternatively, if the partial order is described as the order of the directed acyclic graph , it is possible to check if it is a series-parallel partial order, and if so, calculate its transitive closure in time proportional to the number of vertices and edges in the transitive closure. The question remains open whether it is possible to improve the recognition time of sequentially parallel orders of reachability linear to the size of the input graph [12] .
If a serial-parallel partial order is represented as an describing the execution of sequential and parallel operations, then partial order elements can be represented by the leaves of the expression tree. Comparison of any two elements can be carried out algorithmically by searching for the smallest common ancestor of the corresponding two leaves. If this ancestor is a parallel connection, the two elements are incomparable, otherwise the order of the serial connections of the operands determines the order of the elements. In this way, a series-parallel partial order of n elements can be represented in the space O ( n ) to determine any value to be compared with the time O (1) [2] .
The task of checking for two given series-parallel partial orders P and Q that P contains a restriction isomorphic to Q is NP-complete [3] .
Although the problem of counting the number of linear extensions of an arbitrary partial order is # P-complete [13] , it can be shown that it can be solved in polynomial time for sequentially parallel partial orders. Namely, if L ( P ) denotes the number of linear extensions of partial order P , then L ( P ; Q ) = L ( P ) L ( Q ) and
- [2] .
Applications
Mannila and Miik [14] used sequentially parallel partial orders as a model of the sequence of events in time series data. They described machine learning algorithms for logical inference models for this type and demonstrated the effectiveness of the algorithms in the development of mandatory course requirements based on the registration data of students, as well as on modeling patterns of using browsers [6] .
Amer et al. [15] argue that sequentially parallel partial orders are convenient for modeling requests for the transmission of multimedia presentations. They used the formula to calculate the number of linear extensions of series-parallel partial order as a basis for the analysis of multimedia transmission algorithms [7] .
Chaudhary et al. [16] used sequentially parallel partial orders to model the dependencies of tasks in the data stream of mass data processing for computer vision . They showed that when using serial-parallel orders for this task, it is possible to efficiently construct an optimal schedule that assigns various tasks to various processors of a parallel computing system in order to optimize system throughput [8] .
The class of orderings, a somewhat more general concept of sequentially parallel partial orders, is defined by PQ trees , data structures used in algorithms to check whether a graph is planar , and to recognize interval graphs [17] . The P node of the PQ tree allows all possible orderings of its heirs like parallel joining in partial orders, while the Q node requires the heirs to follow in a fixed linear order like sequential partial orders. However, unlike sequentially parallel partial orders, PQ-trees allow you to reverse the linear order at any node Q.
Notes
- ↑ 1 2 3 4 5 6 7 8 9 Bechet, De Groote, Retoré, 1997 , p. 230-240.
- ↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Möhring, 1989 , p. 105–194.
- ↑ 1 2 3 4 5 6 7 8 Valdes, Tarjan, Lawler, 1982 , p. 298-313.
- ↑ 1 2 3 Jung, 1978 , p. 125-133.
- ↑ Lawler 1978 , p. 75–90.
- ↑ 1 2 Mannila, Meek, 2000 , p. 161–168.
- ↑ 1 2 3 4 Amer, Chassot, Connolly et al., 1994 , p. 440–456.
- ↑ 1 2 Choudhary, Narahari, Nicol, Simha, 1994 , p. 439-445.
- ↑ Furnas, Zacks, 1994 , p. 330–336.
- ↑ Gurov, 2012 , p. 111 Definition 3.14.
- ↑ Kuznetsov .
- ↑ Ma, Spinrad, 1991 , p. 175-183.
- ↑ Brightwell, Winkler, 1991 , p. 225-242.
- ↑ Mannila, Meek, 2000 .
- ↑ Amer, Chassot, Connolly et al., 1994 .
- ↑ Choudhary, Narahari, Nicol, Simha, 1994 .
- ↑ Booth, Lueker, 1976 , p. 335–379.
Literature
- Bechet D., De Groote P., Retoré C. A complete axiomatization for the inclusion of series-parallel partial orders // Rewriting Techniques and Applications. - Springer-Verlag, 1997. - T. 1232. - S. 230–240. - (Lecture Notes in Computer Science). - DOI : 10.1007 / 3-540-62950-5_74 .
- Möhring RH Computationally tractable classes of ordered sets // Algorithms and Order: Proceedings of the NATO Advanced Study Institute on Algorithms and Order, Ottawa, Canada, May 31-June 13, 1987. - Springer-Verlag, 1989.- T. 255. - S. 105–194. - (NATO Science Series C). - ISBN 978-0-7923-0007-6 .
- Valdes J., Tarjan RE, Lawler EL The recognition of series parallel digraphs // SIAM Journal on Computing . - 1982. - T. 11 , no. 2 . - S. 298-313 . - DOI : 10.1137 / 0211023 .
- Lawler EL Sequencing jobs to minimize total weighted completion time subject to precedence constraints // Annals of Discrete Mathematics. - 1978.- T. 2 . - S. 75–90 . - DOI : 10.1016 / S0167-5060 (08) 70323-6 .
- Jung HA On a class of posets and the corresponding comparability graphs // Journal of Combinatorial Theory , Series B. - 1978.- T. 24 , no. 2 . - S. 125–133 . - DOI : 10.1016 / 0095-8956 (78) 90013-8 .
- Furnas GW, Zacks J. Multitrees: enriching and reusing hierarchical structure // Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94). - 1994. - S. 330–336. - DOI : 10.1145 / 191666.191778 .
- Ma T.-H., Spinrad J. Transitive closure for restricted classes of partial orders // Order. - 1991. - T. 8 , no. 2 . - S. 175–183 . - DOI : 10.1007 / BF00383402 .
- Brightwell GR, Winkler P. Counting linear extensions // Order . - 1991. - T. 8 , no. 3 . - S. 225–242 . - DOI : 10.1007 / BF00383444 .
- Amer PD, Chassot C., Connolly TJ, Diaz M., Conrad P. Partial-order transport service for multimedia and other applications // IEEE / ACM Transactions on Networking. - 1994. - T. 2 , no. 5 . - S. 440–456 . - DOI : 10.1109 / 90.336326 .
- Choudhary AN, Narahari B., Nicol DM, Simha R. Optimal processor assignment for a class of pipelined computations // IEEE Transactions on Parallel and Distributed Systems. - 1994. - T. 5 , no. 4 . - S. 439-445 . - DOI : 10.1109 / 71.273050 .
- Booth KS, Lueker GS Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms // Journal of Computer and System Sciences . - 1976. - T. 13 , no. 3 . - S. 335–379 . - DOI : 10.1016 / S0022-0000 (76) 80045-1 .
- Mannila H. Meek C. Global partial orders from sequential data // Proc. 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2000). - 2000. - S. 161–168. - DOI : 10.1145 / 347090.347122 .
- Kuznetsov S.O. Lattice theory for data mining . (inaccessible link)
- Gurov S.I. Boolean algebras, ordered sets, lattices: definitions, properties, examples . - M .: KRASAND, 2012 .-- ISBN 978-5-396-00456-6 .