Dioid

I matematikk og datateknologi , en dioid er en halv-ring , hvor den pre-order definert ved tilsetning er en ordre forhold .

Definisjon

La D være et sett utstyrt med en binær operator , kalt tillegg, med en binær operator , kalt produkt, og der to forskjellige elementer, betegnet 0 og 1, er spesifisert. $\ oplus$ $\ ganger$

Vi betegner med ≤ forhåndsbestillingen tilknyttet operatøren og definert av . $\ oplus$ $a \ leq b \ Leftrightarrow \ eksisterer c, ~ a \ oplus c = b$

Vi sier at det er en dioid hvis: $(D, \ oplus, \ otimes, 0,1)$

$(D, \ oplus, 0)$ er en kommutativ monoid ;
$(D, \ ganger, 1)$ er en monoid;
$\ ganger$ er distribuerende med hensyn til ; $\ oplus$
0 er et absorberende element for , det vil si; $\ ganger$ $a \ ganger 0 = 0 \ ganger a = 0$
forholdet ≤ er en ordrerelasjon, det vil si det . $a \ leq b \ kil b \ leq a \ Rightarrow a = b$

Hvis vi utelater det siste punktet, er den definerte strukturen en halvring.

Terminologi

Navnet på dioid kommer av det faktum at det kombinerer to monoider, som enhver halvring (spesielt hvilken som helst ring ). Dette navnet ble brukt av Jean Kuntzmann i 1972 for strukturen som nå kalles halvringen. Bruken til å betegne en idempotent undergruppe ble introdusert av Baccelli et al. i 1992.

Både dioider og ringer er halve ringer, men de er gjensidig utelukkende .

Idempotent dioid

Den idempotente dioiden er den mest brukte klassen av dioider. Det kjennetegnes ved at alt element er idempotent for , det vil si det . $på$ $\ oplus$ $a \ oplus a = a$

For eksempel er en idempotent dioid. $([- \ infty, + \ infty [, \ max, +, - \ infty, 0)$

Enhver idempotent halvring er en dioid.

Demonstrasjon

Det er et spørsmål om å bevise at forholdet mellom forhåndsbestilling er en ordre. Hvis det eksisterer c slik at , derav $a \ leq b$ $a \ oplus c = b$

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

Likeledes, hvis da . Derfor, hvis og , deretter bruke commutativity av vi får $b \ leq a$ $a = b \ oplus a$ $a \ leq b$ $b \ leq a$ $\ oplus$

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

De idempotente halvringene er derfor akkurat de idempotente dioidene.

Se også

Tropisk matematikk

Merknader og referanser

Jean Kuntzmann , teori om nettverk (grafer) , Paris, Dunod,1972, xxiv + 288 s. ( zbMATH 0239.05101 , SUDOC 002235358 ).
(in) Francois Baccelli, Guy Cohen, Geert Jan Olsder og Jean-Pierre Quadrat, Synchronization and Linearity: An Algebra for Discrete Event Systems , Chichester, Wiley, al. "Wiley Series on Probability and Mathematical Statistics",1992, xix + 489 s. ( ISBN 0-471-93609-X , SUDOC 014487500 , les online ).

Bibliografi

Michel Gondran og Michel Minoux , grafer, dioider og semi-ringer: nye modeller og algoritmer , Paris, Tec & Doc,2001, xvi + 415 s. ( ISBN 2-7430-0489-4 , SUDOC 060235101 )- Engelsk utgave: (en) Michel Gondran og Michel Minoux , Graphs, Dioids and Semirings: New Models and Algorithms , Dordrecht, Springer Science & Business Media, koll. "Operations Research / Computer Science grensesnitt Series" ( N o 41)2008, 388 s. ( ISBN 978-0-387-75450-5 , zbMATH 1201.16038 , les online )

Michel Minoux, " Lineær algebra i halvringer og dioider " [PDF] , på HAL ,1998