monoide libre en un conjunto es el monoide cuyos elementos son todas las secuencias finitas (o cadenas) de cero o más elementos de ese conjunto, con la concatenación de cadenas como operación monoide y con la secuencia única de elementos cero, a menudo llamada la cadena vacía y denotada por ε o λ, como el elemento de identidad . El monoide libre en un conjunto A generalmente se denota como A ∗ . El semigrupo libre en A es el sub semigrupo de A *Contiene todos los elementos excepto la cadena vacía. Por lo general se denota A + . [1] [2]
Más generalmente, un monoide abstracto (o semigrupo) S se describe como libre si es isomorfo al monoide libre (o semigrupo) en algún conjunto. [3]
Como su nombre lo indica, los monoides y semigrupos libres son aquellos objetos que satisfacen la propiedad universal usual que define los objetos libres , en las categorías respectivas de monoides y semigrupos. De ello se deduce que cada monoide (o semigrupo) surge como una imagen homomórfica de un monoide (o semigrupo) libre. El estudio de los semigrupos como imágenes de semigrupos libres se denomina teoría de semigrupos combinatoria.
Ejemplos [ editar ]
Números naturales [ editar ]
El monoide ( N 0 , +) de los números naturales (incluido el cero) bajo adición es un monoide libre en un generador de singleton libre, en este caso el número natural 1. Según la definición formal, este monoide consta de todas las secuencias como "1 "," 1 + 1 "," 1 + 1 + 1 "," 1 + 1 + 1 + 1 ", etc., incluida la secuencia vacía. El mapeo de cada secuencia a su resultado de evaluación [4] y la secuencia vacía a cero establece un isomorfismo desde el conjunto de tales secuencias hasta N 0 . Este isomorfismo es compatible con "+", es decir, para cualquiera de las dos secuencias s y t , si s está mapeado (es decir,a n , entonces su concatenación s + t se asigna a la suma m + n .
Kleene estrella [ editar ]
En la teoría del lenguaje formal , generalmente se considera un conjunto finito de "símbolos" A (a veces llamado el alfabeto). Una secuencia finita de símbolos se llama "palabra sobre A ", y el monoide libre A ∗ se llama la " estrella Kleene de A ". Por lo tanto, el estudio abstracto de los lenguajes formales puede considerarse como el estudio de subconjuntos de monoides libres generados de manera definitiva. Hay conexiones profundas entre la teoría de los semigrupos y la de los autómatas . Por ejemplo, los lenguajes regulares sobre A son las pre-imágenes homomorfas en A ∗ de subconjuntos de monoides finitos. Elaclaración necesaria ]
Por ejemplo, suponiendo un alfabeto A = { a , b , c }, su estrella Kleene A ∗ contiene todas las concatenaciones de a , b y c :
- {ε, a , ab , ba , caa , cccbabbc , ...}.
Si A es un conjunto, la función de longitud de palabra en A ∗ es el homomorfismo monoide único de A ∗ a ( N 0 , +) que mapea cada elemento de A a 1. Un monoide libre es un monoide graduado . [ aclaración necesaria ] [5]
De manera más general, los lenguajes regulares sobre un alfabeto A son el cierre de los subconjuntos finitos de A *, el monoide libre sobre A, bajo unión, producto y generación de submonoides. [6]
Palabras conjugadas [ editar ]
Definimos un par de palabras en A ∗ de la forma uv y vu como conjugado : los conjugados de una palabra son, por lo tanto, sus desplazamientos circulares . [7] Dos palabras son conjugado en este sentido si son conjugado en el sentido de la teoría de grupos como elementos del grupo libre generado por A . [8]
Equidivisibilidad [ editar ]
Un monoide libre es equidivisible : si se cumple la ecuación mn = pq , entonces existe una s tal que m = ps , sn = q (ejemplo ver imagen) o ms= p , n = sq . [9] Este resultado también se conoce como el lema de Levi . [10]
Un monoide es gratis si y solo si es calificado y equidivisible. [9]
Generadores libres y rango [ editar ]
Los miembros de un conjunto A se denominan generadores libres para A ∗ y A + . El superíndice * se entiende comúnmente como la estrella Kleene . Más generalmente, si S es un monoide abstracto libre (semigrupo), entonces un conjunto de elementos que se asigna al conjunto de palabras de una sola letra bajo un isomorfismo a un semigrupo A + (monoide A ∗ ) se llama un conjunto de generadores libres para S .
Cada semigrupo libre (o monoide) S tiene exactamente un conjunto de generadores libres, la cardinalidad de los cuales se llama el rango de S .
Dos monoides o semigrupos libres son isomorfos si y solo si tienen el mismo rango. De hecho, cada conjunto de generadores para un semigrupo libre o monoide S contiene los generadores libres (consulte la definición de generadores en Monoid ) ya que un generador libre tiene la longitud de palabra 1 y, por lo tanto, solo se puede generar por sí mismo. De ello se deduce que un semigrupo o monoide libre se genera de manera finita si y solo si tiene rango finito.
A submonoide N de A * es estable si u , v , ux , xv en N junto implican x en N . [11] Un submonoide de A ∗ es estable si y solo si está libre. [12] Por ejemplo, usando el conjunto de bits {"0", "1"} como A , el conjunto N de todas las cadenas de bits que contienen uniformemente muchos "1" s es un submonoide estable porque si ucontiene un número par de " 1 "s, y ux también, entoncesx debe contener un número par de "1", también. Si bien N no puede generarse libremente por ningún conjunto de bits individuales, sí puede generarse libremente por el conjunto de cadenas de bits {"0", "11", "101", "1001", "10001", ...}.
Códigos [ editar ]
Un conjunto de generadores libres para un monoide P libre se conoce como una base para P : un conjunto de palabras C es un código si C * es un monoide libre y C es una base. [3] Un conjunto X de palabras en A ∗ es un prefijo , o tiene la propiedad de prefijo , si no contiene un prefijo (cadena) adecuado de cualquiera de sus elementos. Cada prefijo en A + es un código, de hecho un código de prefijo . [3] [13]
A submonoide N de A * es derecho unitario si x , xy en N implica y en N . Un submonoide es generado por un prefijo si y solo si es correcto unitario. [14]
Casco libre [ editar ]
La intersección de submonoides libres de un monoide A ∗ libre es nuevamente libre. [15] [16] Si S es un subconjunto de un monoide A * libre, entonces la intersección de todos los submonoides libres de A * que contiene S está bien definida, ya que A * en sí misma es libre y contiene S ; Es un monoide libre. A base de esta intersección es el casco libre de S .
El teorema de defectos [15] [16] [17] establece que si X es finito y C es el casco libre de X , entonces X es un código y C = X , o
- | C | ≤ | X | - 1.
Morfismos [ editar ]
Un morfismo monoide f de un monoide libre B ∗ a un monoide M es un mapa tal que f ( xy ) = f ( x ) ⋅ f ( y ) para las palabras x , y y f (ε) = ι, donde ε y ι Denota el elemento de identidad de B ∗ y M , respectivamente. El morfismo f está determinado por sus valores en las letras de B y, a la inversa, cualquier mapa de B a M seextiende a un morfismo. Un morfismo esno borrado [18] o continuo [19] si ninguna letra de B se asigna a ι y trivial si cada letra de B se asigna a ι. [20]
Un morfismo f de un monoide libre B ∗ a un monoide libre A ∗ es total si cada letra de A aparece en alguna palabra en la imagen de f ; cíclico [20] o periódico [21] si la imagen de f está contenida en { w } ∗ para alguna palabra w de A ∗ . Un morfismo f es k -uniforme si la longitud | f ( a ) | Es constante e igual a k para todos.una en una . [22] [23] Un morfismo de 1 uniforme es estrictamente alfabético [19] o una codificación . [24]
Un morfismo f de un monoide libre B ∗ a un monoide libre A ∗ es simplificable si hay un alfabeto C de cardinalidad menor que el de B, como el morfismo f factores a través de C ∗ , es decir, es la composición de un morfismo de B ∗ a C ∗ y un morfismo de eso a A ∗ ; de lo contrario f es elemental . El morfismo f se llama códigosi la imagen del alfabeto Bdebajo de f es un código: todo morfismo elemental es un código. [25]
Conjuntos de prueba [ editar ]
Para L un subconjunto de B * , un subconjunto finito T de L es un conjunto de prueba para L si morfismos f y g en B * de acuerdo en L si y sólo si están de acuerdo en T . La conjetura de Ehrenfeucht es que cualquier subconjunto L tiene un conjunto de prueba: [26] ha sido probado [27] independientemente por Albert y Lawrence; McNaughton; y Guba. Las pruebas se basan en el teorema de base de Hilbert . [28]
Endomorfismos [ editar ]
Un endomorfismo de A ∗ es un morfismo de A ∗ a sí mismo. [29] El mapa de identidad I es un endomorfismo de A ∗ , y los endomorfismos forman un monoide bajo la composición de funciones .
Un endomorfismo f es prolongable si hay una letra a tal que f ( a ) = como para una cadena s no vacía . [30]
Proyección de cadena [ editar ]
La operación de proyección de cuerdas es un endomorfismo. Es decir, dada una letra a ∈ Σ y una cadena s ∈ Σ ∗, la proyección de la cadena p a ( s ) elimina cada aparición de a desde s ; se define formalmente por
Tenga en cuenta que la proyección de cuerdas está bien definida incluso si el rango del monoide es infinito, ya que la definición recursiva anterior funciona para todas las cadenas de longitud finita. La proyección de cuerdas es un morfismo en la categoría de monoides libres, por lo que
dónde se entiende que es el monoide libre de todas las cadenas finitas que no contienen la letra a . El morfismo de identidad es., [ aclaración necesaria ] tan claramentepara todas las cadenas s . Por supuesto, se conmuta con la operación de concatenación de cadenas, de modo quepara todas las cadenas s y t . Hay muchos inversos correctos para la proyección de cuerdas, y por lo tanto es un epimorfismo dividido .
La proyección de cuerdas es conmutativa, como claramente
Para los monoides libres de rango finito, esto se deduce del hecho de que los monoides libres del mismo rango son isomorfos, ya que la proyección reduce el rango del monoide en uno.
para todas las cadenas s . Por lo tanto, la proyección es una operación conmutativa idempotente, y por lo tanto forma una semilattice limitada o una banda conmutativa .
Endomorfismos Sturmian [ editar ]
Un endomorfismo del monoide B ∗ libre en un alfabeto de 2 letras B es Sturmian si asigna cada palabra sturmiana una palabra sturmian [31] [32] y localmente a Sturmian si asigna alguna palabra sturmian a una palabra sturmian. [33] Los endomorfismos sturmianos forman un submonoide del monoide de endomorfismos de B ∗ . [31]
Define los endomorfismos φ y ψ de B ∗ , donde B = {0,1}, por φ (0) = 01, φ (1) = 0 y ψ (0) = 10, ψ (1) = 0. Entonces I , φ y ψ son Sturmian, [34] y los endomorfismos sturmianos de B ∗ son precisamente esos endomorfismos en el submonoide del monoom endomorfismo generado por { I , φ, ψ}. [32] [33] [35]
Una sustitución primitiva es Sturmian si la imagen de la palabra 10010010100101 está balanceada. [ aclaración necesaria ] [32] [36]
El monoide conmutativo libre [ editar ]
Dado un conjunto A , el monoide conmutativo libre en A es el conjunto de todos los conjuntos múltiples finitos con elementos extraídos de A , siendo la operación monoide la suma de conjuntos múltiples y la unidad monoidea el conjunto múltiple vacío.
Por ejemplo, si A = { a , b , c }, los elementos del monoide conmutativo libre en A son de la forma
- {ε, a , ab , a 2 b , ab 3 c 4 , ...}.
El teorema fundamental de los estados aritméticos de que el monoide de enteros positivos en la multiplicación es un monoide conmutativo libre en un conjunto infinito de generadores, los números primos .
El semigrupo conmutativo libre es el subconjunto del monoide conmutativo libre que contiene todos los conjuntos múltiples con elementos extraídos de A excepto el conjunto múltiple vacío.
Generalización [ editar ]
El monoide parcialmente conmutativo libre , o monoide traza , es una generalización que abarca tanto los monoides conmutativos libres como los casos. Esta generalización encuentra aplicaciones en combinatoria y en el estudio del paralelismo en informática .
Monoides y computación gratis [ editar ]
 |
