MATEMÁTICAS - LISTA DE TEMAS DE ÁLGEBRA ABSTRACTA

 monoide (u objeto monoide ) ( M , μ, η) en una categoría monoidal ( C , ⊗, I ) es un objeto M junto con dos morfismos

• μ: M ⊗ M → M llamada multiplicación ,
• η: I → M unidad llamada ,

tal que el diagrama del pentágono

y el diagrama de unitor

conmutar. En las notaciones anteriores, I es el elemento unitario y α, λ y ρ son, respectivamente, la asociatividad, la identidad izquierda y la identidad derecha de la categoría C monoidal .

Dualmente, un comonoide en una categoría monoidal C es un monoide en la categoría doble C ^op .

Supongamos que la categoría monoidal C tiene una simetría γ. Un monoide M en C es conmutativo cuando μ oγ = μ.

Ejemplos [ editar ]

• Un objeto monoide en Set , la categoría de conjuntos (con la estructura monoidal inducida por el producto cartesiano), es un monoide en el sentido habitual.
• Un objeto monoide en Top , la categoría de espacios topológicos (con la estructura monoidal inducida por la topología del producto ), es un monoide topológico .
• Un objeto monoide en la categoría de monoides (con el producto directo de monoides) es solo un monoide conmutativo . Esto se desprende fácilmente del teorema de Eckmann-Hilton .
• Un objeto monoid en la categoría de completa Join-semiretículo Sup (con la estructura monoidal inducido por el producto cartesiano) es un unital quantale .
• Un objeto monoide en ( Ab , ⊗ _Z ,  Z ), la categoría de grupos abelianos , es un anillo .
• Para un anillo conmutativo R , un objeto monoide en
  • ( R - Mod , ⊗ _R ,  R ), la categoría de módulos sobre R , es una R - álgebra .
  • La categoría de módulos graduados es un R-álgebra graduada .
  • La categoría de complejos de cadenas es un dg-algebra .
• Un objeto monoid en K - Vect , la categoría de los espacios vectoriales (de nuevo, con el producto tensorial), es un K - álgebra , y un objeto comonoid es un K - coalgebra .
• Para cualquier categoría C , la categoría [ C , C ] de sus endofunctors tiene una estructura monoidal inducida por la composición y el funtor identidad I _C . Un objeto monoid en [ C , C ] es una mónada en C .
• Para cualquier categoría con productos finitos , cada objeto se convierte en un objeto comonoide a través del morfismo diagonal$${\ displaystyle \ Delta _ {X}: X \ a X \ veces X}. Dualmente, en una categoría con coproductos finitos, cada objeto se convierte en un objeto monoide a través de$${\ displaystyle id_ {X} \ sqcup id_ {X}: X \ sqcup X \ to X}.

Categorías de monoides [ editar ]

