Dioida

W matematyce i informatyce , o dioid jest pół-ring , w którym preorder zdefiniowane przez dodanie jest relacja zamówienie .

Definicja

Niech D będzie zbiorem wyposażonym w operator binarny , zwany dodawaniem, z operatorem binarnym zwanym produktem, w którym określone są dwa różne elementy, oznaczone 0 i 1. $\ oplus$ $\ otimes$

Oznaczamy przez ≤ zamówienie w przedsprzedaży skojarzone z operatorem i zdefiniowane przez . $\ oplus$ $a \ leq b \ Leftrightarrow \ istnieje c, ~ a \ oplus c = b$

Mówimy, że jest to dioida, jeśli: $(D, \ oplus, \ otimes, 0,1)$

$(D, \ oplus, 0)$ jest przemiennym monoidem ;
$(D, \ otimes, 1)$ jest monoidem;
$\ otimes$ jest rozdzielczy w odniesieniu do ; $\ oplus$
0 jest Element chłonny do , to znaczy ,; $\ otimes$ $a \ otimes 0 = 0 \ otimes a = 0$
relacja ≤ jest relacją porządku, to znaczy tak . $a \ leq b \ wedge b \ leq a \ Rightarrow a = b$

Jeśli pominiemy ostatni punkt, zdefiniowana struktura jest półpierścieniem.

Terminologia

Nazwa dioida pochodzi od tego, że łączy w sobie dwa monoidy, jak każdy półpierścień (zwłaszcza każdy pierścień ). Nazwa ta została użyta przez Jeana Kuntzmanna w 1972 roku dla konstrukcji nazywanej obecnie półpierścieniem. Zastosowanie do wyznaczenia idempotentnej podgrupy zostało wprowadzone przez Baccelli et al. w 1992 roku.

Zarówno dioidy, jak i pierścienie są półpierścieniami, ale wykluczają się wzajemnie .

Idempotent dioidalny

Dioid idempotentny jest najczęściej używaną klasą dioidów. Charakteryzuje się faktem, że każdy element jest idempotentny , to znaczy dla tego . $w$ $\ oplus$ $a \ oplus a = a$

Na przykład jest idempotentnym dioidem. $([- \ infty, + \ infty [, \ max, +, - \ infty, 0)$

Każdy idempotentny półpierścień jest dioidą.

Demonstracja

Chodzi o udowodnienie, że relacja preorder jest zamówieniem. Jeśli to istnieje C , tak że stąd $a \ leq b$ $a \ oplus c = b$

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

Podobnie, jeśli wtedy . Dlatego jeśli i , to używając przemienności otrzymamy $b \ leq a$ $a = b \ oplus a$ $a \ leq b$ $b \ leq a$ $\ oplus$

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

Idempotentne półpierścienie są zatem dokładnie idempotentnymi dioidami.

Zobacz też

Matematyka tropikalna

Uwagi i odniesienia

Jean Kuntzmann , Teoria sieci (wykresy) , Paryż, Dunod,1972, XXIV + 288 pkt. ( zbMATH 0239.05101 , SUDOC 002235358 ).
(w) Francois Baccelli, Guy Cohen, Geert Jan Olsder i Jean-Pierre Quadrat, Synchronization and Linearity: An Algebra for Discrete Event Systems , Chichester, Wiley, al. „Seria Wiley na temat prawdopodobieństwa i statystyki matematycznej”,1992, xix + 489 pkt. ( ISBN 0-471-93609-X , SUDOC 014487500 , czytaj online ).

Bibliografia

Michel Gondran i Michel Minoux , Wykresy, dioidy i półpierścienie: nowe modele i algorytmy , Paryż, Tec & Doc,2001, XVI + 415 pkt. ( ISBN 2-7430-0489-4 , SUDOC 060235101 )- wydanie angielskie: (en) Michel Gondran i Michel Minoux , Graphs, Dioids and Semirings: New Models and Algorithms , Dordrecht, Springer Science & Business Media, coll. "Badania Operacyjne / Interfejsy Computer Science Series" ( n O 41)2008, 388 str. ( ISBN 978-0-387-75450-5 , zbMATH 1201.16038 , czytaj online )

Michel Minoux, " Algebra liniowa w półpierścieniach i dioidach " [PDF] , na HAL ,1998