직렬-병렬 부분 순서

Series-parallel partial order
Hasse 다이어그램으로 표시되는 직렬 병렬 부분 순서입니다.

순서론 수학에서, 직렬 병렬 부분 순서는 두 개의 간단한 합성 [1][2]연산에 의해 더 작은 직렬 병렬 부분 순서로 구성된 부분 순서 집합입니다.

직렬 병렬 부분 순서는 N-자유 유한 부분 순서로 특징지을 수 있으며, 순서 치수는 최대 [1][3]2개입니다.여기에는 유향 트리 및 유향 직렬-병렬 [2][3]그래프에서 약한 순서와 도달 가능성 관계가 포함된다.직렬-병렬 부분 차수의 비교 가능성 그래프는 코그래프입니다.[2][4]

직렬 병렬 부분 순서는 Job shop 스케줄링,[5] 시계열 [6]데이터의 이벤트 시퀀싱 머신 러닝, 멀티미디어 [7]데이터의 전송 시퀀스 및 데이터 흐름 [8]프로그래밍의 throughput 최대화에 적용되었습니다.

직렬 병렬 부분 순서는 멀티 [4]트리라고도 불리지만, 이 이름은 모호합니다. 멀티 트리는 또한 4요소 다이아몬드[9] 하위 순서가 없는 부분 순서 및 여러 트리로 구성된 기타 구조를 나타냅니다.

정의.

부분 순서 집합인 P와 Q를 생각해 보겠습니다.P와 Q의 직렬 구성은 P; Q,[7] P * [2]Q 또는 P q [1]Q로 표기되며, P와 Q의 요소가 분리된 결합인 부분 순서 집합이다.P;Q에서 P에 속하거나 Q에 속하는 2개의 원소 x와 y는 각각 P 또는 Q와 같은 순서 관계를 가진다.단, x가 P에 속하고 y가 Q에 속하는 쌍 x, y마다 계열 구성에는 추가 순서 관계 xθy가 있다.직렬 구성은 연관 연산입니다. 두 괄호(P; Q); R 및 P; (Q; R)는 모두 동일한 부분 순서를 나타내기 때문에 P; Q; R을 쌍으로 결합하는 방법에 대한 모호함 없이 3개의 순서의 직렬 구성으로 쓸 수 있습니다.단, P와 Q의 역할을 바꾸면 P와 [1]Q의 각 요소와의 쌍의 순서 관계가 반전되는 다른 부분 순서가 생성되기 때문에 교환 연산은 아닙니다.

P와 Q의 병렬구성(P Q,[7] P + [2]Q, 또는 P ,[1] Q)은 P와 Q의 요소가 분리되는 것부터 마찬가지로 정의되며 P에 속하거나 Q에 모두 속하는 요소의 쌍은 각각 P 또는 Q와 같은 순서로 정의됩니다.P Q에서 쌍 x, y는 x가 P에 속하고 y가 Q에 속할 때 비교가 안 된다.병렬 구성은 가환적 동시에 [1]연관성이 있다.

직렬 병렬 부분 순서 클래스는 이러한 두 가지 연산을 사용하여 단일 요소 부분 순서에서 쌓을 수 있는 부분 순서 집합입니다.마찬가지로, 단일 요소 부분 순서를 포함하는 가장 작은 부분 순서 집합이며 직렬 및 병렬 합성 [1][2]연산에 의해 닫힙니다.

약차수는 모든 병렬조성을 먼저 실행하고 다음으로 이들 조성의 결과를 [2]직렬조성만을 사용하여 조합하는 일련의 조성작업에서 얻을 수 있는 직렬평행부분순서이다.

금지된 하위 순서 특성 지정

