Serieparallell delordning

En seriell-parallell partiell order  är en partiellt ordnad uppsättning konstruerad av mindre seriell-parallella partiella order med två enkla sammanfogningsoperationer [1] [2] .

Seriell-parallella partiella order kan beskrivas som N-ordningsfria ändliga partiella order. De har ordningsmått högst två [1] [3] . Dessa ordningar inkluderar svaga ordningar och nåbarhetsrelationen i riktade träd och riktade parallell-sekventiella grafer [2] [3] . Jämförbarhetsgraferna för seriell-parallella partiella beställningar är kografer [2] [4] .

Seriell-parallella partiella ordrar tillämpas i schemaläggningsteori [5] , maskininlärning av händelsesekvenser i tidsseriedata [6] , multimediadataöverföringssekvens [ 7] och genomströmningsmaximering i dataströmmar [ 8 ] .

Seriell-parallella partiella beställningar kallas också multiträd [4] . Detta namn är dock tvetydigt - multitrees kallas också partiella ordningar utan fyra-elements underordningar ("diamanter") [9] , såväl som andra strukturer som bildas av flera träd.

Definition

Låt P och Q vara två delvis ordnade uppsättningar. Seriekoppling av P och Q , skrivet P ; Q [7] , P * Q [2] , eller P ⧀ Q [1] , är en poset vars element är den disjunkta föreningen av elementen i P och Q . I P ; Q , två element x och y som samtidigt hör till P eller Q har samma ordningsrelation som de hade i P respektive Q. För alla par x , y där x tillhör P och y tillhör Q , finns det en ytterligare ordningsrelation x ≤ y definierad av seriekoppling. Seriell anslutning är en associativ operation - du kan skriva P ; Q ; R som en sammanlänkning av tre ordningar utan att införa tvetydighet om hur man kombinerar dem i par, eftersom parenteser ( P ; Q ); R & P ; ( Q ; R ) beskriver samma delordning. Denna sammanfogning är dock inte en kommutativ operation , eftersom omkastning av rollerna för P och Q kommer att ge en annan partiell ordning, där ordningsrelationerna för par av element, en från P , den andra från Q , är omvända [1] .

Parallellkoppling av P och Q , skrivet P  || Q [7] , P + Q [2] eller P ⊕ Q [1] , definieras från den disjunkta föreningen av element i P och element i Q på ett liknande sätt. Om ett par element helt och hållet tillhör P eller Q förblir ordningen densamma som den var i P respektive Q. Om ett element x tillhör P och ett element y tillhör Q , är elementen x och y ojämförbara. Parallellkoppling är associativ och kommutativ [1] .

Klassen av seriell-parallella delordrar är uppsättningen av delorder som kan byggas från singel-delorder med dessa två operationer. På motsvarande sätt är en klass den minsta uppsättningen av partiella order som inkluderar en singelton partiell order och som är stängd under seriella och parallella anslutningsoperationer [1] [2] .

Svag ordning är en serie-parallell partiell ordning som är ett resultat av en sekvens av joinoperationer där alla parallella joinoperationer först utförs och sedan resultaten av dessa operationer kombineras med endast sekventiella operationer [2] .

Beskrivning av förbjudna underordnar

En partiell ordning N med fyra element a , b , c och d och exakt tre ordningsrelationer a ≤ b ≥ c ≤ d är ett exempel på ett staket (eller sicksackordning). Hans Hasse-diagram är i form av en stor bokstav "N". Denna ordning är inte serieparallell eftersom det inte finns något sätt att dela upp den i sekvenser av parallella anslutningar av två mindre delordningar. En partiell ordning P sägs vara fri från N-ordningen om det inte finns några mängder av fyra element i P så att begränsningen av P till dessa element är isomorf till N i betydelsen av partiell ordning. Seriell-parallella partiella order är exakt de icke-tomma ändliga N-ordningsfria partiella order [1] [2] [3] .

Detta innebär omedelbart (även om detta kan bevisas direkt) att varje icke-tom begränsning av en serie-parallell partiell ordning i sig är en serie-parallell partiell ordning [1] .

Ordinaldimension

Ordinaldimensionen för en partiell ordning P är minimistorleken för realiseringar P , uppsättningen av linjära förlängningar (linjäriseringar) av ordningen P med egenskapen att för två distinkta element x och y av ordningen P , x ≤ y om och endast om x föregår y i någon linjär fortsättning på implementeringen.

