Dominator (graafiteoria)

Dominaattori graafiteoriassa on binäärirelaatio suunnatun graafin solmuissa , jossa on erottuva syöttösolmu. Se osoittaa edun, kun polku kulkee syöttösolmusta: graafin solmu hallitsee solmua (kirjoitettuna tai ), jos polkua graafista on. syöttösolmu kulkee läpi . Erityisesti jokainen solmu hallitsee itseään. $d$ $n$ $d\,\mathrm{dom}\,n$ $d \gg n$ $n$ $d$

Yleisin käyttö on kääntäjien rakentamisen teoriassa käytetyissä ohjausvuokaavioissa .

Hyödyllinen tapa esittää tietoa dominatoreista on dominatoripuuksi kutsuttu puu , jossa syötesolmu on juuri ja jokainen solmu hallitsee puussa vain lapsiaan [1] . $d$

Historia

Dominanssin tietojenkäsittelytieteessä esitteli ensimmäisenä Reese T. Prosser vuonna 1959 [2] , dominanssilaskenta-algoritmin julkaisivat ensimmäisen kerran 10 vuotta myöhemmin Lowry ja Medlock ( ES Lowry , CW Medlock ) [3] . Uusi kiinnostus dominanssirelaation käyttöön tulee Ron Cytronin vuoden 1989 artikkelista, joka käyttää tätä suhdetta SSA-esityksessä käytettyjen φ-funktioiden tehokkaaseen laskemiseen [4] .

Relationship Properties

Keskeinen havainto dominatoreista on, että jos otamme minkä tahansa asyklisen polun syöttösolmusta solmuun , niin kaikki dominatorit sijoittuvat tälle polulle, ja lisäksi ne sijaitsevat samassa järjestyksessä minkä tahansa polun varrella. $n$ $n$

Transitiivisuus : jos ja niin , $a\,\mathrm{dom}\,b$ $b\,\mathrm{dom}\,c$ $a\,\mathrm{dom}\,c$
Antisymmetria : jos , niin ja samanaikainen suoritus on mahdotonta . $a \neq b$ $a\,\mathrm{dom}\,b$ $b\,\mathrm{dom}\,a$

Jos ja ja ovat dominoijia , niin joko , tai . Tästä seuraa, että jokaisella solmulla paitsi syöttösolmulla on oltava yksi välitön dominatori, toisin sanoen dominatori, joka on lähinnä mitä tahansa asyklistä polkua syöttösolmusta [5] :een . $a$ $b$ $n$ $a\,\mathrm{dom}\,b$ $b\,\mathrm{dom}\,a$ $n$ $n$ $n$

Sovellus

Dominanssia käytetään kääntäjissä SSA - esityksen muodostamiseen . Useat kääntäjien optimoinnit voivat myös hyötyä dominatoreiden käytöstä. Automaattista rinnastusta varten on hyödyllistä tietää kaikki solmut, joita tietty solmu hallitsee. Muistin käyttöanalyysi voi hyötyä dominatoripuusta, jonka avulla on helppo löytää vuotoja ja tunnistaa liiallinen muistin käyttö. Ohjelmistojärjestelmissä niitä käytetään pienentämään testijoukon kokoa [6] .

Implikaatiograafin dominatoria etsitään Boolen kaavojen tyydyttävyysongelmien CDCL-ratkaisijoista , kun analysoidaan konfliktirakennetta [7] .

Muistiinpanot

↑ Kääntäjät: periaatteet, tekniikat ja työkalut, 2008 , s. 787.
↑ Prosser, Reese T. Boolen matriisien sovellukset vuokaavioiden analysointiin // AFIPS Joint Computer Conferences: Paperit esitelty 1.–3. joulukuuta 1959, itäinen yhteinen IRE-AIEE-ACM-tietokonekonferenssi : lehti. - Boston, MA: ACM, 1959. - P. 133-138 .
↑ Lowry, Edward S.; ja Medlock, Cleburne W. Objektikoodin optimointi // Communications of the ACM : Journal. - 1969. - tammikuu ( osa 12 , nro 1 ) . - s. 13-22 .
↑ Cytron, Ron; Hind, Michael; ja Hsieh, Wilson. Automatic Generation of DAG Parallelism (indefinite) // Proceedings of the ACM SIGPLAN 89 Conference on Programming Language Design and Implementation. - 1989. - S. 54-68 .
↑ Kääntäjät: periaatteet, tekniikat ja työkalut, 2008 , s. 788.
↑ Dubrova, Elena. Vähimmäisytimiin perustuva rakennetestaus (määrittämätön) // Proceedings of Design and Test in Europe Conference. - 2005. - S. 1168-1173 .
↑ Armin Biere, Marijn Heule, Hans van Maaren ja Toby Walsch. Luku 4. Konfliktilähtöinen lausekkeen oppiminen SAT- ratkaisijat // Handbook of Satisfiability. - IOS Press, 2008. - s. 135.

Kirjallisuus

Alfred W. Aho, Monica S. Lam, Ravi Seti, Jeffrey D. Ullman. Kääntäjät: periaatteet, tekniikat ja työkalut = kääntäjät: periaatteet, tekniikat ja työkalut. - Williams Publishing House, 2008. - ISBN 0-321-48681-1 .