4개의 요소 a, b, c 및 d와 정확히 3차 관계 a b b c c d d를 갖는 부분 순서 N은 펜스 또는 지그재그 포셋의 예입니다.그 Hasse 다이어그램은 대문자 "N"의 형상을 가지고 있습니다.두 개의 작은 부분 순서의 직렬 또는 병렬 구성으로 분할할 수 없기 때문에 직렬-병렬이 아닙니다.부분차수 P는 P 내에 4개 원소의 세트가 존재하지 않는 경우에는 N이 없는 것으로 하고, 이들 원소에 대한 P의 제한은 N과 동형성이 된다.직렬 병렬 부분 순서는 정확히 비어 있지 않은 유한 N-자유 부분 [1][2][3]순서입니다.

여기서 곧바로(직접 증명할 수도 있지만) 직렬-병렬 부분 순서의 비어 있지 않은 제약은 직렬-병렬 부분 순서 [1]그 자체입니다.

주문차원

부분순서 P의 차수 치수는 P의 리라이저의 최소 크기입니다.P의 2개의 서로 다른 요소 x와 y에 대해 리라이저의 모든 리니어 익스텐션에서 x가 y보다 빠른 위치에 있는 경우에만 P의 x µ y를 갖는 특성을 가진 P의 선형 익스텐션 세트입니다.직렬 병렬 부분 순서는 최대 2개의 순서 차원을 가집니다.이 시리즈 구성 P의 만약 P와 Qrealizers{L1, L2}과{L3, L4}, 각각,{L1L3, L2L4}는 실현하는 사람, Q, 그리고 만일 그것은 2개의 순열의 정체성과 다른 하나는 분리된 실현하는 사람 가지고 있는 부분 순서 직병렬은 병렬 구성 PQ.[2][3]의{L1L3, L4L2}는 실현하는 사람. 순열.

부분순서 P는 동일한 원소에 공역순서 Q가 존재하는 경우에만 순서치수 2를 갖는 것으로 알려져 있으며, 두 개의 서로 다른 원소 x와 y는 정확히 이 두 가지 순서 중 하나에 대해 동등하다.직렬 병렬 부분 차수의 경우, 동일 원소상에서 P를 정의하는 순서와 같은 순서로 일련의 합성 연산을 실시하지만, P의 분해에서는 병렬 구성별로 직렬 구성을 실시함으로써 그 자체가 직렬 병렬인 켤레 순서를 얻을 수 있다.보다 강하게는, 부분 차수가 많은 다른 켤레를 가질 수 있지만, 직렬 병렬 부분 차수의 모든 켤레는 직렬 [2]병렬이어야 합니다.

그래프 이론과의 연관성

임의의 부분순서는 (보통 여러 가지 방법으로) x와 y가 x µ y의 부분순서 요소일 때마다 x에서 y까지의 경로가 있는 방향성 비순환 그래프로 나타낼 수 있다.이러한 방식으로 직렬-병렬 부분 순서를 나타내는 그래프를 정점 직렬 병렬 그래프라고 하며, 이러한 추이적 감소(부분 순서의 포함 관계 그래프)를 최소 정점 직렬 병렬 [3]그래프라고 합니다.유향 트리 및 (2단자) 직렬 병렬 그래프는 최소 정점 직렬 병렬 그래프의 예입니다. 따라서 유향 트리 및 직렬 병렬 [2][3]그래프에서 도달 가능성 관계를 나타내기 위해 직렬 병렬 부분 순서를 사용할 수 있습니다.

부분 순서의 비교 가능성 그래프는 각 요소에 대한 정점과 각 개별 요소 쌍 x, y에 대해 x x y 또는 y x x를 갖는 무방향 에지를 가진 그래프입니다.즉, 각 모서리의 방향을 잊어버림으로써 최소 정점 직렬 병렬 그래프로 구성됩니다.직렬 병렬 부분 순서의 비교 가능성 그래프는 코그래프입니다. 부분 순서의 직렬 및 병렬 구성 연산은 비교 가능성 그래프에서 두 개의 하위 그래프의 분리된 결합을 형성하거나 가능한 모든 가장자리로 두 개의 하위 그래프를 연결하는 연산을 생성합니다. 이 두 개의 연산은 c의 기본 연산입니다.ographs가 정의되어 있습니다.반대로, 모든 코그래프는 직렬-병렬 부분 순서의 비교 가능성 그래프입니다.부분순서가 비교가능성 그래프로서 코그래프를 갖는 경우, 그것은 직렬-병렬 부분순서여야 한다. 왜냐하면 다른 모든 종류의 부분순서는 비교가능성 그래프에서 유도된 4개의 버텍스 경로에 대응하는 N개의 서브오더를 가지며, 이러한 경로는 코그래프에서는 [2][4]금지되기 때문이다.