En alternativ definition kan hittas på Internet: "Det minsta antalet linjära beställningar som ger en given partiellt ordnad uppsättning vid skärningspunkten kallas dess (ordinala dimension)", till exempel i föreläsningar av Gurov S.I. [10] eller Kuznetsova S.O. [11] .

Seriell-parallella delordrar har en dimension som inte överstiger två. Om P och Q har implementerare { L 1 ,  L 2 } respektive { L 3 ,  L 4 } är { L 1 L 3 ,  L 2 L 4 } implementeraren för P :s seriekoppling ; Q , och { L 1 L 3 ,  L 4 L 2 } är implementeraren av parallellkopplingen P  || F [2] [3] . En partiell ordning är seriell-parallell om och endast om den har en implementerare där en av de två permutationerna är identisk och den andra är separerbar .

Det är känt att en partiell ordning P har ordningsdimension två om och endast om det finns en konjugerad ordning Q på samma element med egenskapen att två distinkta element x och y är jämförbara i exakt en av dessa ordningar. I fallet med seriell-parallella partiella ordningar kan den konjugerade ordningen, som i sig är seriell-parallell, erhållas genom att utföra en sekvens av joinoperationer i samma ordning som för P på samma element, men istället för seriell join, P använder parallellkoppling och vice versa. Mer strikt, även om en partiell ordning kan ha olika konjugerade ordningsföljder, måste varje konjugerad ordning av en seriell-parallell partiell ordning också vara seriell-parallell [2] .

Samband med grafteori

Vilken partiell ordning som helst kan representeras (vanligtvis icke-unik) av en riktad acyklisk graf som har en väg från x till y för alla element x och y i den partiella ordningen för vilka x ≤ y . Grafer som representerar seriell-parallella partiella ordningar på detta sätt kallas vertex seriell-parallella grafer och deras transitiva reduktioner (grafer av partiell ordning som täcker relationer ) kallas minimal vertex seriell-parallella grafer 3] . Riktade träd och (med ett terminalpar) parallell-seriegrafer är exempel på minimala seriell-parallella grafer. Således kan seriell-parallella partiella beställningar användas för att representera nåbarhetsrelationen i riktade träd och parallella grafer [2] [3] .

En jämförbarhetsgraf med partiell ordning är en oriktad graf med hörn för varje element och en oriktad kant för varje par av distinkta element x , y om x ≤ y eller y ≤ x . Det vill säga, den bildas från en minimal seriell-parallell graf genom att ta bort kantorienteringen . Jämförbarhetsgrafen för seriell-parallell ordning är en kograf — kopplingsoperationer i serie och parallell ordning ger operationer på jämförbarhetsgrafen som bildar en disjunkt förening av två subgrafer eller förbinder två subgrafer med alla möjliga kanter. Dessa två operationer är de grundläggande operationerna i definitionen av kografer. Omvänt är varje kograf en seriell-parallell partiell ordningsjämförbarhetsgraf. Om en partiell ordning har en kograf som jämförbarhetsgraf, måste den vara en seriell-parallell partiell ordning, eftersom varje annan typ av partiell ordning har en N-underord, som måste motsvara en genererad väg med fyra hörn i dess jämförbarhetsgraf , och sådana vägar är förbjudna i kografer [2] [4] .

Beräkningskomplexitet

Du kan använda den förbjudna underordningsbeskrivningen av seriell-parallella partiella order som grund för en algoritm som kontrollerar, i tid linjärt beroende på antalet par i en relation, om en given binär relation är en seriell-parallell partiell ordning [2] [3] . Alternativt, om en partiell order beskrivs som nåbarhetsordningen för en riktad acyklisk graf , är det möjligt att testa om det är en seriell-parallell partiell order, och om så är fallet, beräkna dess transitiva stängning i tid proportionell mot antal hörn och kanter i den transitiva förslutningen. Det är fortfarande en öppen fråga om det är möjligt att förbättra igenkänningstiden för seriell-parallella nåbarhetsorder till linjär storlek på indatagrafen [12] .

