En álgebra abstracta , el monoide libre de 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 la operación del monoide y con la secuencia única de cero elementos, a menudo llamada la cadena vacía y denotada por ε o λ, como el elemento identidad . El monoide libre de un conjunto A se denota generalmente A ∗ . El semigrupo libre de A es el subsemigrupo de A ∗ que contiene todos los elementos excepto la cadena vacía. Se denota generalmente A + . [1] [2]
De manera más general, 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 a los objetos libres , en las respectivas categorías 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 combinatoria de semigrupos.
Los monoides libres (y los monoides en general) son asociativos por definición, es decir, se escriben sin paréntesis para indicar la agrupación o el orden de operación. El equivalente no asociativo es el magma libre .
El monoide ( N 0 ,+) de números naturales (incluido el cero) bajo adición es un monoide libre en un generador libre singleton, en este caso el número natural 1. Según la definición formal, este monoide consiste en todas las secuencias como "1", "1+1", "1+1+1", "1+1+1+1", y así sucesivamente, incluida la secuencia vacía. Asignar cada una de estas secuencias a su resultado de evaluación [4] y la secuencia vacía a cero establece un isomorfismo del conjunto de tales secuencias a N 0 . Este isomorfismo es compatible con "+", es decir, para dos secuencias cualesquiera s y t , si s se asigna (es decir, se evalúa) a un número m y t a n , entonces su concatenación s + t se asigna a la suma m + n .
En la teoría de los lenguajes formales , se considera habitualmente un conjunto finito de "símbolos" A (a veces llamado alfabeto ). Una secuencia finita de símbolos se denomina "palabra sobre A ", y el monoide libre A ∗ se denomina " estrella de Kleene de A ". Por tanto, el estudio abstracto de los lenguajes formales puede considerarse como el estudio de subconjuntos de monoides libres finitamente generados.
Por ejemplo, suponiendo un alfabeto A = { a , b , c }, su estrella de Kleene A ∗ contiene todas las concatenaciones de a , b y c :
Si A es un conjunto cualquiera, la función de longitud de palabra en A ∗ es el único homomorfismo de monoide de A ∗ a ( N 0 ,+) que asigna cada elemento de A a 1. Un monoide libre es, por tanto, un monoide graduado . [5] (Un monoide graduado es un monoide que se puede escribir como . Cada uno es un grado; la graduación aquí es simplemente la longitud de la cadena. Es decir, contiene aquellas cadenas de longitud El símbolo aquí puede tomarse como "unión de conjuntos"; se utiliza en lugar del símbolo porque, en general, las uniones de conjuntos podrían no ser monoides, y por eso se utiliza un símbolo distinto. Por convención, las gradaciones siempre se escriben con el símbolo).
Existen profundas conexiones entre la teoría de semigrupos y la de autómatas . Por ejemplo, cada lenguaje formal tiene un monoide sintáctico que reconoce ese lenguaje. Para el caso de un lenguaje regular , ese monoide es isomorfo al monoide de transición asociado al semiautómata de algún autómata finito determinista que reconoce ese lenguaje. Los lenguajes regulares sobre un alfabeto A son la clausura de los subconjuntos finitos de A*, el monoide libre sobre A, bajo unión, producto y generación de submonoide. [6]
En el caso de computación concurrente , es decir, sistemas con bloqueos , mutexes o uniones de subprocesos , la computación se puede describir con monoides de historial y monoides de seguimiento . En términos generales, los elementos del monoide pueden conmutar (por ejemplo, diferentes subprocesos pueden ejecutarse en cualquier orden), pero solo hasta un bloqueo o mutex, que evitan una mayor conmutación (por ejemplo, serializar el acceso del subproceso a algún objeto).
Definimos un par de palabras en A ∗ de la forma uv y vu como conjugadas : los conjugados de una palabra son, por tanto, sus desplazamientos circulares . [7] Dos palabras son conjugadas en este sentido si son conjugadas en el sentido de la teoría de grupos como elementos del grupo libre generado por A. [8]
Un monoide libre es equidivisible : si se cumple la ecuación mn = pq , entonces existe un s tal que m = ps , sn = q (véase el ejemplo en la imagen) o ms = p , n = sq . [9] Este resultado también se conoce como lema de Levi . [10]
Un monoide es libre si y sólo si está graduado (en el sentido fuerte de que sólo la identidad tiene gradación 0) y es equidivisible. [9]
Los miembros de un conjunto A se denominan generadores libres de A ∗ y A + . El superíndice * se entiende entonces comúnmente como la estrella de Kleene . De manera más general, si S es un monoide libre abstracto (semigrupo), entonces un conjunto de elementos que se mapea sobre el conjunto de palabras de una sola letra bajo un isomorfismo a un monoide A ∗ (semigrupo A + ) se denomina conjunto de generadores libres de S .
Cada monoide libre (o semigrupo) S tiene exactamente un conjunto de generadores libres, cuya cardinalidad se denomina 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 monoide o semigrupo libre S contiene los generadores libres, ya que un generador libre tiene una longitud de palabra de 1 y, por lo tanto, solo puede generarse por sí mismo. De ello se deduce que un semigrupo o monoide libre se genera finitamente si y solo si tiene un rango finito.
Un submonoide N de A ∗ es estable si u , v , ux , xv en N juntos implican x en N . [11] Un submonoide de A ∗ es estable si y solo si es libre. [12] Por ejemplo, usando el conjunto de bits { "0", "1" } como A , el conjunto N de todas las cadenas de bits que contienen un número par de "1" es un submonoide estable porque si u contiene un número par de "1" y ux también, entonces x debe contener un número par de "1" también. Si bien N no puede generarse libremente mediante ningún conjunto de bits individuales, puede generarse libremente mediante el conjunto de cadenas de bits { "0", "11", "101", "1001", "10001", ... } – el conjunto de cadenas de la forma "10 n 1" para algún entero no negativo n (junto con la cadena "0").
Un conjunto de generadores libres para un monoide libre P se denomina 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 propio (cadena) de ninguno de sus elementos. Cada prefijo en A + es un código, de hecho un código de prefijo . [3] [13]
Un submonoide N de A ∗ es unitario recto si x , xy en N implica y en N . Un submonoide se genera mediante un prefijo si y solo si es unitario recto. [14]
Una factorización de un monoide libre es una secuencia de subconjuntos de palabras con la propiedad de que cada palabra del 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 Lyndon proporcionan una factorización. En términos más generales, las palabras de Hall proporcionan una factorización; las palabras de Lyndon son un caso especial de las palabras de Hall.
La intersección de submonoides libres de un monoide libre A ∗ es nuevamente libre. [15] [16] Si S es un subconjunto de un monoide libre A * entonces la intersección de todos los submonoides libres de A * que contienen a S está bien definida, ya que A * en sí mismo es libre y contiene a S ; es un monoide libre y se llama la envoltura libre de S . Una base para esta intersección es un código.
El teorema del defecto [15] [16] [17] establece que si X es finito y C es la base de la envoltura libre de X , entonces X es un código y C = X , o
Un morfismo monoide f de un monoide libre B ∗ a un monoide M es una función tal que f ( xy ) = f ( x )⋅ f ( y ) para las palabras x , y y f (ε) = ι, donde ε e ι denotan los elementos identidad de B ∗ y M , respectivamente. El morfismo f está determinado por sus valores en las letras de B y, a la inversa, cualquier función de B a M se extiende a un morfismo. Un morfismo no borrable [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 todo a en A . [22] [23] Un morfismo 1-uniforme es estrictamente alfabético [19] o un codificador . [24]
Un morfismo f de un monoide libre B ∗ a un monoide libre A ∗ es simplificable si existe un alfabeto C de cardinalidad menor que la de B tal que el morfismo f se factoriza a través de C ∗ , es decir, es la composición de un morfismo de B ∗ a C ∗ y un morfismo de éste a A ∗ ; en caso contrario f es elemental . El morfismo f se llama código si la imagen del alfabeto B bajo f es un código. Todo morfismo elemental es un código. [25]
Para L , un subconjunto de B ∗ , un subconjunto finito T de L es un conjunto de prueba para L si los morfismos f y g en B ∗ concuerdan en L si y solo si concuerdan en T . La conjetura de Ehrenfeucht es que cualquier subconjunto L tiene un conjunto de prueba: [26] ha sido demostrada [27] independientemente por Albert y Lawrence; McNaughton; y Guba. Las demostraciones se basan en el teorema de la base de Hilbert . [28]
La realización computacional de un morfismo monoide es una función seguida de un pliegue . En este contexto, 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
donde e es la identidad en M . Computacionalmente, cada homomorfismo de este tipo 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 se puede generalizar a operadores binarios no asociativos) ha inspirado el marco de software MapReduce . [ cita requerida ]
Un endomorfismo de A ∗ es un morfismo de A ∗ a sí mismo. [29] La función identidad I es un endomorfismo de A ∗ , y los endomorfismos forman un monoide bajo composición de funciones .
Un endomorfismo f es prolongable si existe una letra a tal que f ( a ) = como para una cadena no vacía s . [30]
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 cuerdas p a ( s ) elimina cada ocurrencia de a de s ; se define formalmente por
Nótese 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, de modo que
donde se entiende que es el monoide libre de todas las cadenas finitas que no contienen la letra a . La proyección conmuta con la operación de concatenación de cadenas, de modo que para todas las cadenas s y t . Hay muchas inversas derechas para la proyección de cuerdas y, por lo tanto, es un epimorfismo dividido .
El morfismo identidad se define como para todas las cadenas s , y .
La proyección de cuerdas es conmutativa, como se ve 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.
La proyección de cuerdas es idempotente , ya que
para todas las cadenas s . Por lo tanto, la proyección es una operación idempotente y conmutativa, y por lo tanto forma una semired acotada o una banda conmutativa .
Dado un conjunto A , el monoide conmutativo libre en A es el conjunto de todos los multiconjuntos finitos con elementos extraídos de A , siendo la operación del monoide la suma del multiconjunto y la unidad del monoide el multiconjunto vacío.
Por ejemplo, si A = { a , b , c }, los elementos del monoide conmutativo libre en A son de la forma
El teorema fundamental de la aritmética establece que el monoide de los números enteros positivos bajo 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 multiconjuntos con elementos extraídos de A excepto el multiconjunto vacío.
El monoide parcialmente conmutativo libre , o monoide de traza , es una generalización que abarca tanto los monoides libres como los monoides conmutativos libres como instancias. Esta generalización encuentra aplicaciones en combinatoria y en el estudio del paralelismo en informática .
Medios relacionados con Monoide libre en Wikimedia Commons
