ในคณิตศาสตร์เชิงทฤษฎีลำดับ ลำดับบางส่วนแบบอนุกรม ขนาน คือเซตที่มีลำดับบางส่วนที่สร้างขึ้นจากลำดับบางส่วนแบบอนุกรมขนานที่เล็กกว่าโดยการดำเนินการประกอบแบบง่ายสองอย่าง^{[ 1 ] [ 2 ]}

ลำดับบางส่วนแบบอนุกรมขนานอาจมีลักษณะเฉพาะเป็นลำดับบางส่วนจำกัดแบบ N-free ซึ่งมีมิติลำดับไม่เกินสอง^{[ 1 ] [ 3 ]}ซึ่งรวมถึงลำดับอ่อนและ ความสัมพันธ์ การเข้าถึงในต้นไม้แบบมีทิศทางและกราฟแบบอนุกรมขนานแบบมีทิศทาง^{[ 2 ] [ 3 ]}กราฟเปรียบเทียบของลำดับบางส่วนแบบอนุกรมขนานคือโคกราฟ^{[ 2 ] [ 4 ]}

ลำดับบางส่วนแบบอนุกรม-ขนานได้รับการนำไปใช้ใน การจัดตารางงาน ^{ในโรงงาน [} 5 ] ^{การเรียน}รู้ของเครื่องในการจัดลำดับเหตุการณ์ในข้อมูลอนุกรมเวลา^{[ 6 ]}การจัดลำดับการส่งข้อมูลมัลติมีเดีย^{[ 7 ]}และการเพิ่มปริมาณงานสูงสุดใน การ เขียนโปรแกรมการไหลของข้อมูล^{[ 8 ]}

ลำดับบางส่วนแบบอนุกรมขนานยังถูกเรียกว่ามัลติทรีด้วย^{[ 4 ​​]}อย่างไรก็ตาม ชื่อนี้มีความกำกวม: มัลติทรียังหมายถึงลำดับบางส่วนที่ไม่มีลำดับย่อยรูปเพชรสี่องค์ประกอบ^{[ 9 ]}และโครงสร้างอื่นๆ ที่สร้างขึ้นจากต้นไม้หลายต้น

พิจารณาPและQซึ่งเป็นเซตที่มีลำดับบางส่วนการประกอบอนุกรมของPและQซึ่งเรียกได้หลายแบบว่าผลรวมเชิงลำดับหรือผลรวมเชิงเส้นและเขียนว่าP ; Q , ^{[ 7 ]} P * Q , ^{[ 2 ]}หรือ P ⧀ Q , ^{[ 1 ]}คือเซตที่มีลำดับบางส่วนซึ่งองค์ประกอบเป็นผลรวมที่ไม่ซ้ำกันขององค์ประกอบของPและQในP ; Qองค์ประกอบสองตัวxและyที่ทั้งคู่เป็นของPหรือทั้งคู่เป็นของQจะมีความสัมพันธ์เชิงลำดับเดียวกันกับที่พวกมันมีในPหรือQตามลำดับ อย่างไรก็ตาม สำหรับทุกคู่x , yที่xเป็นของPและyเป็นของQจะมีความสัมพันธ์เชิงลำดับเพิ่มเติมx ≤ yในการประกอบอนุกรม การประกอบอนุกรมเป็นการดำเนินการแบบสมาคม : เราสามารถเขียนP ; Q ; Rเป็นการประกอบอนุกรมของสามลำดับได้โดยไม่มีความกำกวมเกี่ยวกับวิธีการรวมพวกมันเป็นคู่ๆ เนื่องจากวงเล็บทั้งสอง( P ; Q ); RและP ; ( Q ; R )อธิบายลำดับบางส่วนเดียวกัน อย่างไรก็ตาม มันไม่ใช่การดำเนินการสลับที่เพราะการสลับบทบาทของPและQจะทำให้เกิดลำดับบางส่วนที่แตกต่างกัน ซึ่งจะกลับลำดับความสัมพันธ์ของคู่ที่มีองค์ประกอบหนึ่งอยู่ในPและอีกหนึ่งอยู่^ใน Q ^{[ 1} ]

