Meio anel

Em matemática , um meio-anel , ou semianel , é uma estrutura algébrica que tem as seguintes propriedades: (E,+,×,0,1){\ displaystyle (E, +, \ times, 0,1)}

• (E,+,0){\ displaystyle (E, +, 0)}constitui um monóide comutativo;
• (E,×,1){\ displaystyle (E, \ times, 1)}forma um monóide  ;
• ×{\ displaystyle \ times}é distributivo em relação a +;
• 0 é absorvente para o produto, ou seja: para tudo .x∈E:x×0=0×x=0{\ displaystyle x \ in E: x \ times 0 = 0 \ times x = 0}

Essas propriedades são semelhantes às de um anel , com a diferença de que não existem necessariamente inversos para a adição em um meio-anel.

Um meio anel é comutativo quando seu produto é comutativo; é idempotente quando sua adição é idempotente . Às vezes, distingue-se os semianéis e os semianéis unificados  : neste caso, a estrutura multiplicativa é apenas um meio-grupo , portanto não tem necessariamente um elemento neutro. Em geral, também pedimos isso . Meio anel que não tem necessariamente um elemento neutro para multiplicação é às vezes chamado de hemi-ring ( hemiring inglês). 0≠1{\ displaystyle 0 \ neq 1}

Ao contrário do que acontece com os anéis , não podemos provar que 0 é um elemento absorvente dos outros axiomas.

Áreas de aplicação

Meios anéis são freqüentemente encontrados em:

• pesquisa operacional  : gráficos ponderados têm pesos em meio-anel; o produto está associado à acumulação de valor ao longo de um caminho e a soma corresponde à forma de compor vários caminhos; o cálculo dos caminhos mais curtos é um exemplo particular.
• Teoria das linguagens e autômatos  : o produto é a concatenação de (conjuntos de) strings para fazer outras. A união de (conjuntos de) strings é a soma;
• teoria dos lugares: um lugar é uma rede distributiva completa  ; a categoria dos lugares generaliza a dos espaços topológicos .

Exemplos

Primeiros exemplos

• Os números naturais formam um meio-anel para a adição e multiplicação natural.
• Números naturais estendidos com adição e multiplicação estendidas e )NÃO∪{∞}{\ displaystyle \ mathbb {N} \ cup \ {\ infty \}}1=0⋅∞=0{\ displaystyle 1 = 0 \ cdot \ infty = 0}
• O meio-anel booleano composto de dois elementos 0 e 1. Esta é a álgebra booleana  : onde e são OR e AND respectivamente.({0,1},∨,∧,0,1){\ displaystyle (\ {0,1 \}, \ vee, \ wedge, 0,1)}∨{\ displaystyle \ vee}∧{\ displaystyle \ wedge}
• Em particular, uma álgebra booleana é um meio-anel. Um anel de Boole também é um meio anel - visto que é um anel - mas a adição não é idempotente. Um meio-anel booleano é um meio-anel isomórfico a um sub-meio-anel de uma álgebra booleana.
• Uma rede distributiva é um meio-anel comutativo e idempotente para as leis e .∨{\ displaystyle \ vee}∧{\ displaystyle \ wedge}
• Uma rede em um anel é um meio-anel idempotente para a multiplicação e a operação definida por .∇{\ displaystyle \ nabla}no∇b=no+b+bno-nobno-bnob{\ displaystyle a \ nabla b = a + b + ba-aba-bab}
• O conjunto de ideais em um anel forma um meio-anel para a adição e multiplicação de ideais.
• Os dióides são indivíduos de meio anel.
• O meio-anel de probabilidades são números reais não negativos com adição e multiplicação malsucedidas.
• O meio-anel log  (em) ligado com a adição dada porR∪{±∞}{\ displaystyle \ mathbb {R} \ cup \ {\ pm \ infty \}}

x⊕y=-registro⁡(e-x+e-y) ,{\ displaystyle x \ oplus y = - \ log (e ^ {- x} + e ^ {- y}) \,} e para multiplicação, elemento zero e unidade do elemento .+{\ displaystyle +}+∞{\ displaystyle + \ infty}0{\ displaystyle 0}

• O meio-anel Łukasiewicz é o intervalo fechado , com adição e multiplicação . Esse meio-anel aparece na lógica polivalente .[0,1]{\ displaystyle [0,1]}no+b=max(no,b){\ displaystyle a + b = \ max (a, b)}nob=max(0,no+b-1){\ displaystyle ab = \ max (0, a + b-1)}
• O meio-anel de Viterbi é definido no conjunto , com a adição dada pelo máximo e a multiplicação usual; ele aparece na análise de gramáticas probabilísticas .[0,1]{\ displaystyle [0,1]}

