Dioide

In matematica e informatica , un dioid è un semianello in cui il preorder definito mediante aggiunta è una relazione d'ordine .

Definizione

Sia D un insieme fornito di un operatore binario , chiamato addizione, con un operatore binario , chiamato prodotto, e in cui sono specificati due elementi distinti, indicati con 0 e 1. ⊕{\ displaystyle \ oplus}⊗{\ displaystyle \ otimes}

Indichiamo con ≤ il preordine associato all'operatore e definito da . ⊕{\ displaystyle \ oplus}a≤b⇔∃vs, a⊕vs=b{\ displaystyle a \ leq b \ Leftrightarrow \ esiste c, ~ a \ oplus c = b}

Diciamo che è un dioide se: (D,⊕,⊗,0,1){\ displaystyle (D, \ oplus, \ otimes, 0,1)}

• (D,⊕,0){\ displaystyle (D, \ oplus, 0)}è un monoide commutativo;
• (D,⊗,1){\ displaystyle (D, \ otimes, 1)} è un monoide;
• ⊗{\ displaystyle \ otimes}è distributivo rispetto a  ;⊕{\ displaystyle \ oplus}
• 0 è un elemento assorbente per , cioè  ,;⊗{\ displaystyle \ otimes}a⊗0=0⊗a=0{\ displaystyle a \ otimes 0 = 0 \ otimes a = 0}
• la relazione ≤ è una relazione d'ordine, vale a dire che .a≤b∧b≤a⇒a=b{\ Displaystyle a \ leq b \ wedge b \ leq a \ Rightarrow a = b}

Se omettiamo l'ultimo punto, la struttura definita è un semianello.

Terminologia

Il nome di dioide deriva dal fatto che combina due monoidi, come qualsiasi semianello (soprattutto qualsiasi anello ). Questo nome fu usato da Jean Kuntzmann nel 1972 per la struttura ora chiamata semianello. L'uso per denotare un sottogruppo idempotente è stato introdotto da Baccelli et al. nel 1992.

Sia i dioidi che gli anelli sono semianelli, ma si escludono a vicenda .

Dioide idempotente

Il dioide idempotente è la classe di dioidi più utilizzata. Si caratterizza per il fatto che ogni elemento è idempotente per , vale a dire quello . a{\ displaystyle a}⊕{\ displaystyle \ oplus}a⊕a=a{\ displaystyle a \ oplus a = a}

Ad esempio, è un dioide idempotente. ([-∞,+∞[,max,+,-∞,0){\ displaystyle ([- \ infty, + \ infty [, \ max, +, - \ infty, 0)}

Qualsiasi semianello idempotente è un dioide.

Dimostrazione

Si tratta di provare che la relazione di preordine è un ordine. Se allora esiste c tale che , quindi a≤b{\ displaystyle a \ leq b}a⊕vs=b{\ displaystyle a \ oplus c = b}

b=a⊕vs=a⊕a⊕vs=a⊕b{\ Displaystyle b = a \ oplus c = a \ oplus a \ oplus c = a \ oplus b}.

Allo stesso modo, se allora . Pertanto, se e , quindi utilizzando la commutatività di otteniamo b≤a{\ displaystyle b \ leq a}a=b⊕a{\ displaystyle a = b \ oplus a}a≤b{\ displaystyle a \ leq b}b≤a{\ displaystyle b \ leq a}⊕{\ displaystyle \ oplus}

b=a⊕b=b⊕a=a{\ Displaystyle b = a \ oplus b = b \ oplus a = a}.

I semianelli idempotenti sono quindi esattamente i dioidi idempotenti.

Vedi anche

• Matematica tropicale

Note e riferimenti

1. Jean Kuntzmann , Teoria delle reti (grafici) , Parigi, Dunod,1972, xxiv + 288  p. ( zbMATH  0239.05101 , SUDOC  002235358 ).
2. (a) Francois Baccelli, Guy Cohen, Geert Jan Olsder e Jean-Pierre Quadrat, Synchronization and Linearity: An Algebra for Discrete Event Systems , Chichester, Wiley, al.  "Serie Wiley su probabilità e statistica matematica",1992, xix + 489  p. ( ISBN  0-471-93609-X , SUDOC  014487500 , leggi online ).

Bibliografia

• Michel Gondran e Michel Minoux , Grafici, dioidi e semianelli: nuovi modelli e algoritmi , Paris, Tec & Doc,2001, xvi + 415  p. ( ISBN  2-7430-0489-4 , SUDOC  060235101 )- Edizione inglese: (en) Michel Gondran e Michel Minoux , Graphs, Dioids and Semirings: New Models and Algorithms , Dordrecht, Springer Science & Business Media, coll.  "Serie di interfacce per ricerca operativa / informatica" ( n .  41)2008, 388  p. ( ISBN  978-0-387-75450-5 , zbMATH  1201.16038 , leggi online )

• Michel Minoux, "  Algebra lineare in semianelli e dioidi  " [PDF] , su 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;">