Hispanopedia Wiki
Articulo de referencia

monoide libre

En álgebra abstracta , el monoide libre sobre un conjunto es aquel cuyos elementos son todas las secuencias finitas (o cadenas) de cero o más elementos de dicho conjunto, siendo...

Hispanopedia WikiContenido en espanolLectura gratuita

En álgebra abstracta , el monoide libre sobre un conjunto es aquel cuyos elementos son todas las secuencias finitas (o cadenas) de cero o más elementos de dicho conjunto, siendo la concatenación de cadenas la operación monoide y la única secuencia de cero elementos, a menudo denominada cadena vacía y denotada por ε o λ, la identidad . El monoide libre sobre un conjunto A se suele denotar A * . El semigrupo libre sobre A es el subsemigrupo de A * que contiene todos los elementos excepto la cadena vacía. Se suele denotar 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 usual que define a los objetos libres , en las categorías respectivas de monoides y semigrupos. De ello se deduce que todo 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 .

Ejemplos

Números naturales

El monoide ( N 0 ,+) de los números naturales (incluido el cero) bajo la suma es un monoide libre sobre un generador libre unitario, 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 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 cualesquiera dos secuencias s y t , si s se mapea (es decir, se evalúa) a un número m y t a n , entonces su concatenación s + t se mapea a la suma m + n .

Tuplas

El monoide libre sobre el conjunto N 0 de los números naturales es ( T , ⟨ ⟩ ,::), donde T denota el conjunto de tuplas de números naturales, ⟨ ⟩ denota la única 0-tupla y  :: denota la concatenación de tuplas. Los monoides ( N 0 ,+) y ( T , ⟨ ⟩ ,::) no son isomorfos, ya que + es conmutativo, mientras que  :: no lo es.

Estrella Kleene

En la teoría de lenguajes formales , se suele considerar 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 lo tanto, el estudio abstracto de los lenguajes formales puede entenderse 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 :

{ε, a , ab , ba , caa , cccbabbc , ...}.

Si A es cualquier conjunto, la función de longitud de palabra en A ∗ es el único homomorfismo de monoide de A ∗ a ( N 0 ,+) que asigna a cada elemento de A el valor 1. Un monoide libre es, por lo tanto, un monoide graduado . [ 5 ] (Un monoide graduadoMETRO{\displaystyle M}es un monoide que se puede escribir comoMETRO=METRO0⊕METRO1⊕METRO2⋯{\displaystyle M=M_{0}\oplus M_{1}\oplus M_{2}\cdots }. CadaMETROnorte{\displaystyle M_{n}}es una calificación; la calificación aquí es simplemente la longitud de la cuerda. Es decir,METROnorte{\displaystyle M_{n}}contiene esas cadenas de longitudnorte.{\displaystyle n.}El⊕{\displaystyle \oplus }El símbolo aquí puede interpretarse como "unión de conjuntos"; se utiliza en lugar del símbolo∪{\displaystyle \cup }porque, en general, las uniones de conjuntos pueden no ser monoides, y por lo tanto se utiliza un símbolo distinto. Por convención, las gradaciones siempre se escriben con el⊕{\displaystyle \oplus }símbolo.)

Existen profundas conexiones entre la teoría de semigrupos y la de autómatas . Por ejemplo, todo lenguaje formal posee un monoide sintáctico que lo reconoce. En el caso de un lenguaje regular , dicho 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 la unión, el producto y la generación de submonoides. [ 6 ]

En el caso de la computación concurrente , es decir, sistemas con bloqueos , mutex o uniones de hilos , la computación se puede describir con monoides de historial y monoides de traza . En términos generales, los elementos del monoide pueden conmutar (por ejemplo, diferentes hilos pueden ejecutarse en cualquier orden), pero solo hasta un bloqueo o mutex, que impiden una conmutación posterior (por ejemplo, serializar el acceso de un hilo a algún objeto).

Conjugar palabras

Ejemplo para el primer caso de equidivisibilidad: m="UNCLE", n="ANLY", p="UN", q="CLEANLY" y s="CLE"

Definimos un par de palabras en A ∗ de la forma uv y vu como conjugadas : las conjugadas de una palabra son, por lo 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 ]

