Dioide

En matemáticas e informática , un dioide es un medio anillo en el que el preorden definido por la suma es una relación de orden .

Definición

Sea D un conjunto provisto de un operador binario , llamado suma, con un operador binario , llamado producto, y en el que se especifican dos elementos distintos, denominados 0 y 1. ⊕{\ Displaystyle \ oplus}⊗{\ Displaystyle \ otimes}

Denotamos por ≤ el preorden asociado con el operador y definido por . ⊕{\ Displaystyle \ oplus}a≤B⇔∃vs, a⊕vs=B{\ Displaystyle a \ leq b \ Leftrightarrow \ existe c, ~ a \ oplus c = b}

Decimos que es un dioide si: (D,⊕,⊗,0,1){\ Displaystyle (D, \ oplus, \ otimes, 0,1)}

• (D,⊕,0){\ Displaystyle (D, \ oplus, 0)}es un monoide conmutativo;
• (D,⊗,1){\ Displaystyle (D, \ otimes, 1)} es un monoide;
• ⊗{\ Displaystyle \ otimes}es distributivo con respecto a  ;⊕{\ Displaystyle \ oplus}
• 0 es un elemento absorbente para , es decir  ,;⊗{\ Displaystyle \ otimes}a⊗0=0⊗a=0{\ Displaystyle a \ otimes 0 = 0 \ otimes a = 0}
• la relación ≤ es una relación de orden, es decir .a≤B∧B≤a⇒a=B{\ Displaystyle a \ leq b \ wedge b \ leq a \ Rightarrow a = b}

Si omitimos el último punto, la estructura definida es un medio anillo.

Terminología

El nombre de dioide proviene del hecho de que combina dos monoides, como cualquier medio anillo (especialmente cualquier anillo ). Este nombre fue utilizado por Jean Kuntzmann en 1972 para la estructura que ahora se llama medio anillo. El uso para denotar un subgrupo idempotente fue introducido por Baccelli et al. en 1992.

Tanto los dioides como los anillos son medios anillos, pero se excluyen mutuamente .

Dioide idempotente

El dioide idempotente es la clase de dioides más utilizada. Se caracteriza el hecho de que todo elemento es idempotente para , es decir que . a{\ Displaystyle a}⊕{\ Displaystyle \ oplus}a⊕a=a{\ Displaystyle a \ oplus a = a}

Por ejemplo, es un dioide idempotente. ([-∞,+∞[,max,+,-∞,0){\ Displaystyle ([- \ infty, + \ infty [, \ max, +, - \ infty, 0)}

Cualquier medio anillo idempotente es un dioide.

Demostración

Se trata de probar que la relación de preorden es un orden. Si entonces existe c tal que , por lo tanto 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}.

Del mismo modo, si entonces . Por lo tanto, si y , entonces usando la conmutatividad de obtenemos 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}.

Los medios anillos idempotentes son, por tanto, exactamente los dioides idempotentes.

Ver también

• Matemáticas tropicales

Notas y referencias

1. Jean Kuntzmann , Teoría de redes (gráficos) , París, Dunod,1972, xxiv + 288  pág. ( zbMATH  0239.05101 , SUDOC  002235358 ).
2. (en) Francois Baccelli, Guy Cohen, Geert Jan Olsder y Jean-Pierre Quadrat, Sincronización y linealidad: un álgebra para sistemas de eventos discretos , Chichester, Wiley, al.  "Serie de Wiley sobre probabilidad y estadística matemática",1992, xix + 489  pág. ( ISBN  0-471-93609-X , SUDOC  014487500 , leer en línea ).

Bibliografía

• Michel Gondran y Michel Minoux , Gráficos, dioides y semianillos: nuevos modelos y algoritmos , Paris, Tec & Doc,2001, xvi + 415  pág. ( ISBN  2-7430-0489-4 , SUDOC  060235101 )- Edición en inglés: (en) Michel Gondran y Michel Minoux , Graphs, Dioids and Semirings: New Models and Algorithms , Dordrecht, Springer Science & Business Media, coll.  "Serie de interfaces de investigación de operaciones / ciencias de la computación" ( n o  41)2008, 388  p. ( ISBN  978-0-387-75450-5 , zbMATH  1201.16038 , leer en línea )

• Michel Minoux, "  Álgebra lineal en semianillos y dioides  " [PDF] , en 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;">