องค์ประกอบคู่ขนานของPและQเขียนว่าP || Q , ^{[ 7 ]} P + Q , ^{[ 2 ]}หรือP ⊕ Q , ^{[ 1 ]}ถูกกำหนดในทำนองเดียวกัน จากการรวมแบบไม่ทับซ้อนกันขององค์ประกอบในPและองค์ประกอบในQโดยที่คู่ขององค์ประกอบที่อยู่ในPหรือQ ทั้งคู่ จะมีลำดับเดียวกันกับที่อยู่ในPหรือQตามลำดับ ในP || Qคู่x , yจะเปรียบเทียบกันไม่ได้เมื่อใดก็ตามที่xอยู่ในPและyอยู่ในQองค์ประกอบคู่ขนานเป็นทั้งแบบสลับที่ได้และแบบเชื่อมโยงได้^{[ 1 ]}

คลาสของลำดับย่อยแบบอนุกรม-ขนานคือเซตของลำดับย่อยที่สามารถสร้างขึ้นจากลำดับย่อยองค์ประกอบเดี่ยวโดยใช้การดำเนินการทั้งสองนี้ หรือเทียบเท่ากับเซตของลำดับย่อยที่เล็กที่สุดที่รวมลำดับย่อยองค์ประกอบเดี่ยวและปิดภายใต้การดำเนินการประกอบแบบอนุกรมและแบบขนาน^{[ 1 ] [ 2 ]}

ลำดับที่อ่อนแอคือลำดับบางส่วนแบบอนุกรมขนานที่ได้จากลำดับของการดำเนินการประกอบซึ่งดำเนินการประกอบแบบขนานทั้งหมดก่อน จากนั้นผลลัพธ์ของการประกอบเหล่านี้จะถูกรวมเข้าด้วยกันโดยใช้การประกอบแบบอนุกรมเท่านั้น^{[ 2 ]}

ลำดับบางส่วนNที่มีองค์ประกอบสี่ตัวคือa , b , cและdและความสัมพันธ์เชิงลำดับสามแบบคือa ≤ b ≥ c ≤ dเป็นตัวอย่างของโพเซตแบบรั้วหรือซิกแซกแผนภาพ Hasse ของมัน มีรูปร่างเหมือนตัวอักษรพิมพ์ใหญ่ "N" มันไม่ใช่แบบอนุกรม-ขนาน เพราะไม่มีวิธีใดที่จะแยกมันออกเป็นการประกอบแบบอนุกรมหรือขนานของลำดับบางส่วนที่เล็กกว่าสองตัว ลำดับบางส่วนPเรียกว่าเป็นอิสระจาก N ถ้าไม่มีเซตขององค์ประกอบสี่ตัวในPที่การจำกัดของPไปยังองค์ประกอบเหล่านั้นมีลำดับที่สมมาตรกับNลำดับบางส่วนแบบอนุกรม-ขนานคือลำดับบางส่วนที่เป็นอิสระจาก N ที่มีค่าจำกัดและไม่ว่างเปล่า^{[ 1 ] [ 2 ] [ 3 ]}

จากสิ่งนี้จึงสรุปได้ทันที (แม้ว่าจะสามารถพิสูจน์ได้โดยตรงเช่นกัน) ว่าข้อจำกัดที่ไม่ว่างเปล่าใดๆ ของลำดับบางส่วนแบบอนุกรมขนานก็เป็นลำดับบางส่วนแบบอนุกรมขนานเช่นกัน^{[ 1 ]}