Equidivisibilidad

Un monoide libre es equidivisible : si se cumple la ecuación mn = pq , entonces existe un s tal que o bien m = ps , sn = q (véase la imagen del ejemplo) o bien ms = p , n = sq . [ 9 ] Este resultado también se conoce como el lema de Levi . [ 10 ]

Un monoide es libre si y solo si es graduado (en el sentido estricto de que solo la identidad tiene gradación 0) y equidivisible. [ 9 ]

Generadores y rangos gratuitos

Los miembros de un conjunto A se denominan generadores libres para A ∗ y A + . El superíndice * se entiende comúnmente como la estrella de Kleene . De forma más general, si S es un monoide (semigrupo) libre abstracto, 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 para S.

Cada monoide libre (o semigrupo) S tiene exactamente un conjunto de generadores libres, cuya cardinalidad se llama rango de S.

Dos monoides o semigrupos libres son isomorfos si y solo si tienen el mismo rango. De hecho, todo conjunto de generadores para un monoide o semigrupo libre S contiene los generadores libres, ya que un generador libre tiene longitud de palabra 1 y, por lo tanto, solo puede ser generado por sí mismo. De ello se deduce que un semigrupo o monoide libre es finitamente generado si y solo 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 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 también debe contener un número par de "1". Si bien N no puede ser generado libremente por ningún conjunto de bits individuales, puede ser generado libremente por 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").

Códigos

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 . Todo 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 solo si es unitario derecho. [ 14 ]

Factorización

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 dichos subconjuntos. El teorema de Chen-Fox-Lyndon establece que las palabras de Lyndon proporcionan una factorización. De forma más general, las palabras de Hall también proporcionan una factorización; las palabras de Lyndon son un caso particular de las palabras de Hall.

Casco libre

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 * 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 o bien X es un código y C = X , o bien

| C | ≤ | X | − 1 .

Morfismos

Un morfismo de 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 ε e ι denotan los elementos identidad de B ∗ y M , respectivamente. El morfismo f está determinado por sus valores en las letras de B y, recíprocamente, cualquier aplicación de B a M se extiende a un morfismo. Un morfismo es no borrador [ 18 ] o continuo [ 19 ] si ninguna letra de B se aplica a ι y trivial si todas las letras de B se aplican 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 de 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 una codificación . [ 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 este a A ∗ ; de lo contrario, f es elemental . El morfismo f se denomina código si la imagen del alfabeto B bajo f es un código. Todo morfismo elemental es un código. [ 25 ]

Conjuntos de prueba

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 ∗ coinciden en L si y solo si coinciden en T . La conjetura de Ehrenfeucht afirma 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 ]

Mapa y plegado

La representación computacional de un morfismo de monoide es un mapa seguido de un pliegue . [ 29 ] En este contexto, el monoide libre sobre un conjunto A corresponde a listas de elementos de A con la concatenación como operación binaria. Un homomorfismo de 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. Computacionalmente, cada homomorfismo de este tipo corresponde a una operación de mapeo 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 de software MapReduce . [ 30 ]

Endomorfismos

Un endomorfismo de A ∗ es un morfismo de A ∗ en sí mismo. [ 31 ] El mapa 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 existe una letra a tal que f ( a ) = como para una cadena no vacía s . [ 32 ]

Proyección de cadena

La operación de proyección de cadenas es un endomorfismo. Es decir, dada una letra a ∈ Σ y una cadena s ∈ Σ ∗ , la proyección de cadenas p a ( s ) elimina cada ocurrencia de a de s ; se define formalmente por