계산의 복잡성

직렬-병렬 부분 순서의 금지된 하위 순서 특성은 특정 이진 관계가 직렬-병렬 부분 순서인지 여부를 관련 쌍 [2][3]수에서 선형인 시간 동안 테스트하는 알고리즘의 기초로 사용할 수 있습니다.또는 부분 순서가 유도 비순환 그래프의 도달 가능성 순서로 설명되는 경우, 연속 병렬 부분 순서인지 여부를 테스트할 수 있으며, 그렇다면 전이 폐쇄의 정점과 모서리 수에 비례하는 시간에 전이 폐쇄를 계산할 수 있다. 세리를 인식할 수 있는지 여부는 열린 상태로 남아 있다.s-module 도달 가능성 순서는 입력 [10]그래프의 크기에서 선형으로 개선될 수 있습니다.

직렬-병렬 부분순서가 직렬 및 이를 형성한 병렬 합성 연산을 기술하는 식목으로서 표현되는 경우, 부분순서의 요소는 식목의 잎으로 표현될 수 있다.대응하는 두 잎의 가장 낮은 공통 조상을 탐색함으로써 두 요소 간의 비교를 알고리즘적으로 실행할 수 있다.만약 그 조상이 병렬 조성이면 두 요소는 비교할 수 없고, 그렇지 않으면 직렬 합성 오퍼랜드의 순서가 요소의 순서를 결정한다.이와 같이 n개 요소상의 직렬 병렬 부분 순서를 O(1)시간과 함께 O(n)공간으로 표현하여 임의의 [2]비교값을 결정할 수 있다.

주어진 두 직렬 병렬 부분 순서 P와 Q에 대해 P가 Q와 [3]동형 제약 조건을 포함하는지 여부를 테스트하는 것은 NP-완전입니다.

임의의 부분 순서의 선형 확장 수를 카운트하는 문제는 [11]#P-완전이지만 직렬 병렬 부분 순서의 경우 다항식 시간으로 해결할 수 있습니다.구체적으로 L(P)이 부분 순서 P의 선형 확장 수를 나타낸다면, L(P; Q) = L(P)L(Q) 및

따라서 선형 확장의 수는 주어진 직렬-순서의 [2]분해 트리와 동일한 형태의 식 트리를 사용하여 계산할 수 있습니다.

적용들

Mannila & Meek(2000)는 시계열 데이터의 이벤트 시퀀스의 모델로 직렬 병렬 부분 순서를 사용합니다.이러한 유형의 모델을 추론하기 위한 기계 학습 알고리즘을 설명하고, 학생 등록 데이터에서 과정 필수 조건을 추론하고 웹 브라우저 사용 [6]패턴을 모델링하는 데 효과적입니다.

Amer 외 연구진(1994)은 직렬 병렬 부분 순서가 멀티미디어 프레젠테이션의 전송 시퀀스 처리 요구 사항을 모델링하는 데 적합하다고 주장한다.이들은 멀티미디어 전송 알고리즘을 [7]분석하기 위한 기초로서 직렬 병렬 부분 순서의 선형 확장 수를 계산하는 공식을 사용합니다.

Choudhary et al.(1994)는 컴퓨터 비전을 위한 대규모 데이터 처리의 데이터 흐름 모델에서 작업 종속성을 모델링하기 위해 직렬 병렬 부분 순서를 사용한다.이 문제에 대해 직렬 병렬 순서를 사용함으로써 [8]시스템의 throughput을 최적화하기 위해 병렬 컴퓨팅 시스템의 서로 다른 프로세서에 서로 다른 작업을 할당하는 최적화된 스케줄을 효율적으로 구축할 수 있음을 알 수 있습니다.

