Dioidní

V matematiky a výpočetní techniky , je dioid je polovina-kroužek , ve kterém preorder definovaný přídavkem je vztah pořadí .

Definice

Nechť D je množina poskytovaná binárním operátorem , který se nazývá sčítání, s binárním operátorem , který se nazývá produkt, a ve kterém jsou specifikovány dva odlišné prvky, označené 0 a 1. ⊕{\ displaystyle \ oplus}⊗{\ displaystyle \ otimes}

Označujeme ≤ předobjednávkou spojenou s operátorem a definovanou . ⊕{\ displaystyle \ oplus}na≤b⇔∃vs., na⊕vs.=b{\ displaystyle a \ leq b \ Leftrightarrow \ existuje c, ~ a \ oplus c = b}

Říkáme, že jde o dioid, pokud: (D,⊕,⊗,0,1){\ displaystyle (D, \ oplus, \ otimes, 0,1)}

• (D,⊕,0){\ displaystyle (D, \ oplus, 0)}je komutativní monoid ;
• (D,⊗,1){\ displaystyle (D, \ otimes, 1)} je monoid;
• ⊗{\ displaystyle \ otimes}je distribuční ve vztahu k  ;⊕{\ displaystyle \ oplus}
• 0 je absorpční prvek pro , tj  .;⊗{\ displaystyle \ otimes}na⊗0=0⊗na=0{\ displaystyle a \ otimes 0 = 0 \ otimes a = 0}
• vztah ≤ je řádový vztah, to znamená .na≤b∧b≤na⇒na=b{\ displaystyle a \ leq b \ klín b \ leq a \ Rightarrow a = b}

Pokud vynecháme poslední bod, definovanou strukturou je půlkruh.

Terminologie

Název dioidu vychází ze skutečnosti, že kombinuje dva monoidy, jako každý půlkruh (zejména jakýkoli kruh ). Tento název použil Jean Kuntzmann v roce 1972 pro strukturu, která se nyní nazývá půlkruh. Použití k označení idempotentní podskupiny představili Baccelli a kol. v roce 1992.

Dioidy i prstence jsou půlkruhy, ale vzájemně se vylučují .

Idempotentní dioid

Idempotent dioid je nejrozšířenější třída dioids. Je charakterizována skutečnost, že všechny prvky jsou idempotentní , to znamená . na{\ displaystyle a}⊕{\ displaystyle \ oplus}na⊕na=na{\ displaystyle a \ oplus a = a}

Například je idempotentní dioid. ([-∞,+∞[,max,+,-∞,0){\ displaystyle ([- \ infty, + \ infty [, \ max, +, - \ infty, 0)}

Jakýkoli idempotentní půlkruh je dioid.

Demonstrace

Jde o prokázání, že předobjednávkový vztah je řád. Pokud pak existuje c takové, že tedy na≤b{\ displaystyle a \ leq b}na⊕vs.=b{\ displaystyle a \ oplus c = b}

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

Stejně tak, pokud tedy . Proto pokud a , pak pomocí komutativity dostaneme b≤na{\ displaystyle b \ leq a}na=b⊕na{\ displaystyle a = b \ oplus a}na≤b{\ displaystyle a \ leq b}b≤na{\ displaystyle b \ leq a}⊕{\ displaystyle \ oplus}

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

Idempotentní půlkruhy jsou tedy přesně idempotentní dioidy.

Podívejte se také

• Tropická matematika

Poznámky a odkazy

1. Jean Kuntzmann , Teorie sítí (grafy) , Paříž, Dunod,1972, xxiv + 288  str. ( zbMATH  0239.05101 , SUDOC  002235358 ).
2. (in) Francois Baccelli, Guy Cohen, Geert Jan Olsder a 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  str. ( ISBN  0-471-93609-X , SUDOC  014487500 , číst online ).

Bibliografie

• Michel Gondran a Michel Minoux , Graphs, dioids and semi-ring: new models and algorithms , Paris, Tec & Doc,2001, xvi + 415  str. ( ISBN  2-7430-0489-4 , SUDOC  060235101 )- Anglické vydání: (en) Michel Gondran a Michel Minoux , Graphs, Dioids and Semirings: New Models and Algorithms , Dordrecht, Springer Science & Business Media, coll.  „Operační výzkum / Výpočetní technika rozhraní série“ ( n o  41)2008, 388  s. ( ISBN  978-0-387-75450-5 , zbMATH  1201.16038 , číst online )

• Michel Minoux, „  Lineární algebra v polokroužcích a dioidech  “ [PDF] , na 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;">