Exemplos gerais

• O conjunto de partes de um conjunto E fornecido com a união e a interseção é um meio-anel. As duas leis são distributivas entre si, o elemento neutro da união é o conjunto vazio, o da intersecção é o conjunto E. As duas leis são comutativas e formam com E os dois monóides requeridos. É uma álgebra booleana e, portanto, uma rede .
• O conjunto de relações binárias sobre um conjunto, com a adição dada pela união e a multiplicação pela composição das relações. O zero desse meio-anel é a relação vazia e seu elemento unitário a relação de identidade.
• O conjunto de linguagens formais em um determinado alfabeto é um meio-anel com a adição dada pela união e o produto pelo produto da concatenação dos elementos. O zero é o conjunto vazio, e a unidade o conjunto reduzido à palavra vazia.
• Mais geralmente, o conjunto de partes de um monóide, fornecido com a união e o produto das partes, é um meio-anel.você⋅V={você⋅v∣você∈você, v∈V}{\ displaystyle U \ cdot V = \ {u \ cdot v \ mid u \ in U, \ v \ in V \}}
• Da mesma forma, a família de partes de um monóide M com multiplicidades, isto é, somas formais de elementos de M com coeficientes inteiros naturais formam um meio-anel. Adição é a soma formal com adição de coeficientes, e a multiplicação é o produto de Cauchy. A soma zero é o elemento neutro para adição e o monômio formado a partir do elemento neutro de M é a unidade para multiplicação.

Meio anel tropical

• O conjunto de números naturais estendidos da maneira usual (qualquer soma com dá  ; qualquer produto com dá , exceto 0 que permanece absorvente) fornecido com o operador min e a soma é um meio-anel: é conhecido pelos nomes de ( min, +) - meio anel e meio anel tropical , assim chamado em homenagem ao seu promotor Imre Simon . A criação do adjetivo tropical é atribuída por Jean-Éric Pin a Dominique Perrin, enquanto o próprio Imre Simon o atribui a Christian Choffrut. O termo tropical se refere apenas às origens brasileiras, portanto trópicas, de Imre Simon. Essa estrutura embasa os algoritmos de cálculo do caminho mais curto em um gráfico: os pesos são somados ao longo dos caminhos e na frente de vários caminhos, tomamos o custo mínimo. Uma variante é o (max, +) - meio-anel, onde o máximo toma o lugar do mínimo . Ambos são meios anéis tropicais.∞{\ displaystyle \ infty}∞{\ displaystyle \ infty}∞{\ displaystyle \ infty}∞{\ displaystyle \ infty}∞{\ displaystyle \ infty}(NÃO∪{∞},min,+,∞,0){\ displaystyle (\ mathbb {N} \ cup \ {\ infty \}, \ min, +, \ infty, 0)}
• (NÃO∪{∞},max,min,0,∞){\ displaystyle (\ mathbb {N} \ cup \ {\ infty \}, \ max, \ min, 0, \ infty)} é o meio-anel subjacente ao cálculo do fluxo máximo de um gráfico: numa sequência de arcos, o de peso mínimo impõe o seu fluxo e diante de várias sequências, tomamos o fluxo máximo.

Transferência de estrutura

Por transferência de estrutura  :

• As matrizes quadradas de ordem n com entradas em um meio-anel e com a adição e a multiplicação induzidas; esse meio-anel geralmente não é comutativo, mesmo que o meio-anel de suas entradas seja.
• O conjunto End ( A ) dos endomorfismos de um monóide comutativo A é um meio-anel com, para adição, aquele induzido por A ( ) e para multiplicação a composição de funções . O morfismo nulo e a identidade são os elementos neutros.f+g(no)=f(no)+g(no){\ displaystyle f + g (a) = f (a) + g (a)}
• O conjunto de polinômios com coeficientes em um meio-anel S forma um meio-anel, comutativo se S for, idempotente se S for. Se S é o conjunto de inteiros naturais, é o meio-anel livre com gerador { x }.S[x]{\ displaystyle S [x]}

Meio-anel completo e contínuo

Um monóide completo é um monóide comutativo que tem uma operação de soma infinita para qualquer conjunto de índices e tal que as seguintes propriedades são válidas: ∑eu{\ displaystyle \ sum _ {I}}eu{\ displaystyle I}