Dados dos monoides ( M , μ, η) y ( M ', μ', η ') en una categoría monoidal C , un morfismo f  : M → M ' es un morfismo de los monoides cuando

• f o μ = μ ' o ( f ⊗ f ),
• f o η = η '.

En otras palabras, los siguientes diagramas.

, 

conmutar.

La categoría de monoides en C y sus morfismos monoides está escrito Lu _C .

 factorización de un monoide libre es una secuencia de subconjuntos de palabras con la propiedad de que cada palabra en el monoide libre puede escribirse como una concatenación de elementos extraídos de los subconjuntos. El teorema de Chen-Fox-Lyndon establece que las palabras de Lyndonproporcionan una factorización. El teorema de Schützenberger relaciona la definición en términos de una propiedad multiplicativa con una propiedad aditiva.

Deje A ^* sea el monoide libre en un alfabeto A . Sea X _i una secuencia de subconjuntos de A ^* indexados por un conjunto de índices I totalmente ordenado . Una factorización de una palabra w en A ^* es una expresión

$${\ displaystyle w = x_ {i_ {1}} x_ {i_ {2}} \ cdots x_ {i_ {n}} \}

con $${\ displaystyle x_ {i_ {j}} \ en X_ {i_ {j}}} y $${\ displaystyle i_ {1} \ geq i_ {2} \ geq \ ldots \ geq i_ {n}}.

Teorema de Chen-Fox-Lyndon [ editar ]

Una palabra de Lyndon sobre un alfabeto totalmente ordenado A es una palabra que es lexicográficamentemenor que todas sus rotaciones. ^[1] El teorema de Chen-Fox-Lyndon establece que cada cadena puede formarse de una manera única al concatenar una secuencia no creciente de palabras de Lyndon. Por lo tanto, si X _l es el conjunto único { l } de cada palabra de Lyndon l , con el conjunto de índices L de las palabras de Lyndon ordenadas lexicográficamente, obtenemos una factorización de A ^* . ^[2] Tal factorización se puede encontrar en el tiempo lineal. ^[3]

Bisección [ editar ]

Una bisección de un monoide libre es una factorización con solo dos clases X ₀ , X ₁ . ^[4]

Ejemplos:

A = { a , b }, X ₀ = { a ^* b }, X ₁ = { a }.

Si X , Y son conjuntos separados de palabras no vacías, entonces ( X , Y ) es una bisección de A * si y solo si ^[5]

$${\ displaystyle YX \ cup A = X \ cup Y \.}

Como consecuencia, para cualquier partición P , Q de A ⁺ hay una bisección único ( X , Y ) con X un subconjunto de P y Y un subconjunto de Q . ^[6]

Schützenberger teorema [ editar ]

Este teorema establece que una secuencia X _i de subconjuntos de A ^* forma una factorización si y solo si se cumplen dos de las siguientes tres afirmaciones:

• Cada elemento de A ^* tiene al menos una expresión en la forma requerida;
• Cada elemento de A ^* tiene como máximo una expresión en la forma requerida;
• Cada conjugado de clase C cumple solo con uno de los monoides M _i = X _i * y los elementos de C en M _iestán conjugados en M _i .

monoide sintáctica M ( L ) de un lenguaje formal L es la más pequeña monoid que reconoce el lenguaje L .

Cociente sintáctico [ editar ]

El monoide libre en un conjunto dado es el monoide cuyos elementos son todas las cadenas de cero o más elementos de ese conjunto, con la concatenación de cadenas como la operación monoides y la cadena vacíacomo el elemento de identidad . Dado un subconjunto $${\ displaystyle S} de un monoide libre $${\ displaystyle M}, uno puede definir conjuntos que consisten en inversos formales de izquierda o derecha de elementos en$${\ displaystyle S}. Estos se llaman cocientes , y uno puede definir cocientes derecho o izquierdo, dependiendo de qué lado se está concatenando. Así, el cociente correcto de$${\ displaystyle S} por un elemento $${\ displaystyle m} desde $${\ displaystyle M} es el conjunto

$${\ displaystyle S \ / \ m = \ {u \ en M \; \ vert \; um \ en S \}.}

Del mismo modo, el cociente de la izquierda es

$${\ displaystyle m \ setminus S = \ {u \ en M \; \ vert \; mu \ en S \}.}

Equivalencia sintáctica [ editar ]

El cociente sintáctico induce una relación de equivalencia en M , llamada relación sintáctica , o equivalencia sintáctica (inducida por S ). La equivalencia sintáctica correcta es la relación de equivalencia.

$${\ displaystyle \ sim _ {S} \; = \ {(s, t) \ in M ​​\ times M \, \ vert \; S \ / \ s = S \ / \ t \}.}

Del mismo modo, la relación sintáctica izquierda es.

$${\ displaystyle \, _ {S} \ sim \; = \ {(s, t) \ in M ​​\ times M \, \ vert \; s \ setminus S = t \ setminus S \}.}

La congruencia sintáctica o Myhill congruencia ^[1] puede definirse como ^[2]

$${\ displaystyle s \ equiv _ {S} t \ Leftrightarrow \ forall x, y \ en M (xsy \ en S \ Leftrightarrow xty \ en S).}

La definición se extiende a una congruencia definida por un subconjunto S de un monoid general M . Un conjunto disyuntivo es un subconjunto S tal que la congruencia sintáctica definida por S es la relación de igualdad. ^[3]

Llamemos $${\ displaystyle [s] _ {S}} la clase de equivalencia de $${\ displaystyle s}Por la congruencia sintáctica. La congruencia sintáctica es compatible con la concatenación en el monoide, ya que uno tiene

$${\ displaystyle [s] _ {S} [t] _ {S} = [st] _ {S}}

para todos $${\ displaystyle s, t \ en M}. Por lo tanto, el cociente sintáctico es un morfismo monoide , e induce un monoide cociente

$${\ displaystyle M (S) = M \ / \ {\ equiv _ {S}}.}

Este monoide $${\ displaystyle M (S)}se llama la monoid sintáctica de S . Se puede demostrar que es el monoide más pequeño el que reconoce S ; es decir, M ( S ) reconoce S , y por cada monoid N reconociendo S , M ( S ) es un cociente de un submonoide de N . El monoid sintáctica de S es también la monoid transición del autómata mínimo de S . ^{[1] [2] [4]}

De manera similar, un idioma L es regular si y solo si la familia de cocientes

$${\ displaystyle \ {m \ setminus L \, \ vert \; m \ in M ​​\}}

es finito ^[1] La prueba que muestra la equivalencia es bastante fácil. Suponga que una cadena x es leída por un autómata finito determinista , con la máquina avanzando al estado p . Si y es otra cadena leída por la máquina, que también termina en el mismo estado p , entonces claramente uno tiene$${\ displaystyle x \ setminus L \, = y \ setminus L}. Así, el número de elementos en$${\ displaystyle \ {m \ setminus L \, \ vert \; m \ in M ​​\}} a lo sumo es igual al número de estados del autómata y $${\ displaystyle \ {m \ setminus L \, \ vert \; m \ in L \}}es a lo sumo el número de estados finales. Supongamos, a la inversa, que el número de elementos en$${\ displaystyle \ {m \ setminus L \, \ vert \; m \ in M ​​\}}es finito Entonces se puede construir un autómata donde$${\ displaystyle Q = \ {m \ setminus L \, \ vert \; m \ en M \}} es el conjunto de estados, $${\ displaystyle F = \ {m \ setminus L \, \ vert \; m \ in L \}}es el conjunto de estados finales, el lenguaje L es el estado inicial y la función de transición viene dada por$${\ displaystyle y \ setminus (x \ setminus L) = (xy) \ setminus L}. Claramente, este autómata reconoce L . Así, un idioma L es reconocible si y solo si el conjunto$${\ displaystyle \ {m \ setminus L \, \ vert \; m \ in M ​​\}}es finito Tenga en cuenta que esta prueba también construye el autómata mínimo.

Dada una expresión regular E que representa S , es fácil calcular el monoide sintáctica de S .

Un lenguaje grupal es aquel para el cual el monoide sintáctico es un grupo . ^[5]

Ejemplos [ editar ]

• Sea L el lenguaje sobre A = { a , b } de palabras de longitud uniforme. La congruencia sintáctica tiene dos clases, L en sí y L ₁ , las palabras de longitud impar. El monoide sintáctico es el grupo de orden 2 en { L , L ₁}. ^[6]
• El monoide bicíclico es el monoide sintáctico del lenguaje Dyck (el lenguaje de conjuntos equilibrados de paréntesis).
• El monoide libre en A (| A |> 1) es el monoide sintáctico del lenguaje { ww ^R | w en A *}, donde w ^R denota la inversión de la palabra w .
• Cada monoide finito es homomorfo ^{[ clarificación necesaria ]} al monoid sintáctico de algún lenguaje no trivial, ^[7]pero no todo monoid finito es isomorfo a un monoide sintáctico. ^[8]
• Cada grupo finito es isomorfo al monoide sintáctico de algún lenguaje no trivial. ^[7]
• El lenguaje sobre { a , b } en el que el número de apariciones de a y b son congruentes módulo 2 ⁿ es un lenguaje grupal con monoide sintáctico Z / 2 ⁿ . ^[5]
• Los monoides traza son ejemplos de monoides sintácticos.
• Marcel-Paul Schützenberger ^[9] caracterizó a los idiomas sin estrellas como aquellos con monoides sintácticos aperiódicos finitos .