Dioide

În matematică și informatică , un dioid este o jumătate de inel în care precomanda definită prin adunare este o relație de ordine .

Definiție

Fie D un set prevăzut cu un operator binar , numit adunare, cu un operator binar , numit produs și în care sunt specificate două elemente distincte, notate 0 și 1. ⊕{\ displaystyle \ oplus}⊗{\ displaystyle \ otimes}

Notăm cu ≤ precomanda asociată cu operatorul și definită de . ⊕{\ displaystyle \ oplus}la≤b⇔∃vs., la⊕vs.=b{\ displaystyle a \ leq b \ Leftrightarrow \ există c, ~ a \ oplus c = b}

Spunem că este un dioid dacă: (D,⊕,⊗,0,1){\ displaystyle (D, \ oplus, \ otimes, 0,1)}

• (D,⊕,0){\ displaystyle (D, \ oplus, 0)}este un monoid comutativ;
• (D,⊗,1){\ displaystyle (D, \ otimes, 1)} este un monoid;
• ⊗{\ displaystyle \ otimes}este distributiv în ceea ce privește  ;⊕{\ displaystyle \ oplus}
• 0 este un element absorbant pentru , adică  ;⊗{\ displaystyle \ otimes}la⊗0=0⊗la=0{\ displaystyle a \ otimes 0 = 0 \ otimes a = 0}
• relația ≤ este o relație de ordine, adică că .la≤b∧b≤la⇒la=b{\ displaystyle a \ leq b \ wedge b \ leq a \ Rightarrow a = b}

Dacă omitem ultimul punct, structura definită este o jumătate de inel.

Terminologie

Denumirea de dioid provine din faptul că combină doi monoizi, ca orice jumătate de inel (în special orice inel ). Acest nume a fost folosit de Jean Kuntzmann în 1972 pentru structura numită acum jumătate de inel. Utilizarea pentru a desemna un subgrup idempotent a fost introdusă de Baccelli și colab. în 1992.

Atât dioidele, cât și inelele sunt jumătăți de inele, dar se exclud reciproc .

Dioid puternic

Dioidul idempotent este cea mai utilizată clasă de dioide. Se caracterizează faptul că toate elementele sunt idempotente pentru , adică asta . la{\ displaystyle a}⊕{\ displaystyle \ oplus}la⊕la=la{\ displaystyle a \ oplus a = a}

De exemplu, este un dioid idempotent. ([-∞,+∞[,max,+,-∞,0){\ displaystyle ([- \ infty, + \ infty [, \ max, +, - \ infty, 0)}

Orice jumătate de inel idempotent este un dioid.

Demonstrație

Este vorba de a demonstra că relația de precomandă este o ordine. Dacă atunci există c astfel încât , de aici la≤b{\ displaystyle a \ leq b}la⊕vs.=b{\ displaystyle a \ oplus c = b}

b=la⊕vs.=la⊕la⊕vs.=la⊕b{\ displaystyle b = a \ oplus c = a \ oplus a \ oplus c = a \ oplus b}.

La fel, dacă atunci . Prin urmare, dacă și , atunci folosind comutativitatea obținem b≤la{\ displaystyle b \ leq a}la=b⊕la{\ displaystyle a = b \ oplus a}la≤b{\ displaystyle a \ leq b}b≤la{\ displaystyle b \ leq a}⊕{\ displaystyle \ oplus}

b=la⊕b=b⊕la=la{\ displaystyle b = a \ oplus b = b \ oplus a = a}.

Semicercurile idempotente sunt, prin urmare, exact dioidele idempotente.

Vezi și tu

• Matematică tropicală

Note și referințe

1. Jean Kuntzmann , Teoria rețelelor (grafice) , Paris, Dunod,1972, xxiv + 288  p. ( zbMATH  0239.05101 , SUDOC  002235358 ).
2. (în) Francois Baccelli, Guy Cohen, Geert Jan Olsder și Jean-Pierre Quadrat, Sincronizare și liniaritate: o algebră pentru sisteme de evenimente discrete , Chichester, Wiley, al.  „Seria Wiley privind probabilitatea și statisticile matematice”,1992, xix + 489  p. ( ISBN  0-471-93609-X , SUDOC  014487500 , citit online ).

Bibliografie

• Michel Gondran și Michel Minoux , Grafice, dioide și semi-inele: noi modele și algoritmi , Paris, Tec & Doc,2001, xvi + 415  p. ( ISBN  2-7430-0489-4 , SUDOC  060235101 )- Ediția în limba engleză: (ro) Michel Gondran și Michel Minoux , Grafice, dioxide și semirings: noi modele și algoritmi , Dordrecht, Springer Science & Business Media, col.  "Seria de interfețe de cercetare operațională / informatică" ( nr .  41)2008, 388  p. ( ISBN  978-0-387-75450-5 , zbMATH  1201.16038 , citiți online )

• Michel Minoux, „  Algebră liniară în semi-inele și dioide  ” [PDF] , pe HAL ,1998

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">