∑eu∈∅meu=0;∑eu∈{j}meu=mj;∑eu∈{j,k}meu=mj+mkparaj≠k{\ displaystyle \ sum _ {i \ in \ emptyset} {m_ {i}} = 0; \ quad \ sum _ {i \ in \ {j \}} {m_ {i}} = m_ {j}; \ quad \ sum _ {i \ in \ {j, k \}} {m_ {i}} = m_ {j} + m_ {k} \ quad {\ textrm {para}} \; j \ neq k}

e

∑j∈J∑eu∈eujmeu=∑eu∈eu(meu)E se⋃j∈Jeuj=eueeuj∩euj′=∅paraj≠j′{\ displaystyle \ sum _ {j \ in J} {\ sum _ {i \ in I_ {j}} {m_ {i}}} = \ sum _ {i \ in I} (m_ {i}) \; {\ textrm {si}} \ bigcup _ {j \ in J} I_ {j} = I \; {\ textrm {and}} \; I_ {j} \ cap I_ {j '} = \ emptyset \; { \ textrm {para}} \; j \ neq j '}

Um monóide contínuo é um monóide ordenado para o qual qualquer conjunto ordenado de filtragem tem um limite superior que, além disso, é compatível com a operação monóide:

no+e aíS=e aí(no+S) .{\ displaystyle a + \ sup S = \ sup (a + S) \.}

Os dois conceitos estão intimamente relacionados: um monóide contínuo é completo, a soma infinita pode de fato ser definida por:

∑eunoeu=e aí∑Enoeu{\ displaystyle \ sum _ {I} a_ {i} = \ sup \ sum _ {E} a_ {i}}

onde o "sup" é obtido em todos os subconjuntos finitos E de I e cada soma, no membro certo, portanto, se relaciona a um conjunto finito.

Um meio-anel completo é um meio-anel para o qual o monóide aditivo é um monóide completo, e que satisfaz as seguintes leis distributivas infinitas:

∑eu∈eu(no⋅noeu)=no⋅(∑eu∈eunoeu){\ displaystyle \ sum _ {i \ in I} {(a \ cdot a_ {i})} = a \ cdot {\ bigl (} \ sum _ {i \ in I} {a_ {i}} {\ bigl )}}   e   .∑eu∈eu(noeu⋅no)=(∑eu∈eunoeu)⋅no{\ displaystyle \ sum _ {i \ in I} {(a_ {i} \ cdot a)} = {\ bigl (} \ sum _ {i \ in I} {a_ {i}} {\ bigl)} \ cdot a}

Um exemplo de meio-anel completo é o conjunto de partes de um monóide para a união; o meio-anel da entrada morre em um meio-anel completo é ele próprio um meio-anel completo.

Um meio-anel contínuo é um monóide contínuo cuja multiplicação respeita a ordem e os limites superiores. O meio-anel N ∪ {∞} com adição, multiplicação e a ordem natural é um meio-anel contínuo.

Qualquer meio-anel contínuo está completo e esta propriedade pode ser incluída na definição.

Meio-anel estrelado

Um semi-anel estrela (em inglês star semiring ou starsemiring é um meio-anel fornecido com um operador unário adicional anotado como "*" satisfatório:

no∗=1+nono∗=1+no∗no.{\ displaystyle a ^ {*} = 1 + aa ^ {*} = 1 + a ^ {*} a.}

Exemplos de meias argolas em estrela:

• O meio-anel de Boole com 0 ∗ = 1 ∗ = 1 ;
• O meio-anel das relações binárias em um conjunto U , onde a estrela de uma relação R é definida por

R∗=⋃não≥0Rnão{\ displaystyle R ^ {*} = \ bigcup _ {n \ geq 0} R ^ {n}}. Este é o fecho reflexivo e transitória da relação R .

• O meio anel das linguagens formais é um anel de meia estrela completo, com a operação estrela sendo a estrela de Kleene .
• O conjunto de números reais positivos aumentados por ∞, com a adição e multiplicação usuais é um meio-anel estrela completo com a operação estrela dada por a ∗ = 1 / (1 - a ) para 0 ≤ a <1 (a série geométrica usual ) e a ∗ = ∞ para a ≥ 1 .
• O meio-anel N ∪ {∞}, com adição e multiplicação estendidas, e 0 ∗ = 1 , a ∗ = ∞ para a ≥ 1 .

Álgebra de Kleene

Uma álgebra de Kleene é um meio-anel estrelado com adição idempotente; eles estão envolvidos na teoria da linguagem e em expressões regulares .

Half Conway Ring

Um meio-anel de Conway é um meio-anel em forma de estrela que satisfaz as seguintes equações entre a operação estrela e adição e multiplicação:

(no+b)∗=(no∗b)∗no∗,{\ displaystyle (a + b) ^ {*} = (a ^ {*} b) ^ {*} a ^ {*}, \,} (nob)∗=1+no(bno)∗b.{\ displaystyle (ab) ^ {*} = 1 + a (ba) ^ {*} b. \,}

Os primeiros três exemplos acima também são anéis de meio Conway.

Meio-anel iterativo

Um meio-anel iterativo ( semiragem de iteração em inglês ) Conway é um meio-anel do qual verifica grupos de axiomas de Conway associados por grupos de John Conway nos meios-anéis estrelados

Estrela cheia meio anel

Um meio-anel de estrela cheia é um meio-anel em que a estrela tem as propriedades usuais da estrela de Kleene  ; nós o definimos usando o operador de soma infinita por:

no∗=∑j≥0noj{\ displaystyle a ^ {*} = \ sum _ {j \ geq 0} {a ^ {j}}}

com e para . no0=1{\ displaystyle a ^ {0} = 1}noj+1=no⋅noj=noj⋅no{\ displaystyle a ^ {j + 1} = a \ cdot a ^ {j} = a ^ {j} \ cdot a}j≥0{\ displaystyle j \ geq 0}

Os meios-anéis de relações binárias, linguagens formais e números reais não negativos estendidos são totalmente marcados com estrelas.

Um anel de meia estrela completo também é um anel de meio Conway, mas o contrário não é verdade. Um exemplo é fornecido pelos números racionais não negativos estendidos com a adição e multilicação usuais. {x∈Q∣x≥0}∪{∞}{\ displaystyle \ {x \ in \ mathbb {Q} \ mid x \ geq 0 \} \ cup \ {\ infty \}}

Notas e referências

1. Golan 1999 , p.  1
2. Sakarovich 2009 , p.  28
3. Alexander E. Guterman, "Rank and determinant functions for matrices over semirings" , em Nicholas Young e Yemon Choi (eds), Surveys in Contemporary Mathematics , Cambridge University Press , col.  "London Mathematical Society Nota Tocar Series" ( n o  347)2008( ISBN  0-521-70564-9 , zbMATH  1181.16042 ) , p.  1–33.
4. Lothaire 2005 , p.  211.
5. Claude Pair, "Sobre algoritmos para problemas de fluxo em grafos finitos" , em P. Rosentiehl, Théorie des graphes (dias de estudo internacionais) - Teoria dos Grafos (simpósio internacional) , Dunod (Paris) e Gordon e Breach (Novo Iorque),1966
6. Droste e Kuich 2009 , p.  7-10.
7. Berstel e Reutenauer 2011 , p.  4
8. Jean-Éric Pin, “Tropical Semirings” , em J. Gunawardena, Idempotency (Bristol, 1994) , Cambridge, Cambridge University Press, col.  "Publ. Newton Inst. 11  ”, 1998, p.  50-69 .
9. Imre Simon, “Recognizable sets with multiplicities in the tropical semiring” , in Mathematical Foundations of Computer Science (Carlsbad, 1988) , Springer, coll.  "Lecture Notes in Computer Science" ( n S  324), 1988( leia online ) , p.  107-120.
10. Mathoverflow, 2011, O que é tropical sobre álgebra tropical? no Mathoverflow
11. Udo Hebisch , "  Eine algebraische Theorie unendlicher Summen mit Anwendungen auf Halbgruppen und Halbringe  ", Bayreuther Mathematische Schriften , vol.  40,1992, p.  21–152 ( zbMATH  0747.08005 )
12. Werner Kuich , “semirings w-contínuo, sistemas algébricos e autômatos pushdown” , em Michael S. Paterson (editor), Autômatos, Linguagens e Programação (17º Colóquio Internacional, Universidade de Warwick, Inglaterra, 16-20 julho , 1990) , Springer-Verlag , col.  "Lecture Notes in Computer Science" ( n S  443), 1990( ISBN  3-540-52826-1 ) , p.  103-110
13. Kuich 2011 .
14. Sakarovitch 2009 , p.  471.
15. Zoltán Ésik e Hans Leiß , "Greibach normal form in algebraically complete semirings" , em Julian Bradfield, Computer Science Logic (16º workshop internacional, CSL 2002, 11ª conferência anual da EACSL, Edimburgo, Escócia, 22 a 25 de setembro de 2002) , Berlin, Springer-Verlag , col.  "Lecture Notes in Computer Science" ( n o  2471), 2002( zbMATH  1020.68056 ) , p.  135-150.
16. Esik 2008 .
17. Daniel J. Lehmann, "  Estruturas algébricas para fechamento transitivo  ", Theoretical Computer Science , vol.  4, n o  1,1977, p.  59-76.
18. Berstel e Reutenauer 2011 , p.  27
19. Esik e Kuich 2004 .
20. John H. Conway , Regular algebra and finite machines , London, Chapman and Hall,1971( ISBN  0-412-10620-5 , zbMATH  0231.94041 )
21. Droste e Kuich 2009 , Teorema 3.4 p.  15 .

Bibliografia

• Claude Pair, "On algorítmos para problemas de fluxo em grafos finitos" , em P. Rosentiehl, Théorie des graphes (dias de estudo internacionais) - Theory of Graphs (internainal symposium) , Dunod (Paris) e Gordon and Breach (New York),1966
• Jean Claude Derniame e Claude Pair, Problemas de progressão em gráficos , Dunod (Paris),1971, 182  p.
• Kazimierz Głazek , Um guia para a literatura sobre seminários e suas aplicações em matemática e ciências da informação. Com bibliografia completa , Dordrecht, Kluwer Academic,2002( ISBN  1-4020-0717-5 , zbMATH  1072.16040 )
• Jonathan S. Golan, Semirings and their Applications , Dordrecht, Kluwer Academic Publishers (Springer Science & Business Media),1999, xii + 381  pág. ( ISBN  978-0-7923-5786-5 , Math Reviews  1746739 , leia online )- Edição revista e expandida (in) A teoria dos semirings, com aplicações para matemática e ciência da computação teórica , Harlow, Longman Scientific & Technical e John Wiley & Sons, al.  "Pitman Monographs and Surveys in Pure and Applied Mathematics",1992, xiv + 318  pág. ( ISBN  0-582-07855-5 , Math Reviews  1163371 )
• (en) M. Lothaire , Aplicada combinatória em palavras , Cambridge (GB), Cambridge University Press , col.  "Enciclopédia de Matemática e suas Aplicações" ( n o  105)2005, 610  p. ( ISBN  978-0-521-84802-2 , zbMATH  1133.68067 , leia online )
• Michel Gondran e Michel Minoux , Gráficos, dióides e semi-anéis: novos modelos e algoritmos , Paris, Tec & Doc,2001, xvi + 415  p. ( ISBN  2-7430-0489-4 , SUDOC  060235101 )- Edição em inglês: (en) Michel Gondran e Michel Minoux , Graphs, Dioids and Semirings: New Models and Algorithms , Dordrecht, Springer Science & Business Media, col.  "Pesquisa Operacional / Computer Science Interfaces Series" ( n o  41)2008, xix + 383  pág. ( ISBN  978-0-387-75450-5 , zbMATH  1.201,16038 , SUDOC  12874958X , lido online )
• (pt) Jacques Sakarovitch , Elementos da teoria dos autômatos (traduzido do francês por Reuben Thomas) , Cambridge, Cambridge University Press ,2009, 758  p. ( ISBN  978-0-521-84425-3 , zbMATH  1188.68177 )
• Manfred Droste e Werner Kuich, "Semirings and Formal Power Series" , em Manfred Droste, Werner Kuich, Heiko Vogler (eds), Handbook of Weighted Automata , Springer-Verlag,2009( DOI  10.1007 / 978-3-642-01492-5_1 ) , p.  3-29
• Zoltán Ésik , “Iteration semirings” , em Masami Ito (editor), Developments in language theory (12ª conferência internacional, DLT 2008, Kyoto, Japão, 16–19 de setembro de 2008) . , Berlin, Springer-Verlag , col.  "Lecture Notes in Computer Science" ( n o  5257)2008( ISBN  978-3-540-85779-2 , DOI  10.1007 / 978-3-540-85780-8_1 , zbMATH  1161.68598 ) , p.  1-20
• Zoltán Ésik e Werner Kuich , “ Axiomas equacionais para uma teoria dos autômatos” , em Carlos Martín-Vide, Linguagens formais e aplicações , Berlin, Springer-Verlag , col.  "Estudos em Difusão e macia Computing" ( n o  148),2004( ISBN  3-540-20907-7 , zbMATH  1088.68117 ) , p.  183–196
• Werner Kuich , “Algebraic systems and pushdown automata” , em Werner Kuich, Algebraic foundations in computer science. Ensaios dedicados a Symeon Bozapalidis por ocasião de sua aposentadoria , Berlin, Springer-Verlag , col.  "Lecture Notes in Computer Science" ( n o  7020)2011( ISBN  978-3-642-24896-2 , zbMATH  1251.68135 ) , p.  228-256.

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">