الترتيب الجزئي المتسلسل المتوازي

في الرياضيات القائمة على نظرية الترتيب ، يُعرف الترتيب الجزئي المتسلسل المتوازي بأنه مجموعة مرتبة جزئياً تتكون من ترتيبات جزئية متسلسلة متوازية أصغر حجماً من خلال عمليتي تركيب بسيطتين. ^{[ 1 ]}^{[ 2 ]}

يمكن وصف الترتيبات الجزئية المتسلسلة المتوازية بأنها ترتيبات جزئية منتهية خالية من N؛ ولها بُعد ترتيبي لا يتجاوز اثنين. ^{[ 1 ]}^{[ 3 ]} وهي تشمل الترتيبات الضعيفة وعلاقة الوصول في الأشجار الموجهة والرسوم البيانية المتسلسلة المتوازية الموجهة . ^{[ 2 ]}^{[ 3 ]} رسوم المقارنة للترتيبات الجزئية المتسلسلة المتوازية هي رسوم بيانية مكملة . ^{[ 2 ]}^{[ 4 ]}

تم تطبيق الترتيبات الجزئية المتسلسلة والمتوازية في جدولة ورش العمل ، ^{[ 5 ]} والتعلم الآلي لتسلسل الأحداث في بيانات السلاسل الزمنية ، ^{[ 6 ]} وتسلسل إرسال بيانات الوسائط المتعددة ، ^{[ 7 ]} وتعظيم الإنتاجية في برمجة تدفق البيانات . ^{[ 8 ]}

وقد أطلق على الترتيبات الجزئية المتوازية المتسلسلة أيضًا اسم الأشجار المتعددة؛ ^{[ 4 ]} ومع ذلك، فإن هذا الاسم غامض: تشير الأشجار المتعددة أيضًا إلى الترتيبات الجزئية التي لا تحتوي على ترتيب فرعي ماسي رباعي العناصر ^{[ 9 ]} وإلى الهياكل الأخرى المتكونة من أشجار متعددة.

تعريف

لنفترض أن لدينا مجموعتين مرتبتين جزئيًا ، $P$ و $Q. يُعرف$ تركيب المتسلسلات لـ P $و$ Q $،$ والذي يُسمى أحيانًا بالمجموع الترتيبي أو المجموع الخطي ، ويُكتب $P$ $;$ $Q$ ، ^[⁷^] $أو P$ $*$ $Q$ ، ^[²^] أو $P$ $⧀$ $Q$ ، ^[¹^]، بأنه المجموعة المرتبة جزئيًا التي تكون عناصرها عبارة عن اتحاد منفصل لعناصر $P$ و $Q.$ في $P$ $;$ $Q$ ، يكون للعنصرين $x$ و $y،$ سواء كانا ينتميان إلى $P$ أو إلى $Q،$ نفس علاقة الترتيب الموجودة في $P$ أو $Q$ على التوالي. مع ذلك، لكل زوج $x$ ، $y$ حيث ينتمي $x$ إلى $P$ و $y$ إلى $Q$ ، توجد علاقة ترتيب إضافية $x$ $\leq$ $y$ في تركيب المتسلسلات. تركيب المتسلسلات عملية تجميعية : يمكن كتابة $P$ $;$ $Q$ $;$ $R$ كتركيب متسلسلات لثلاثة ترتيبات، دون أي لبس حول كيفية دمجها ثنائيًا، لأن كلا التركيبين $($ $P$ $;$ $Q$ $);$ $R$ و $P$ $; ($ $Q$ $;$ $R$ $)$ يصفان نفس الترتيب الجزئي. ومع ذلك، فهي ليست عملية تبديلية ، لأن تبديل أدوار $P$ و $Q$ سينتج عنه ترتيب جزئي مختلف يعكس علاقات الترتيب للأزواج التي تحتوي على عنصر واحد في ^P $وعنصر$ واحد في $Q.$ ^[¹ ]