그래프가 평면인지 아닌지를 테스트하고 [12]구간 그래프를 인식하기 위한 알고리즘에 적용된 데이터 구조인 PQ 트리에 의해 직렬 병렬 부분 순서보다 다소 일반적인 순서 클래스가 제공된다.PQ 트리의 P 노드는 부분 순서의 병렬 구성처럼 가능한 모든 자식 순서를 허용하는 반면, Q 노드는 부분 순서의 직렬 구성처럼 고정된 선형 순서로 자식 순서를 발생시킬 것을 요구한다.그러나 직렬 병렬 부분 순서와 달리 PQ 트리를 사용하면 Q 노드의 선형 순서가 반전됩니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b c d e f g h i 를 클릭합니다Bechet, Denis; De Groote, Philippe; Retoré, Christian (1997), "A complete axiomatisation for the inclusion of series-parallel partial orders", Rewriting Techniques and Applications, Lecture Notes in Computer Science, vol. 1232, Springer-Verlag, pp. 230–240, doi:10.1007/3-540-62950-5_74.
  2. ^ 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 Rival, Ivan (ed.), Algorithms and Order: Proceedings of the NATO Advanced Study Institute on Algorithms and Order, Ottawa, Canada, May 31-June 13, 1987, NATO Science Series C, vol. 255, Springer-Verlag, pp. 105–194, ISBN 978-0-7923-0007-6.
  3. ^ a b c d e f g h 를 클릭합니다Valdes, Jacobo; Tarjan, Robert E.; Lawler, Eugene L. (1982), "The recognition of series parallel digraphs", SIAM Journal on Computing, 11 (2): 298–313, doi:10.1137/0211023.
  4. ^ a b c 를 클릭합니다Jung, H. A. (1978), "On a class of posets and the corresponding comparability graphs", Journal of Combinatorial Theory, Series B, 24 (2): 125–133, doi:10.1016/0095-8956(78)90013-8, MR 0491356.
  5. ^ 를 클릭합니다Lawler, Eugene L. (1978), "Sequencing jobs to minimize total weighted completion time subject to precedence constraints", Annals of Discrete Mathematics, 2: 75–90, doi:10.1016/S0167-5060(08)70323-6, ISBN 9780720410433, MR 0495156.
  6. ^ a b 를 클릭합니다Mannila, Heikki; Meek, Christopher (2000), "Global partial orders from sequential data", Proc. 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2000), pp. 161–168, doi:10.1145/347090.347122, S2CID 14735932.
  7. ^ a b c d 를 클릭합니다Amer, Paul D.; Chassot, Christophe; Connolly, Thomas J.; Diaz, Michel; Conrad, Phillip (1994), "Partial-order transport service for multimedia and other applications", IEEE/ACM Transactions on Networking, 2 (5): 440–456, doi:10.1109/90.336326, S2CID 1974607.
  8. ^ 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, doi:10.1109/71.273050.
  9. ^ 를 클릭합니다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, doi:10.1145/191666.191778, S2CID 18710118.
  10. ^ 를 클릭합니다Ma, Tze-Heng; Spinrad, Jeremy (1991), "Transitive closure for restricted classes of partial orders", Order, 8 (2): 175–183, doi:10.1007/BF00383402, S2CID 120935610.
  11. ^ 를 클릭합니다Brightwell, Graham R.; Winkler, Peter (1991), "Counting linear extensions", Order, 8 (3): 225–242, doi:10.1007/BF00383444, S2CID 119697949.
  12. ^ 를 클릭합니다Booth, Kellogg S.; Lueker, George S. (1976), "Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms", Journal of Computer and System Sciences, 13 (3): 335–379, doi:10.1016/S0022-0000(76)80045-1.