Om en seriell-parallell partiell ordning representeras som ett uttrycksträd som beskriver exekveringen av seriella och parallella operationer, då kan elementen i den partiella ordningen representeras av uttrycksträdets blad. Jämförelse av två element kan göras algoritmiskt genom att hitta den minst gemensamma förfadern till motsvarande två blad. Om denna förfader är en parallellkoppling är de två elementen ojämförbara, annars bestämmer ordningen på operandernas seriekopplingar elementens ordning. På detta sätt kan en serieparallell partiell ordning av n element representeras i O( n )-rymden för att bestämma vilket värde som helst som ska jämföras i O(1) [2] -tid .

Problemet med att kontrollera för två givna seriell-parallella partiella order P och Q att P innehåller en restriktion isomorf till Q är NP-komplett [3] .

Även om problemet med att räkna antalet linjära förlängningar av en godtycklig partiell ordning är #P-komplett [13] , kan det visas att det kan lösas i polynomtid för seriell-parallella partiella ordningar. Nämligen, om L ( P ) anger antalet linjära förlängningar av den partiella ordningen P , då L ( P ; Q )= L ( P ) L ( Q ) och

[2] .

Applikationer

Mannila och Meek [14] använde seriell-parallella partiella beställningar som en modell för händelseförloppet i tidsseriedata . De beskrev maskininlärningsalgoritmer för slutledningsmodeller för denna typ och demonstrerade effektiviteten av algoritmerna för att generera obligatoriska kurskrav baserat på studentregistreringsdata, såväl som vid modellering av webbläsaranvändningsmönster [6] .

Amer et al [15] hävdar att seriell-parallella partiella beställningar är bekväma för att modellera förfrågningar om sekvensering av mediapresentationer . De använde formeln för att beräkna antalet linjära fortsättningar av en seriell-parallell partiell ordning som grund för analysen av multimediaöverföringsalgoritmer [7] .

Chaudhary et al [16] använde seriell-parallella partiella order för att modellera uppgiftsberoenden i ett dataflöde av bulkdatabehandling för datorseende . De visade att när man använder seriell-parallella order för denna uppgift är det möjligt att effektivt konstruera ett optimalt schema som tilldelar olika uppgifter till olika processorer i ett parallellt datorsystem för att optimera genomströmningen av systemet [8] .

Klassen av ordningsföljder, något mer generell än begreppet seriell-parallella partiella beställningar, ges av PQ-trees , datastrukturer som används i algoritmer för att kontrollera om en graf är plan och för att känna igen intervallgrafer [17] . En nod P i ett PQ-träd tillåter alla möjliga ordningsföljder av dess avkomlingar som en parallellkoppling i delordningar, medan en nod Q kräver att efterföljarna följer i en fast linjär ordning som sekventiella partiella ordningsföljder. Men till skillnad från seriell-parallella partiella ordningar tillåter PQ-träd dig att vända den linjära ordningen vid valfri nod av Q .

Anteckningar

  1. ↑ 1 2 3 4 5 6 7 8 9 Bechet, De Groote, Retoré, 1997 , sid. 230–240.
  2. ↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Möhring, 1989 , sid. 105–194.
  3. ↑ 1 2 3 4 5 6 7 8 Valdes, Tarjan, Lawler, 1982 , sid. 298–313.
  4. ↑ 1 2 3 Jung, 1978 , sid. 125–133.
  5. ↑ Lawler, 1978 , sid. 75–90.
  6. ↑ 1 2 Mannila, Meek, 2000 , sid. 161–168.
  7. ↑ 1 2 3 4 Amer, Chassot, Connolly et al., 1994 , sid. 440–456.
  8. ↑ 1 2 Choudhary, Narahari, Nicol, Simha, 1994 , sid. 439–445.
  9. ↑ Furnas och Zacks 1994 , sid. 330–336.
  10. ↑ Gurov, 2012 , sid. 111 Definition 3.14.
  11. ↑ Kuznetsov .
  12. ↑ Ma, Spinrad, 1991 , sid. 175–183.
  13. ↑ Brightwell, Winkler, 1991 , sid. 225–242.
  14. ↑ Mannila, Meek, 2000 .
  15. ↑ Amer, Chassot, Connolly et al., 1994 .
  16. ↑ Choudhary, Narahari, Nicol, Simha, 1994 .
  17. ↑ Booth och Lueker 1976 , sid. 335–379.

Litteratur