The parallel composition of $P$ and $Q$ , written $P || Q$ ,^[7] $P + Q$ ,^[2] or $P \oplus 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 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.^[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

الترتيب الجزئي $N$ ذو العناصر الأربعة $a$ و $b$ و $c$ و $d$ ، والذي يحمل تحديدًا علاقات الترتيب الثلاث $a \leq b \geq c \leq d،$ هو مثال على مجموعة جزئية مرتبة متعرجة أو سياجية؛ ويأخذ مخطط هاس الخاص به شكل الحرف "N" الكبير. وهو ليس ترتيبًا متسلسلًا متوازيًا، لأنه لا توجد طريقة لتقسيمه إلى تركيب متسلسل أو متوازي لترتيبين جزئيين أصغر. يُقال إن الترتيب الجزئي $P$ خالٍ من N إذا لم توجد مجموعة من أربعة عناصر في $P$ بحيث يكون تقييد $P$ على تلك العناصر متماثلًا ترتيبيًا مع $N.$ الترتيبات الجزئية المتسلسلة المتوازية هي تحديدًا الترتيبات الجزئية الخالية من N غير الفارغة والمنتهية. ^{[ 1 ]}^{[ 2 ]}^{[ 3 ]}

ويترتب على ذلك مباشرة (على الرغم من أنه يمكن إثبات ذلك بشكل مباشر أيضًا) أن أي تقييد غير فارغ لترتيب جزئي متسلسل-متوازي هو نفسه ترتيب جزئي متسلسل-متوازي. ^{[ 1 ]}

أبعاد الطلب

بُعد الترتيب الجزئي $P$ هو أصغر حجم لمُحقق $P$ ، وهو مجموعة من الامتدادات الخطية لـ $P$ بحيث يكون $x$ $\leq$ $y$ في $P لكل عنصرين مختلفين$ $x$ و $y$ من $P$ ، إذا وفقط إذا كان $x$ يسبق $y$ في أي امتداد خطي للمُحقق. يبلغ بُعد الترتيب للترتيبات الجزئية المتسلسلة المتوازية اثنين على الأكثر. إذا كان للترتيبين $P$ و $Q$ مُحققان هما ${$ $L1$ $,$ $L2$ $}$ $و$ { $L3$ $,$ $L4$ $}$ $على$ $التوالي$ $،$ فإن ${$ $L1$ $,$ $L3$ $,$ $L2$ $,$ $L4$ $}$ يُمثل مُحققًا للتركيب المتسلسل $P$ $||$ $Q$ ، و ${$ $L1$ $,$ $L3$ $,$ $L4$ $,$ $L2$ $}$ يُمثل مُحققًا للتركيب المتوازي $P$ $||$ $Q.$ ^[²^]^[³^] $يكون الترتيب الجزئي متسلسلًا متوازيًا إذا وفقط إذا$ $كان$ له مُحقق يكون فيه أحد التبديلين تبديلًا محايدًا $والآخر$ تبديلًا $قابلًا$ $للفصل$ .

من المعروف أن الترتيب الجزئي $P$ له بُعد ترتيبي ثنائي إذا وفقط إذا وُجد ترتيب مترافق $Q$ على نفس العناصر، بحيث يكون أي عنصرين مختلفين $x$ و $y$ قابلين للمقارنة على أحد هذين الترتيبين فقط. في حالة الترتيبات الجزئية المتوازية المتسلسلة، يمكن الحصول على ترتيب مترافق متسلسلة متوازية بدوره عن طريق إجراء سلسلة من عمليات التركيب بنفس ترتيب العمليات التي تُعرّف $P$ على نفس العناصر، ولكن مع إجراء تركيب متسلسل لكل تركيب متوازٍ في تفكيك $P$ والعكس صحيح. والأهم من ذلك، أنه على الرغم من أن الترتيب الجزئي قد يكون له العديد من المترافقات المختلفة، إلا أن كل مترافق لترتيب جزئي متسلسل متوازي يجب أن يكون متسلسلًا متوازيًا بدوره. ^{[ 2 ]}

الروابط بنظرية الرسم البياني

يمكن تمثيل أي ترتيب جزئي (عادةً بأكثر من طريقة) بواسطة رسم بياني موجه غير دوري، حيث يوجد مسار من $x$ إلى $y$ عندما يكون $x$ و $y$ عنصرين من عناصر الترتيب الجزئي مع $x \leq y$ . تُسمى الرسوم البيانية التي تُمثل الترتيبات الجزئية المتسلسلة المتوازية بهذه الطريقة برسوم بيانية متسلسلة متوازية الرؤوس، وتُسمى اختزالاتها المتعدية (رسوم بيانية لعلاقات التغطية للترتيب الجزئي) برسوم بيانية متسلسلة متوازية الرؤوس الدنيا. ^{[ 3 ]} تُعد الأشجار الموجهة والرسوم البيانية المتسلسلة المتوازية (ذات الطرفين) أمثلة على الرسوم البيانية المتسلسلة المتوازية الرؤوس الدنيا؛ لذلك، يمكن استخدام الترتيبات الجزئية المتسلسلة المتوازية لتمثيل علاقات الوصول في الأشجار الموجهة والرسوم البيانية المتسلسلة المتوازية. ^{[ 2 ]}^{[ 3 ]}

الرسم البياني للمقارنة لترتيب جزئي هو رسم بياني غير موجه ، حيث يمثل كل عنصر رأسًا، ويمثل كل زوج من العناصر المختلفة $x$ و $y$ حافة غير موجهة ، حيث $x \leq y$ أو $y \leq x$ . أي أنه يتكون من رسم بياني متسلسل متوازٍ ذي رؤوس قليلة، مع إغفال اتجاه كل حافة. الرسم البياني للمقارنة لترتيب جزئي متسلسل متوازٍ هو رسم بياني متكامل : إذ تُنتج عمليات التركيب المتسلسل والمتوازي للترتيب الجزئي عمليات على الرسم البياني للمقارنة، تُشكل اتحادًا منفصلًا لرسمين بيانيين فرعيين، أو تربط بين رسمين بيانيين فرعيين بجميع الحواف الممكنة؛ وهاتان العمليتان هما العمليتان الأساسيتان اللتان تُعرّف منهما الرسوم البيانية المتكاملة. وبالعكس، فإن كل رسم بياني متكامل هو الرسم البياني للمقارنة لترتيب جزئي متسلسل متوازٍ. إذا كان الترتيب الجزئي يمتلك مخططًا مكملًا كمخطط مقارنة له، فإنه يجب أن يكون ترتيبًا جزئيًا متسلسلًا متوازيًا، لأن كل نوع آخر من الترتيب الجزئي يحتوي على ترتيب فرعي N يُقابل مسارًا مُستحثًا بأربعة رؤوس في مخطط المقارنة الخاص به، وهذه المسارات ممنوعة في المخططات المكملة. ^{[ 2 ]}^{[ 4 ]}

التعقيد الحسابي

يمكن استخدام توصيف الترتيب الفرعي المحظور للترتيبات الجزئية المتسلسلة المتوازية كأساس لخوارزمية تختبر ما إذا كانت علاقة ثنائية معينة تمثل ترتيبًا جزئيًا متسلسلًا متوازيًا، وذلك في زمن يتناسب خطيًا مع عدد الأزواج المرتبطة. ^{[ 2 ]}^{[ 3 ]} وبدلاً من ذلك، إذا وُصف ترتيب جزئي بأنه ترتيب إمكانية الوصول لرسم بياني موجه غير دوري ، فمن الممكن اختبار ما إذا كان ترتيبًا جزئيًا متسلسلًا متوازيًا، وإذا كان كذلك، حساب إغلاقه المتعدي، في زمن يتناسب مع عدد الرؤوس والحواف في الإغلاق المتعدي؛ ويبقى السؤال مطروحًا حول إمكانية تحسين زمن التعرف على ترتيبات إمكانية الوصول المتسلسلة المتوازية ليصبح خطيًا مع حجم الرسم البياني المُدخل. ^{[ 10 ]}

إذا مُثِّل ترتيب جزئي متسلسل-متوازي بشجرة تعبيرية تصف عمليات التركيب المتسلسل والمتوازي التي شكلته، فيمكن تمثيل عناصر الترتيب الجزئي بأوراق الشجرة التعبيرية. ويمكن إجراء مقارنة بين أي عنصرين خوارزميًا بالبحث عن السلف المشترك الأدنى للورقتين المتناظرتين؛ فإذا كان هذا السلف تركيبًا متوازيًا، يكون العنصران غير قابلين للمقارنة، وإلا فإن ترتيب معاملات التركيب المتسلسل هو الذي يحدد ترتيب العناصر. وبهذه الطريقة، يمكن تمثيل ترتيب جزئي متسلسل-متوازي على $n$ عنصرًا في مساحة $O (n) بزمن$ $O (1)$ لتحديد أي قيمة مقارنة. ^{[ 2 ]}

من الصعب اختبار ^ما إذا كان $P$ يحتوي على تقييد متماثل مع $Q$ بالنسبة لترتيبين جزئيين متوازيين متسلسلين معطيين $P$ و $Q.$ [ ³^]

على الرغم من أن مسألة حساب عدد الامتدادات الخطية لترتيب جزئي عشوائي هي مسألة كاملة من فئة #P ، ^{[ 11 ]} إلا أنه يمكن حلها في وقت متعدد الحدود للترتيبات الجزئية المتسلسلة والمتوازية. تحديدًا، إذا كان $L (P)$ يرمز إلى عدد الامتدادات الخطية لترتيب جزئي $P$ ، فإن $L (P; Q) = L (P) / L (Q)$ و

L(P||Q)={\frac {(|P|+|Q|)!}{|P|!|Q|!}}L(P)L(Q),

لذا يمكن حساب عدد الامتدادات الخطية باستخدام شجرة تعبير لها نفس شكل شجرة التفكيك لترتيب السلسلة والتوازي المعطى. ^{[ 2 ]}

التطبيقات

يستخدم مانيلا وميك (2000) الترتيبات الجزئية المتسلسلة المتوازية كنموذج لتسلسل الأحداث في بيانات السلاسل الزمنية . ويصفان خوارزميات التعلم الآلي لاستنتاج نماذج من هذا النوع، ويوضحان فعاليتها في استنتاج متطلبات المقررات الدراسية من بيانات تسجيل الطلاب وفي نمذجة أنماط استخدام متصفح الويب. ^{[ 6 ]}

يرى عامر وآخرون (1994) أن الترتيبات الجزئية المتسلسلة والمتوازية تُعدّ نموذجًا مناسبًا لمتطلبات تسلسل إرسال عروض الوسائط المتعددة . ويستخدمون صيغة حساب عدد الامتدادات الخطية للترتيب الجزئي المتسلسل والمتوازي كأساس لتحليل خوارزميات إرسال الوسائط المتعددة. ^{[ 7 ]}

استخدم تشودري وآخرون (1994) ترتيبات جزئية متسلسلة-متوازية لنمذجة تبعيات المهام في نموذج تدفق البيانات لمعالجة البيانات الضخمة في مجال رؤية الحاسوب . وقد أظهروا أنه باستخدام الترتيبات المتسلسلة-المتوازية لهذه المشكلة، من الممكن إنشاء جدول زمني مُحسَّن بكفاءة، يُسند مهامًا مختلفة إلى معالجات مختلفة في نظام الحوسبة المتوازية ، وذلك لتحسين إنتاجية النظام. ^{[ 8 ]}

تُقدّم أشجار PQ فئةً من الترتيبات أكثر عموميةً من الترتيبات الجزئية المتسلسلة المتوازية ، وهي هياكل بيانات تُستخدم في خوارزميات اختبار ما إذا كان الرسم البياني مستويًا والتعرف على الرسوم البيانية الفاصلية . ^{[ 12 ]} تسمح عقدة P في شجرة PQ بجميع الترتيبات الممكنة لأبنائها، مثل التركيب المتوازي للترتيبات الجزئية، بينما تتطلب عقدة Q أن تظهر الأبناء بترتيب خطي ثابت، مثل التركيب المتسلسل للترتيبات الجزئية. مع ذلك، وعلى عكس الترتيبات الجزئية المتسلسلة المتوازية، تسمح أشجار PQ بعكس الترتيب الخطي لأي عقدة Q.

انظر أيضاً

الدوائر المتصلة على التوالي والتوازي

مراجع

1 2 3 4 5 6 7 8 9 بيشيه، دينيس؛ دي غروت، فيليب؛ ريتوري، كريستيان (1997)، "صياغة بديهية كاملة لإدراج الترتيبات الجزئية المتسلسلة المتوازية"، تقنيات إعادة الكتابة وتطبيقاتها ، سلسلة محاضرات في علوم الحاسوب، المجلد 1232، سبرينغر-فيرلاغ، الصفحات 230-240 ، doi : 10.1007/3-540-62950-5_74 ، ISBN 978-3-540-62950-4.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 موهرينغ، رولف هـ. (1989)، "فئات المجموعات المرتبة القابلة للمعالجة حسابيًا"، في ريفال، إيفان (محرر)، الخوارزميات والترتيب: وقائع معهد الدراسات المتقدمة التابع لحلف الناتو حول الخوارزميات والترتيب، أوتاوا، كندا، 31 مايو - 13 يونيو 1987 ، سلسلة علوم الناتو ج، المجلد 255، سبرينغر-فيرلاغ، الصفحات 105-194 ، ISBN 978-0-7923-0007-6.
1 2 3 4 5 6 7 8 فالديس، جاكوبو؛ تارجان، روبرت إي .؛ لولر، يوجين إل. (1982)، "التعرف على الرسوم البيانية الموجهة المتوازية المتسلسلة"، مجلة SIAM للحوسبة ، 11 (2): 298-313 ، doi : 10.1137/0211023 .
1 2 3 جونغ، هـ. أ. (1978)، "حول فئة من المجموعات المرتبة جزئيًا ورسوم بيانية للمقارنة المقابلة"، مجلة نظرية التوافيق، السلسلة ب ، 24 (2): 125-133 ، doi : 10.1016/0095-8956(78)90013-8 ، MR 0491356 .
↑ لولر، يوجين ل. (1978)، "ترتيب المهام لتقليل إجمالي وقت الإنجاز المرجح مع مراعاة قيود الأسبقية" (ملف PDF) ، حوليات الرياضيات المتقطعة ، 2 : 75-90 ، doi : 10.1016/S0167-5060(08)70323-6 ، ISBN 9780720410433، MR 0495156 {{citation}}: CS1 maint: work parameter with ISBN ( link ) .
1 2 مانيلا، هيكي ؛ ميك، كريستوفر (2000)، "الترتيبات الجزئية العالمية من البيانات المتسلسلة"، وقائع المؤتمر الدولي السادس لجمعية ACM SIGKDD حول اكتشاف المعرفة واستخراج البيانات (KDD 2000) ، الصفحات 161-168 ، doi : 10.1145/347090.347122 ، ISBN 1-58113-233-6، S2CID 14735932 .
1 2 3 4 عامر، بول د.؛ شاسو، كريستوف؛ كونولي، توماس ج.؛ دياز، ميشيل؛ كونراد، فيليب (1994)، "خدمة نقل جزئية الترتيب للوسائط المتعددة والتطبيقات الأخرى"، معاملات IEEE/ACM في الشبكات ، 2 (5): 440-456 ، Bibcode : 1994ITNet...2..440A ، doi : 10.1109/90.336326 ، S2CID 1974607 .
1 2 تشودري، أ.ن.؛ ناراهاري، ب.؛ نيكول، د.م.؛ سيمها، ر. (1994)، "التخصيص الأمثل للمعالج لفئة من العمليات الحسابية المتسلسلة" ، معاملات IEEE للأنظمة المتوازية والموزعة ، 5 (4): 439-445 ، Bibcode : 1994ITPDS...5..439C ، doi : 10.1109/71.273050 ، S2CID 5588390 .
↑ فورناس، جورج و.؛ زاكس، جيف (1994)، "الأشجار المتعددة: إثراء وإعادة استخدام البنية الهرمية"، وقائع مؤتمر SIGCHI حول العوامل البشرية في أنظمة الحوسبة (CHI '94) ، الصفحات 330-336 ، doi : 10.1145/191666.191778 ، S2CID 18710118 .
↑ ما، تزي-هينغ؛ سبينراد، جيريمي (1991)، "الإغلاق المتعدي لفئات مقيدة من الترتيبات الجزئية"، الترتيب ، 8 (2): 175-183 ، doi : 10.1007/BF00383402 ، S2CID 120935610 .
↑ برايتويل، غراهام ر.؛ وينكلر، بيتر (1991)، "حساب الامتدادات الخطية"، النظام ، 8 (3): 225-242 ، doi : 10.1007/BF00383444 ، S2CID 119697949 .
↑ بوث، كيلوج س.؛ لوكر، جورج س. (1976)، "اختبار خاصية الواحدات المتتالية، والرسوم البيانية الفاصلية، وتسطيح الرسم البياني باستخدام خوارزميات شجرة PQ"، مجلة علوم الحاسوب والنظم ، 13 (3): 335-379 ، doi : 10.1016/S0022-0000(76)80045-1.

[bgr-1] 1 2 3 4 5 6 7 8 9 بيشيه، دينيس؛ دي غروت، فيليب؛ ريتوري، كريستيان (1997)، "صياغة بديهية كاملة لإدراج الترتيبات الجزئية المتسلسلة المتوازية"، تقنيات إعادة الكتابة وتطبيقاتها ، سلسلة محاضرات في علوم الحاسوب، المجلد 1232، سبرينغر-فيرلاغ، الصفحات 230-240 ، doi : 10.1007/3-540-62950-5_74 ، ISBN 978-3-540-62950-4.

[m-2] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 موهرينغ، رولف هـ. (1989)، "فئات المجموعات المرتبة القابلة للمعالجة حسابيًا"، في ريفال، إيفان (محرر)، الخوارزميات والترتيب: وقائع معهد الدراسات المتقدمة التابع لحلف الناتو حول الخوارزميات والترتيب، أوتاوا، كندا، 31 مايو - 13 يونيو 1987 ، سلسلة علوم الناتو ج، المجلد 255، سبرينغر-فيرلاغ، الصفحات 105-194 ، ISBN 978-0-7923-0007-6.

[vtl-3] 1 2 3 4 5 6 7 8 فالديس، جاكوبو؛ تارجان، روبرت إي .؛ لولر، يوجين إل. (1982)، "التعرف على الرسوم البيانية الموجهة المتوازية المتسلسلة"، مجلة SIAM للحوسبة ، 11 (2): 298-313 ، doi : 10.1137/0211023 .

[j-4] 1 2 3 جونغ، هـ. أ. (1978)، "حول فئة من المجموعات المرتبة جزئيًا ورسوم بيانية للمقارنة المقابلة"، مجلة نظرية التوافيق، السلسلة ب ، 24 (2): 125-133 ، doi : 10.1016/0095-8956(78)90013-8 ، MR 0491356 .

[5] لولر، يوجين ل. (1978)، "ترتيب المهام لتقليل إجمالي وقت الإنجاز المرجح مع مراعاة قيود الأسبقية" (ملف PDF) ، حوليات الرياضيات المتقطعة ، 2 : 75-90 ، doi : 10.1016/S0167-5060(08)70323-6 ، ISBN 9780720410433، MR 0495156 {{citation}}: CS1 maint: work parameter with ISBN ( link ) .

[mm-6] 1 2 مانيلا، هيكي ؛ ميك، كريستوفر (2000)، "الترتيبات الجزئية العالمية من البيانات المتسلسلة"، وقائع المؤتمر الدولي السادس لجمعية ACM SIGKDD حول اكتشاف المعرفة واستخراج البيانات (KDD 2000) ، الصفحات 161-168 ، doi : 10.1145/347090.347122 ، ISBN 1-58113-233-6، S2CID 14735932 .

[accdc-7] 1 2 3 4 عامر، بول د.؛ شاسو، كريستوف؛ كونولي، توماس ج.؛ دياز، ميشيل؛ كونراد، فيليب (1994)، "خدمة نقل جزئية الترتيب للوسائط المتعددة والتطبيقات الأخرى"، معاملات IEEE/ACM في الشبكات ، 2 (5): 440-456 ، Bibcode : 1994ITNet...2..440A ، doi : 10.1109/90.336326 ، S2CID 1974607 .

[cnns-8] 1 2 تشودري، أ.ن.؛ ناراهاري، ب.؛ نيكول، د.م.؛ سيمها، ر. (1994)، "التخصيص الأمثل للمعالج لفئة من العمليات الحسابية المتسلسلة" ، معاملات IEEE للأنظمة المتوازية والموزعة ، 5 (4): 439-445 ، Bibcode : 1994ITPDS...5..439C ، doi : 10.1109/71.273050 ، S2CID 5588390 .

[9] فورناس، جورج و.؛ زاكس، جيف (1994)، "الأشجار المتعددة: إثراء وإعادة استخدام البنية الهرمية"، وقائع مؤتمر SIGCHI حول العوامل البشرية في أنظمة الحوسبة (CHI '94) ، الصفحات 330-336 ، doi : 10.1145/191666.191778 ، S2CID 18710118 .

[10] ما، تزي-هينغ؛ سبينراد، جيريمي (1991)، "الإغلاق المتعدي لفئات مقيدة من الترتيبات الجزئية"، الترتيب ، 8 (2): 175-183 ، doi : 10.1007/BF00383402 ، S2CID 120935610 .

[11] برايتويل، غراهام ر.؛ وينكلر، بيتر (1991)، "حساب الامتدادات الخطية"، النظام ، 8 (3): 225-242 ، doi : 10.1007/BF00383444 ، S2CID 119697949 .

[12] بوث، كيلوج س.؛ لوكر، جورج س. (1976)، "اختبار خاصية الواحدات المتتالية، والرسوم البيانية الفاصلية، وتسطيح الرسم البياني باستخدام خوارزميات شجرة PQ"، مجلة علوم الحاسوب والنظم ، 13 (3): 335-379 ، doi : 10.1016/S0022-0000(76)80045-1.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]