มิติลำดับของลำดับบางส่วนPคือขนาดขั้นต่ำของตัวสร้างของPซึ่งเป็นเซตของส่วนขยายเชิงเส้นของPที่มีคุณสมบัติว่า สำหรับองค์ประกอบที่แตกต่างกันสองตัวxและyของP , x ≤ yในPก็ต่อเมื่อxมีตำแหน่งก่อนหน้าyในส่วนขยายเชิงเส้นทุกตัวสร้าง ลำดับบางส่วนแบบอนุกรม-ขนานมีมิติลำดับไม่เกินสอง ถ้าPและQมีตัวสร้าง{ L ₁ , L ₂ }และ{ L ₃ , L ₄ }ตามลำดับ แล้ว{ L ₁ L ₃ , L ₂ L ₄ }เป็นตัวสร้างของการประกอบแบบอนุกรมP ; Qและ{ L ₁ L ₃ , L ₄ L ₂ }เป็นตัวสร้างของการประกอบแบบขนานP || Q ^{[ 2 ] [ 3 ]}ลำดับบางส่วนเป็นแบบอนุกรม-ขนานก็ต่อเมื่อมีตัวสร้างซึ่งการเรียงสับเปลี่ยนหนึ่งในสองแบบเป็นเอกลักษณ์และอีกแบบหนึ่งเป็นการเรียงสับเปลี่ยนที่แยกได้

เป็นที่ทราบกันว่าลำดับบางส่วนPมีมิติลำดับสองก็ต่อเมื่อมีลำดับคู่ควบQบนองค์ประกอบเดียวกัน โดยมีคุณสมบัติว่าองค์ประกอบที่แตกต่างกันสองตัวใดๆxและyสามารถเปรียบเทียบได้บนลำดับใดลำดับหนึ่งในสองลำดับนี้เท่านั้น ในกรณีของลำดับบางส่วนแบบอนุกรมขนาน ลำดับคู่ควบที่เป็นอนุกรมขนานนั้นอาจได้รับโดยการดำเนินการประกอบตามลำดับเดียวกับที่กำหนดPบนองค์ประกอบเดียวกัน แต่ดำเนินการประกอบแบบอนุกรมสำหรับการประกอบแบบขนานแต่ละครั้งในการแยกส่วนของPและในทางกลับกัน ยิ่งไปกว่านั้น แม้ว่าลำดับบางส่วนอาจมีคู่ควบที่แตกต่างกันหลายแบบ แต่คู่ควบทุกคู่ของลำดับบางส่วนแบบอนุกรมขนานจะต้องเป็นอนุกรมขนานด้วย^{[ 2 ]}

ลำดับบางส่วนใดๆ อาจถูกแทนด้วย กราฟแบบมีทิศทางที่ไม่มีวงจร (โดยปกติแล้วมากกว่าหนึ่งวิธี) ซึ่งมีเส้นทางจากxไปยังyเมื่อใดก็ตามที่xและyเป็นองค์ประกอบของลำดับบางส่วนที่มีx ≤ yกราฟที่แสดงลำดับบางส่วนแบบอนุกรมขนานในลักษณะนี้เรียกว่ากราฟแบบอนุกรมขนานของจุดยอด และการลด รูปแบบทรานซิทีฟ (กราฟของความสัมพันธ์การครอบคลุมของลำดับบางส่วน) เรียกว่ากราฟแบบอนุกรมขนานของจุดยอดขั้นต่ำ^{[ 3 ]}ต้นไม้แบบมีทิศทางและกราฟแบบอนุกรมขนาน (สองเทอร์มินัล) เป็นตัวอย่างของกราฟแบบอนุกรมขนานของจุดยอดขั้นต่ำ ดังนั้น ลำดับบางส่วนแบบอนุกรมขนานจึงสามารถใช้เพื่อแทนความสัมพันธ์การเข้าถึงได้ในต้นไม้แบบมีทิศทางและกราฟแบบอนุกรมขนาน^{[ 2 ] [ 3 ]}