paga(s)={εsi s=ε, la cadena vacíapaga(t)si s=tapaga(t)bsi s=tb y b≠a.{\displaystyle p_{a}(s)={\begin{cases}\varepsilon &{\text{si }}s=\varepsilon ,{\text{ la cadena vacía}}\\p_{a}(t)&{\text{si }}s=ta\\p_{a}(t)b&{\text{si }}s=tb{\text{ y }}b\neq a.\end{cases}}}

Nótese que la proyección de cadenas 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 cadenas es un morfismo en la categoría de monoides libres, de modo que

paga(Σ∗)=(Σ−a)∗{\displaystyle p_{a}\left(\Sigma ^{*}\right)=\left(\Sigma -a\right)^{*}}

dóndepaga(Σ∗){\displaystyle p_{a}\left(\Sigma ^{*}\right)}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 quepaga(st)=paga(s)paga(t){\displaystyle p_{a}(st)=p_{a}(s)p_{a}(t)}para todas las cadenas s y t . Hay muchas inversas derechas de la proyección de cadenas, y por lo tanto es un epimorfismo dividido .

El morfismo identidad espagε,{\ Displaystyle p _ {\ varepsilon},}definido comopagε(s)=s{\displaystyle p_{\varepsilon }(s)=s}para todas las cadenas s ypagε(ε)=ε{\displaystyle p_{\varepsilon }(\varepsilon )=\varepsilon }.

La proyección de cadenas es conmutativa, como se observa claramente.

paga(pagb(s))=pagb(paga(s)).{\displaystyle p_{a}(p_{b}(s))=p_{b}(p_{a}(s)).}

Para 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 cadenas es idempotente , ya que

paga(paga(s))=paga(s){\displaystyle p_{a}(p_{a}(s))=p_{a}(s)}

para todas las cadenas s . Por lo tanto, la proyección es una operación idempotente y conmutativa, y por lo tanto forma un semirretículo acotado o una banda conmutativa .

El monoide conmutativo libre

Dado un conjunto A , el monoide conmutativo libre en A es el conjunto de todos los multiconjuntos finitos con elementos extraídos de A , donde la operación del monoide es la suma de multiconjuntos y la unidad del monoide es el multiconjunto 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 la aritmética establece que el monoide de los enteros positivos bajo la multiplicación es un monoide conmutativo libre sobre 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 engloba tanto a los monoides libres como a los monoides libres conmutativos como instancias. Esta generalización encuentra aplicaciones en combinatoria y en el estudio del paralelismo en informática .

Véase también

Notas

  1. ^ Lothaire (1997 , págs. 2-3) , 
  2. ↑ Pytheas Fogg (2002 , p. 2) 
  3. 1 2 3 Lothaire (1997 , pág. 5) 
  4. ↑ Dado que la suma de números naturales es asociativa, el resultado no depende del orden de evaluación, lo que garantiza que la correspondencia esté bien definida.
  5. ↑ Sakarovitch (2009) pág. 382
  6. ↑ Borovik, Alexandre (1 de enero de 2005). Grupos, lenguajes, algoritmos: Sesión especial conjunta AMS-ASL sobre interacciones entre lógica, teoría de grupos e informática, 16-19 de enero de 2003, Baltimore, Maryland . American Mathematical Soc. ISBN 9780821836187.
  7. ↑ Sakarovitch (2009) pág. 27
  8. ↑ Pytheas Fogg (2002 , p. 297) 
  9. 1 2 Sakarovitch (2009) pág. 26
  10. ↑ de Luca, Aldo; Varricchio, Stefano (1999). Finiteness and Regularity in Semigroups and Formal Languages . Springer Berlin Heidelberg. p. 2. ISBN  978-3-642-64150-3.
  11. ↑ Berstel, Perrin y Reutenauer (2010 , p.61 ) 
  12. ↑ Berstel, Perrin y Reutenauer (2010 , p.62 ) 
  13. ^ Berstel, Perrin y Reutenauer (2010 , p. 58) 
  14. ↑ Lothaire (1997 , p. 15) 
  15. 1 2 Lothaire (1997 , pág. 6) 
  16. 1 2 Lothaire (2011 , pág. 204) 
  17. ↑ Berstel, Perrin y Reutenauer (2010 , p.66 ) 
  18. ↑ Lothaire (1997 , p. 7) 
  19. 1 2 Sakarovitch (2009 , pág. 25) 
  20. 1 2 Lothaire (1997 , pág. 164) 
  21. ↑ Salomaa (1981 , p. 77) 
  22. ↑ Lothaire (2005 , p. 522) 
  23. ↑ Berstel, Jean; Reutenauer, Christophe (2011). Series racionales no conmutativas con aplicaciones . Enciclopedia de Matemáticas y sus Aplicaciones. Vol. 137. Cambridge: Cambridge University Press . pág. 103. ISBN   978-0-521-19022-0. Zbl 1250.68007 . 
  24. ^ Allouche y Shallit (2003 , pág. 9) 
  25. ↑ Salomaa (1981 , p. 72) 
  26. ^ Lothaire (1997 , págs. 178-179) 
  27. ↑ Lothaire (2011 , p. 451) 
  28. ↑ Salomaa, A. (octubre de 1985). "La conjetura de Ehrenfeucht: una demostración para teóricos del lenguaje". Boletín de la EATCS (27): 71–82 .
  29. ↑ Bird, Richard S. (1989), "Lectures on Constructive Functional Programming" , en Broy, Manfred (ed.), Constructive Methods in Computing Science , Berlín, Heidelberg: Springer Berlin Heidelberg, pp. 151–217 , doi : 10.1007/978-3-642-74884-4_5 , ISBN  978-3-642-74886-8, consultado el 28 de diciembre de 2025
  30. ↑ "¿Qué es MapReduce? | IBM" . www.ibm.com . 19 de noviembre de 2024. Consultado el 22 de octubre de 2025 .
  31. ↑ Lothaire (2011 , pág. 450) 
  32. ^ Allouche y Shallit (2003) p.10

Referencias

  • Allouche, Jean-Paul; Shallit, Jeffrey (2003), Automatic Sequences: Theory, Applications, Generalizations , Cambridge University Press , ISBN 978-0-521-82332-6, Zbl 1086.11015 
  • Berstel, Jean ; Perrin, Dominique ; Reutenauer, Christophe (2010), Códigos y autómatas , Enciclopedia de Matemáticas y sus Aplicaciones, vol.  129, Cambridge: Cambridge University Press , ISBN 978-0-521-88831-8, Zbl 1187.94001 
  • Lothaire, M. (1997), Combinatoria en palabras , Cambridge Mathematical Library, vol.  17, Colaboradores: Perrin, D.; Reutenauer, C.; Berstel, J.; Pin, JE; Pirillo, G.; Foata, D.; Sakarovitch, J.; Simon, I.; Schützenberger, MP; Choffrut, C.; Cori, R. Editores de la serie: Lyndon, Roger; Rota, Gian-Carlo. Prólogo de Roger Lyndon (2.ª  ed.), Cambridge University Press , doi : 10.1017/CBO9780511566097 , ISBN 0-521-59924-5, MR 1475463 , Zbl 0874.20040  
  • Lothaire, M. (2011), Combinatoria algebraica en palabras , Enciclopedia de Matemáticas y sus Aplicaciones, vol.  90, Con prefacio de Jean Berstel y Dominique Perrin (Reimpresión de la  edición en tapa dura de 2002), Cambridge University Press , ISBN 978-0-521-18071-9, Zbl 1221.68183 
  • Lothaire, M. (2005), Combinatoria aplicada a las palabras , Enciclopedia de las Matemáticas y sus Aplicaciones, vol.  105, una obra colectiva de Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert , Sophie Schbath , Michael Waterman, Philippe Jacquet, Wojciech Szpankowski , Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche y Valérie Berthé , Cambridge: Cambridge University Press , ISBN 0-521-84802-4, Zbl 1133.68067 
  • Pytheas Fogg, N. (2002), Berthé, Valérie ; Ferenczi, Sébastien; Mauduit, cristiano; Siegel, A. (eds.), Sustituciones en dinámica, aritmética y combinatoria , Lecture Notes in Mathematics, vol.  1794, Berlín: Springer-Verlag , ISBN 3-540-44141-7, Zbl 1014.11015 
  • Sakarovitch, Jacques (2009), Elementos de la teoría de autómatas , Traducido del francés por Reuben Thomas, Cambridge: Cambridge University Press , ISBN 978-0-521-84425-3, Zbl 1188.68177 
  • Salomaa, Arto (1981), Joyas de la teoría del lenguaje formal , Pitman Publishing, ISBN 0-273-08522-0, Zbl 0487.68064