Esta sección no cita ninguna fuente . ( Febrero de 2015 ) ( Aprenda cómo y cuándo eliminar este mensaje de plantilla )
|
El monoide libre en un conjunto A corresponde a listas de elementos de A con concatenación como operación binaria. Un homomorfismo monoide del monoide libre a cualquier otro monoide ( M , •) es una función f tal que
- f ( x 1 … x n ) = f ( x 1 ) •… • f ( x n )
- f () = e
donde e es la identidad en m . Desde el punto de vista informático, cada homomorfismo corresponde a una operación de mapa que aplica f a todos los elementos de una lista, seguida de una operación de plegado que combina los resultados utilizando el operador binario •. Este paradigma computacional (que puede generalizarse a operadores binarios no asociativos) ha inspirado el marco del software MapReduce .
las relaciones de Green son cinco relaciones de equivalencia que caracterizan los elementos de un semigrupo en términos de los principales ideales que generan. Las relaciones llevan el nombre de James Alexander Green , quien las presentó en un artículo de 1951. John Mackintosh Howie , un destacado teórico del semigrupo, describió este trabajo como "tan omnipresente que, al encontrarse con un nuevo semigrupo, casi la primera pregunta que se hace es '¿Cómo son las relaciones verdes?' "(Howie 2002). Las relaciones son útiles para comprender la naturaleza de la divisibilidad en un semigrupo; También son válidos para grupos., pero en este caso no nos dice nada útil, porque los grupos siempre tienen divisibilidad.
En lugar de trabajar directamente con un semigrupo S , es conveniente definir las relaciones de Green sobre el monoide S 1 . ( S 1 es " S con una identidad adjunta si es necesario"; si S no es ya un monoide, se adjunta un nuevo elemento y se define como una identidad). Esto garantiza que los ideales principales generados por algún elemento de semigrupo sí contienen ese elemento . Para un elemento a de S , los ideales relevantes son:
- El director ideal a izquierda generada por una :. Esto es lo mismo que, cual es .
- El director ideal justo generada por una :, o equivalente .
- El director ideales de dos caras generada por una :o .
Las relaciones L, R y J [ editar ]
Para los elementos a y b de S , las relaciones de Green L , R y J se definen por
- a L b si y solo si S 1 a = S 1 b .
- a R b si y solo si a S 1 = b S 1 .
- a J b si y solo si S 1 a S 1 = S 1 b S 1 .
Es decir, a y b están relacionados con L si generan el mismo ideal izquierdo; Relacionadas con R si generan el mismo derecho ideal; y J- relacionados si generan el mismo ideal de dos caras. Estas son relaciones de equivalencia en S , por lo que cada una de ellas produce una partición de S en clases de equivalencia. La clase Lde a se denota como L a (y de manera similar para las otras relaciones). Las clases L y las clases R pueden entenderse de manera equivalente como los componentes fuertemente conectados de los gráficos Cayleyizquierdo y derechode S 1 . [1] Además, las relaciones L , R y J definen tres preorden ≤ L , ≤ R y ≤ J , donde a ≤ J b se cumple para dos elementos a y b de S si la clase J de a está incluida en la de b , es decir, S 1 a S 1 ⊆ S 1 b S 1, y ≤ L y ≤R se definen de manera análoga. [2]
El verde usaba la letra negra en minúscula . , y Para estas relaciones, y escribí para un L b (y lo mismo para R y J ). Los matemáticos de hoy tienden a usar letras de guión comoen su lugar, y reemplace la notación de estilo aritmético modular de Green con el estilo de infijo utilizado aquí. Las letras ordinarias se utilizan para las clases de equivalencia.
Las relaciones L y R son de izquierda a derecha duales entre sí; los teoremas relativos a uno pueden traducirse en declaraciones similares sobre el otro. Por ejemplo, L es compatible derecha : si un L b y c es otro elemento de S , entonces ac L bc . Dualmente, R es compatible con la izquierda : si a R b , entonces ca R cb .
Si S es conmutativo, entonces L , R y J coinciden.
Las relaciones H y D [ editar ]
Las relaciones restantes se derivan de L y R . Su intersección es H :
- a H b si y solo si a L b y a R b .
Esto también es una relación de equivalencia en S . La clase H a es la intersección de L a y R a . Más generalmente, la intersección de cualquier clase L con cualquier clase R es una clase H o el conjunto vacío.
El teorema de Green establece que para cualquier H- clase H de un semigrupo S, ya sea (i) o (ii) y H es un subgrupo de S. Un corolario importante es que la clase de equivalencia H e , donde e es un idempotente , es un subgrupo de S (su identidad es e , y todos los elementos tienen inversos), y de hecho es el subgrupo más grande de S que contiene e . Ninguna clase H puede contener más de un idempotente, por lo tanto H es una separación idempotente . En un monoide M, H 1 es tradicionalmente llamado el grupo de unidades . [3](Tenga en cuenta que la unidad no significa identidad en este contexto, es decir, en general hay elementos de no identidad en H 1. La terminología de "unidad" proviene de la teoría de anillos .) Por ejemplo, en la transformación monoide en n elementos, T n , El grupo de unidades es el grupo simétrico S n .
Finalmente, se define D : a D b si y solo si existe una c en S tal que a L c y c R b . En el lenguaje de los enrejados , D es la unión de L y R . (La unión para relaciones de equivalencia es normalmente más difícil de definir, pero se simplifica en este caso por el hecho de que a L c y b R b para algunos c si y solo si a R d y d L bpara algunos d .)
Como D es la relación de equivalencia más pequeño que contiene tanto L y R , sabemos que una D b implica una J b - así J contiene D . En un semigrupo finito, D y J son lo mismo. [4] como también en un monoide racional . [5] [ aclaración necesaria ] Además, también coinciden en cualquier epigrupo . [6]
También hay una formulación de D en términos de clases de equivalencia, derivada directamente de la definición anterior: [7]
- a D b si y solo si la intersección de R a y L b no está vacía.
En consecuencia, las clases D de un semigrupo pueden verse como uniones de clases L , como uniones de clases R , o como uniones de clases H. Clifford y Preston (1961) sugieren pensar en esta situación en términos de una "caja de huevos": [8]
Cada fila de huevos representa una clase R , y cada columna una clase L ; Los huevos en sí mismos son las clases H. Para un grupo, solo hay un huevo, porque las cinco relaciones de Green coinciden y hacen que todos los elementos del grupo sean equivalentes. El caso opuesto, que se encuentra, por ejemplo, en el semigrupo bicíclico , es donde cada elemento se encuentra en una clase H propia. La caja de huevos para este semigrupo contendría un número infinito de huevos, pero todos los huevos están en la misma caja porque solo hay una clase D. (Un semigrupo para el que todos los elementos están relacionados con D se llama bisimple ).
Se puede mostrar que dentro de una clase D , todas las clases H son del mismo tamaño. Por ejemplo, el semigrupo de transformación T 4 contiene cuatro clases D , dentro de las cuales las clases H tienen 1, 2, 6 y 24 elementos respectivamente.
Los avances recientes en la combinatoria de semigrupos han usado las relaciones de Green para ayudar a enumerar semigrupos con ciertas propiedades. Un resultado típico (Satoh, Yama y Tokizawa, 1994) muestra que hay exactamente 1,843,120,128 semigrupos no equivalentes de orden 8, incluyendo 221,805 que son conmutativos; su trabajo se basa en una exploración sistemática de posibles clases de clase D. (Por el contrario, solo hay cinco grupos de orden 8 ).
Ejemplo [ editar ]
El semigrupo completo de transformación T 3 consta de todas las funciones desde el conjunto {1, 2, 3} hasta sí mismo; hay 27 de estos Escriba ( a b c ) para la función que envía 1 a a , 2 a b y 3 a c . Dado que T 3 contiene el mapa de identidad, (1 2 3), no hay necesidad de adjuntar una identidad.
El diagrama de la caja de huevos para T 3 tiene tres clases D. También son clases J , porque estas relaciones coinciden para un semigrupo finito.
| ||||||||||
| ||||||||||
|
En T 3 , dos funciones están relacionadas con L si y solo si tienen la misma imagen . Tales funciones aparecen en la misma columna de la tabla anterior. Del mismo modo, las funciones f y g están relacionadas con R si y solo si
- f ( x ) = f ( y ) ⇔ g ( x ) = g ( y )
para x e y en {1, 2, 3}; tales funciones están en la misma fila de la tabla. En consecuencia, dos funciones están relacionadas con D si y solo si sus imágenes son del mismo tamaño.
Los elementos en negrita son los idempotentes. Cualquier clase H que contenga uno de estos es un subgrupo (máximo). En particular, la tercera clase D es isomorfa al grupo simétrico S 3 . También hay seis subgrupos de orden 2 y tres de orden 1 (así como subgrupos de estos subgrupos). Seis elementos de T 3 no están en ningún subgrupo.
Generalizaciones [ editar ]
Hay esencialmente dos formas de generalizar una teoría algebraica. Una es cambiar sus definiciones para que cubra más o diferentes objetos; La otra forma, más sutil, es encontrar algún resultado deseable de la teoría y considerar formas alternativas de llegar a esa conclusión.
Siguiendo la primera ruta, se han definido versiones análogas de las relaciones de Green para semirings (Grillet 1970) y anillos (Petro 2002). Algunas, pero no todas, las propiedades asociadas con las relaciones en los semigrupos se transfieren a estos casos. Permaneciendo dentro del mundo de los semigrupos, las relaciones de Green pueden extenderse para cubrir ideales relativos , que son subconjuntos que solo son ideales con respecto a un sub-grupo (Wallace 1963).
Para el segundo tipo de generalización, los investigadores se han concentrado en las propiedades de las biyecciones entre las clases L y R. Si x R y , entonces siempre es posible encontrar bijectiones entre L x y L y que son preservación de clase R. (Es decir, si dos elementos de una clase L están en la misma clase R , entonces sus imágenes bajo una bijección aún estarán en la misma clase R. ) La declaración dual para x L ytambién sostiene. Estas bijections son traducciones a derecha e izquierda, restringidas a las clases de equivalencia apropiadas. La pregunta que surge es: ¿de qué otra manera podría haber tales bijections?
Supongamos que Λ y Ρ son semigroups de transformaciones parciales de algunos semigrupo S . Bajo ciertas condiciones, se puede mostrar que si x Ρ = y , con x ρ 1 = y y y ρ 2 = x , entonces las restricciones
- ρ 1 : Λ x → Λ y
- ρ 2 : Λ y → Λ x
Son biyectiones mutuamente inversas. (Convencionalmente, los argumentos se escriben a la derecha para Λ, y a la izquierda para Ρ.) Entonces las relaciones L y R pueden definirse por
- x L y si y solo si Λ x = Λ y
- x R y si y sólo si x Ρ = y Ρ
y D y H siguen como de costumbre. La generalización de J no es parte de este sistema, ya que no desempeña ningún papel en la propiedad deseada.
Llamamos (Λ, Ρ) un par de Green . Hay varias opciones de semigrupo de transformación parcial que producen las relaciones originales. Un ejemplo sería tomar Λ como el semigrupo de todas las traducciones a la izquierda en S 1 , restringido a S , y Ρ el semigrupo correspondiente de traducciones de derechos restringidos.
Estas definiciones se deben a Clark y Carruth (1980). Subsumen el trabajo de Wallace, así como varias otras definiciones generalizadas propuestas a mediados de los años setenta. Los axiomas completos son bastante largos de establecer; informalmente, los requisitos más importantes son que tanto Λ como Ρ deben contener la transformación de identidad, y que los elementos de Λ deben conmutar con los elementos de Ρ.
No hay comentarios:
Publicar un comentario