กราฟเปรียบเทียบของลำดับบางส่วนคือกราฟแบบไม่มีทิศทางที่มีจุดยอดสำหรับแต่ละองค์ประกอบและขอบแบบไม่มีทิศทางสำหรับแต่ละคู่ขององค์ประกอบที่แตกต่างกันx , yโดยที่x ≤ yหรือy ≤ xกล่าวคือ มันถูกสร้างขึ้นจากกราฟอนุกรมขนานที่มีจุดยอดน้อยที่สุดโดยไม่คำนึงถึงทิศทางของแต่ละขอบ กราฟเปรียบเทียบของลำดับบางส่วนแบบอนุกรมขนานคือโคกราฟ : การดำเนินการประกอบแบบอนุกรมและแบบขนานของลำดับบางส่วนก่อให้เกิดการดำเนินการบนกราฟเปรียบเทียบที่สร้างการรวมกันที่ไม่ซ้ำกันของสองกราฟย่อยหรือที่เชื่อมต่อสองกราฟย่อยด้วยขอบที่เป็นไปได้ทั้งหมด การดำเนินการทั้งสองนี้เป็นการดำเนินการพื้นฐานที่ใช้กำหนดโคกราฟ ในทางกลับกัน ทุกโคกราฟคือกราฟเปรียบเทียบของลำดับบางส่วนแบบอนุกรมขนาน ถ้าลำดับบางส่วนมีโคกราฟเป็นกราฟเปรียบเทียบ ลำดับนั้นจะต้องเป็นลำดับบางส่วนแบบอนุกรมขนาน เพราะลำดับบางส่วนประเภทอื่น ๆ ทุกประเภทจะมีลำดับย่อย N ที่จะสอดคล้องกับเส้นทางสี่จุดยอดที่เหนี่ยวนำในกราฟเปรียบเทียบ และเส้นทางดังกล่าวเป็นสิ่งต้องห้ามในโคกราฟ^{[ 2 ] [ 4 ]}

ลักษณะเฉพาะของลำดับย่อยที่ต้องห้ามของลำดับบางส่วนแบบอนุกรม-ขนานสามารถใช้เป็นพื้นฐานสำหรับอัลกอริทึมที่ทดสอบว่าความสัมพันธ์ไบนารีที่กำหนดเป็นลำดับบางส่วนแบบอนุกรม-ขนานหรือไม่ โดยใช้เวลาที่เป็นเชิงเส้นตามจำนวนคู่ที่เกี่ยวข้อง^{[ 2 ] [ 3 ]}หรืออีกทางหนึ่ง หากลำดับบางส่วนถูกอธิบายว่าเป็น ลำดับ การเข้าถึงของกราฟแบบไม่มีวงจรที่มีทิศทางก็สามารถทดสอบได้ว่าเป็นลำดับบางส่วนแบบอนุกรม-ขนานหรือไม่ และถ้าเป็นเช่นนั้น ให้คำนวณการปิดแบบส่งผ่าน โดยใช้เวลาเป็นสัดส่วนกับจำนวนจุดยอดและขอบในการปิดแบบส่งผ่าน ยังคงเปิดอยู่ว่าเวลาในการรับรู้ลำดับการเข้าถึงแบบอนุกรม-ขนานสามารถปรับปรุงให้เป็นเชิงเส้นตามขนาดของกราฟอินพุตได้หรือไม่^{[ 10 ]}

หากลำดับบางส่วนแบบอนุกรม-ขนานถูกแสดงเป็นต้นไม้การแสดงออกที่อธิบายการดำเนินการประกอบแบบอนุกรมและขนานที่ก่อตัวขึ้น องค์ประกอบของลำดับบางส่วนอาจถูกแสดงด้วยใบของต้นไม้การแสดงออก การเปรียบเทียบระหว่างองค์ประกอบสองตัวใดๆ สามารถทำได้โดยใช้อัลกอริทึมโดยการค้นหาบรรพบุรุษร่วมที่ต่ำที่สุดของใบสองใบที่สอดคล้องกัน หากบรรพบุรุษนั้นเป็นการประกอบแบบขนาน องค์ประกอบทั้งสองจะไม่สามารถเปรียบเทียบกันได้ และมิฉะนั้น ลำดับของตัวดำเนินการประกอบแบบอนุกรมจะกำหนดลำดับขององค์ประกอบ ด้วยวิธีนี้ ลำดับบางส่วนแบบอนุกรม-ขนานบน องค์ประกอบ nตัวอาจถูกแสดงใน พื้นที่ O ( n )ด้วย เวลา O (1)ในการกำหนดค่าการเปรียบเทียบใดๆ^{[ 2 ]}

การทดสอบว่าPมีข้อจำกัดที่สมมาตรกับQ สำหรับ ลำดับบางส่วน แบบ อนุกรมขนานสองลำดับที่กำหนด นั้นเป็นปัญหาNP-complete ^{[ 3 ]}

