En álgebra abstracta , el 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 cadena vacía y denotada por ε o λ, como elemento de identidad . El monoide libre en un conjunto A generalmente se denota como A ∗ . El semigrupo libre de A es el subsemigrupo de A ∗ que contiene todos los elementos excepto la cadena vacía. Generalmente se denota como A + . [1] [2]
De manera más general, un monoide (o semigrupo) abstracto S se describe como libre si es isomorfo al monoide (o semigrupo) libre en algún conjunto. [3]
Como su nombre lo indica, los monoides y semigrupos libres son aquellos objetos que satisfacen la propiedad universal habitual que define 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 mostrar agrupación u orden de operación. El equivalente no asociativo es el magma libre .
El monoide ( N 0 ,+) de los números naturales (incluido el cero) bajo la suma es un monoide libre en un generador 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. Mapear cada una de estas secuencias con su resultado de evaluación [4] y la secuencia vacía con cero establece un isomorfismo del conjunto de dichas secuencias con 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 myt a n , entonces su concatenación s + t se asigna a la suma m + n .
En la teoría del lenguaje formal , normalmente se considera 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 generados finitamente.
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 cualquier conjunto, la función de longitud de palabra en A ∗ es el homomorfismo monoide único 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 clasificación aquí es solo la longitud de la cadena. Es decir, contiene esas cadenas de longitud. El símbolo aquí puede interpretarse como "conjunto unión"; se usa en lugar del símbolo porque, en general, las uniones de conjuntos pueden no ser monoides, por lo que se usa un símbolo distinto. Por convención, las gradaciones siempre se escriben con el símbolo.)
Existen profundas conexiones entre la teoría de los semigrupos y la de los autómatas . Por ejemplo, todo 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]
Para el caso de computación concurrente , es decir, sistemas con bloqueos , mutex o uniones de subprocesos , la computación se puede describir con monoides históricos y monoides de traza . En términos generales, los elementos del monoide pueden conmutarse (por ejemplo, diferentes subprocesos pueden ejecutarse en cualquier orden), pero sólo hasta un bloqueo o mutex, que evita 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 lo son en el sentido de la teoría de grupos como elementos del grupo libre generado por A. [8]
Un monoide libre es equidivisible : si la ecuación mn = pq se cumple, 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 lema de Levi . [10]
Un monoide es libre si y sólo si está graduado (en el sentido estricto 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 + . Entonces se entiende comúnmente que el superíndice * es la estrella Kleene . De manera más general, si S es un monoide libre abstracto (semigrupo), entonces un conjunto de elementos que se asigna al conjunto de palabras de una sola letra bajo un isomorfismo a un monoide A ∗ (semigrupo A + ) se llama conjunto de generadores libres para S .
Cada monoide (o semigrupo) libre S tiene exactamente un conjunto de generadores libres, cuya cardinalidad se denomina rango de S.
Dos monoides o semigrupos libres son isomorfos si y sólo si tienen el mismo rango. De hecho, cada conjunto de generadores para un monoide o semigrupo S libre contiene los generadores libres, ya que un generador libre tiene una longitud de palabra 1 y, por lo tanto, solo puede generarse por sí mismo. De ello se deduce que un semigrupo o monoide libre se genera de forma finita si y sólo si tiene 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 sólo si es libre. [12] Por ejemplo, utilizando 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 también debe contener un número par de "1". 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 (cadena) adecuado 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 derecho si x , xy en N implica y en N . Un submonoide es generado por un prefijo si y sólo si es unitario por la derecha. [14]
Una 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 Lyndon proporcionan una factorización. De manera más general, 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 ∗ vuelve a ser 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 S está bien definida, ya que A * en sí es libre y contiene S ; es un monoide libre y se llama casco 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 cáscara 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 aplicación tal que f ( xy ) = f ( x )⋅ f ( y ) para las palabras x , y y f (ε) = ι, donde ε y ι denotamos 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 mapa de B a M se extiende a un morfismo. Un morfismo no se borra [18] o es continuo [19] si ninguna letra de B se asigna a ι y es 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 a 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 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 , tal que el morfismo f se factorice a través de C ∗ , es decir, es la composición de un morfismo de B ∗ a C ∗ y un morfismo de ese a A ∗ ; de lo 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 demostrado [27] de forma independiente por Albert y Lawrence; McNaughton; y Guba. Las pruebas se basan en el teorema de la base de Hilbert . [28]
La encarnación computacional de un morfismo monoide es un mapa seguido de un pliegue . En esta configuración, 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 puede generalizarse a operadores binarios no asociativos) ha inspirado el marco del software MapReduce . [ cita necesaria ]
Un endomorfismo de A ∗ es un morfismo de A ∗ hacia sí mismo. [29] El mapa de identidad I es un endomorfismo de A ∗ , y los endomorfismos forman un monoide bajo 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]
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 cadena p a ( s ) elimina cada aparición de a de s ; está formalmente definido 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 cuerdas de longitud finita. La proyección de cuerdas es un morfismo en la categoría de monoides libres, de modo que
donde se entiende 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 muchos inversos rectos de la proyección de cuerdas y, por lo tanto, es un epimorfismo dividido .
El morfismo de identidad se define como para todas las cadenas s , y .
La proyección de cuerdas es conmutativa, como claramente
Para los monoides libres de rango finito, esto se deriva 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 , como
para todas las cadenas s . Por tanto, la proyección es una operación conmutativa idempotente, por lo que 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 monoide la suma de múltiples conjuntos y la unidad 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 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 libre parcialmente conmutativo , o monoide traza , es una generalización que abarca tanto el monoide libre como el monoide conmutativo libre 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
