Dioidi

In matematiikan ja tietojenkäsittelytiede , eli dioid on puoli-rengas , jossa ennakkotilauskauden määritellään lisäämällä on tilauksen suhteen .

Määritelmä

Olkoon D joukko, joka on varustettu binäärioperaattorilla , jota kutsutaan lisäykseksi, binäärioperaattorina , jota kutsutaan tuotteeksi, ja jossa määritetään kaksi erillistä elementtiä, joita merkitään 0 ja 1. $\ oplus$ $\ otimes$

Merkitsemme ≤ operaattoriin liittyvän ennakkotilauksen, jonka määrittelee . $\ oplus$ $a \ leq b \ Vasenkätinen nuoli \ on olemassa c, ~ a \ oplus c = b$

Sanomme, että se on dioidi, jos: $(D, \ oplus, \ otimes, 0,1)$

$(D, \ oplus, 0)$ on kommutatiivinen monoidi ;
$(D, \ otimes, 1)$ on monoidi;
$\ otimes$ on jakautuva suhteessa ; $\ oplus$
0 on imukykyinen elementti on , että on ,; $\ otimes$ $a \ otimes 0 = 0 \ otimes a = 0$
suhde ≤ on järjestyssuhde, toisin sanoen se . $a \ leq b \ wedge b \ leq a \ Rightarrow a = b$

Jos jätämme viimeisen pisteen pois, määritelty rakenne on puolirengas.

Terminologia

Dioidin nimi tulee siitä, että se yhdistää kaksi monoidia, kuten mikä tahansa puolirengas (erityisesti mikä tahansa rengas ). Tätä nimeä käytti Jean Kuntzmann vuonna 1972 rakenteelle, jota nyt kutsutaan puolirenkaaksi. Baccelli et ai. Esittivät käytön idempotentin alaryhmän nimeämiseen . vuonna 1992.

Sekä dioidit että renkaat ovat puolirenkaita, mutta ne sulkevat toisiaan pois .

Idempotentti dioidi

Idempotentti dioid on yleisimmin käytetty luokka dioids. Sille on tunnusomaista, että kaikki elementit ovat idempotentteja , toisin sanoen niin . $klo$ $\ oplus$ $a \ oplus a = a$

Esimerkiksi on idempotentti dioidi. $([- \ infty, + \ infty [, \ max, +, - \ infty, 0)$

Mikä tahansa idempotenttinen puolirengas on dioidi.

Esittely

Kyse on todistamisesta, että ennakkotilauksen suhde on järjestys. Jos sitten on olemassa c sellainen, että , siis $a \ leq b$ $a \ oplus c = b$

b = a \ oplus c = a \ oplus a \ oplus c = a \ oplus b

Samoin, jos silloin . Siksi, jos ja , sitten saamme kommutatiivisuutta $b \ leq a$ $a = b \ oplus a$ $a \ leq b$ $b \ leq a$ $\ oplus$

b = a \ oplus b = b \ oplus a = a

Idempotentit puolirenkaat ovat siis täsmälleen idempotentit dioidit.

Katso myös

Trooppinen matematiikka

Huomautuksia ja viitteitä

Jean Kuntzmann , Verkkojen teoria (kaaviot) , Pariisi, Dunod,1972, xxiv + 288 Sivumäärä ( zbMATH 0239.05101 , SUDOC 002235358 ).
(in) Francois Baccelli, Guy Cohen, Geert Jan Olsder ja Jean-Pierre Quadrat, Synkronointi ja Lineaarisuus: algebran diskreetteiå Event Systems , Chichester, Wiley, ai. "Todennäköisyyttä ja matemaattisia tilastoja käsittelevä Wiley-sarja",1992, xix + 489 Sivumäärä ( ISBN 0-471-93609-X , SUDOC 014487500 , lue verkossa ).

Bibliografia

Michel Gondran ja Michel Minoux , kuvaajat, dioidit ja puolirenkaat: uudet mallit ja algoritmit , Paris, Tec & Doc,2001, xvi + 415 Sivumäärä ( ISBN 2-7430-0489-4 , SUDOC 060235101 )- Englanninkielinen painos: (en) Michel Gondran ja Michel Minoux , Graphs, Dioids and Semirings: New Models and Algorithms , Dordrecht, Springer Science & Business Media, kokoonpano. "Operations Research / Computer Science liitännät Series" ( n o 41)2008, 388 Sivumäärä ( ISBN 978-0-387-75450-5 , zbMATH 1201.16038 , lue verkossa )

Michel Minoux, " Lineaarinen algebra puolirenkaissa ja dioideissa " [PDF] , HAL ,1998