แม้ว่าปัญหาการนับจำนวนส่วนขยายเชิงเส้นของลำดับบางส่วนใดๆ จะเป็นปัญหา#P-completeก็ตาม^{[ 11 ]}แต่อาจแก้ไขได้ในเวลาพหุนามสำหรับลำดับบางส่วนแบบอนุกรม-ขนาน โดยเฉพาะอย่างยิ่ง ถ้าL ( P )แทนจำนวนส่วนขยายเชิงเส้นของลำดับบางส่วนPแล้วL ( P ; Q ) = L ( P ) L ( Q )และ

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

ดังนั้นจำนวนส่วนขยายเชิงเส้นอาจคำนวณได้โดยใช้แผนผังการแสดงออกที่มีรูปแบบเดียวกับแผนผังการแยกส่วนของลำดับอนุกรม-ขนานที่กำหนด^{[ 2 ]}

Mannila & Meek (2000)ใช้ลำดับบางส่วนแบบอนุกรมขนานเป็นแบบจำลองสำหรับลำดับเหตุการณ์ใน ข้อมูล อนุกรมเวลาพวกเขาอธิบาย อัลกอริธึม การเรียนรู้ของเครื่องสำหรับการอนุมานแบบจำลองประเภทนี้ และสาธิตประสิทธิภาพในการอนุมานข้อกำหนดเบื้องต้นของหลักสูตรจากข้อมูลการลงทะเบียนนักเรียนและการสร้างแบบจำลองรูปแบบการใช้งานเว็บเบราว์เซอร์^{[ 6 ]}

Amer et al. (1994)โต้แย้งว่าลำดับย่อยแบบอนุกรม-ขนานนั้นเหมาะสมสำหรับการสร้างแบบจำลองข้อกำหนดลำดับการส่งสัญญาณของ การนำเสนอ มัลติมีเดียพวกเขาใช้สูตรสำหรับการคำนวณจำนวนส่วนขยายเชิงเส้นของลำดับย่อยแบบอนุกรม-ขนานเป็นพื้นฐานสำหรับการวิเคราะห์อัลกอริธึมการส่งสัญญาณมัลติมีเดีย^{[ 7 ]}

Choudhary et al. (1994)ใช้ลำดับบางส่วนแบบอนุกรม-ขนานเพื่อสร้างแบบจำลองการพึ่งพาของงานใน แบบ จำลองการไหลของข้อมูลสำหรับการประมวลผลข้อมูลขนาดใหญ่สำหรับคอมพิวเตอร์วิชั่นพวกเขาแสดงให้เห็นว่า การใช้ลำดับแบบอนุกรม-ขนานสำหรับปัญหานี้ สามารถสร้างตารางเวลาที่เหมาะสมที่สุดได้อย่างมีประสิทธิภาพ โดยกำหนดงานต่างๆ ให้กับโปรเซสเซอร์ต่างๆ ของ ระบบ ประมวลผลแบบขนานเพื่อเพิ่มประสิทธิภาพของปริมาณงานของระบบ^{[ 8 ]}

โครงสร้างข้อมูล PQ treeให้ลำดับประเภทหนึ่งที่ทั่วไปกว่าลำดับบางส่วนแบบอนุกรม-ขนานซึ่งถูกนำมาใช้ในอัลกอริธึมสำหรับการทดสอบว่ากราฟเป็นระนาบ หรือ ไม่ และการจดจำกราฟช่วง^{[ 12 ]}โหนดPของ PQ tree อนุญาตให้มีการเรียงลำดับที่เป็นไปได้ทั้งหมดของโหนดลูก เช่น การประกอบแบบขนานของลำดับบางส่วน ในขณะที่ โหนด Qกำหนดให้โหนดลูกต้องอยู่ในลำดับเชิงเส้นที่กำหนดไว้ เช่น การประกอบแบบอนุกรมของลำดับบางส่วน อย่างไรก็ตาม ต่างจากลำดับบางส่วนแบบอนุกรม-ขนาน PQ tree อนุญาตให้ลำดับเชิงเส้นของ โหนด Q ใดๆ สามารถกลับด้านได้

• วงจรอนุกรมและวงจรขนาน