Semigrupo de transformación

En álgebra , un semigrupo de transformaciones (o semigrupo de composición ) es una colección de transformaciones ( funciones de un conjunto en sí mismo) que es cerrada bajo la composición de funciones . Si incluye la función identidad , es un monoide , llamado monoide de transformaciones (o de composición ) . Este es el análogo semigrupal de un grupo de permutaciones .

Un semigrupo de transformación de un conjunto tiene una acción tautológica de semigrupo sobre ese conjunto. Dichas acciones se caracterizan por ser fieles; es decir, si dos elementos del semigrupo tienen la misma acción, entonces son iguales.

Un análogo del teorema de Cayley muestra que cualquier semigrupo puede realizarse como un semigrupo de transformación de algún conjunto.

En la teoría de autómatas , algunos autores utilizan el término semigrupo de transformación para referirse a un semigrupo que actúa fielmente sobre un conjunto de "estados" diferente del conjunto base del semigrupo. ^{[ 1 ]} Existe una correspondencia entre las dos nociones .

Semigrupos y monoides de transformación

Un semigrupo de transformaciones es un par ( X , S ), donde X es un conjunto y S es un semigrupo de transformaciones de X. Aquí, una transformación de X es simplemente una función de un subconjunto de X a X , no necesariamente invertible, y por lo tanto S es simplemente un conjunto de transformaciones de X que es cerrado bajo la composición de funciones . El conjunto de todas las funciones parciales en un conjunto base dado, X , forma un semigrupo regular llamado semigrupo de todas las transformaciones parciales (o semigrupo de transformaciones parciales en X ), típicamente denotado por ${\mathcal {PT}}_{X}$ . ^{[ 2 ]}

Si S incluye la transformación identidad de X , entonces se denomina monoide de transformaciones . Cualquier semigrupo de transformaciones S determina un monoide de transformaciones M tomando la unión de S con la transformación identidad. Un monoide de transformaciones cuyos elementos son invertibles es un grupo de permutaciones .

El conjunto de todas las transformaciones de X es un monoide de transformaciones llamado monoide de transformaciones completo (o semigrupo ) de X. También se le denomina semigrupo simétrico de X y se denota por T _X. Por lo tanto, un semigrupo de transformaciones (o monoide) es simplemente un subsemigrupo (o submonoide ) del monoide de transformaciones completo de X.

Si ( X , S ) es un semigrupo de transformación, entonces X puede convertirse en una acción de semigrupo de S mediante evaluación:

s\cdot x=s(x){\text{ para }}s\in S,x\in X.

Esta es una acción de monoide si S es un monoide de transformación.

La característica distintiva de los semigrupos de transformación, como acciones, es que son fieles , es decir, si

s\cdot x=t\cdot x{\text{ para todo }}x\in X,

entonces s = t . Recíprocamente, si un semigrupo S actúa sobre un conjunto X mediante T ( s , x ) = s • x entonces podemos definir, para s ∈ S , una transformación T _s de X mediante

T_{s}(x)=T(s,x).\,

El mapa que envía s a T _s es inyectivo si y solo si ( X , T ) es fiel, en cuyo caso la imagen de este mapa es un semigrupo de transformación isomorfo a S .

Representación de Cayley

En teoría de grupos , el teorema de Cayley afirma que cualquier grupo G es isomorfo a un subgrupo del grupo simétrico de G (considerado como un conjunto), de modo que G es un grupo de permutaciones . Este teorema se generaliza directamente a los monoides: cualquier monoide M es un monoide de transformación de su conjunto subyacente, mediante la acción dada por la multiplicación por la izquierda (o por la derecha). Esta acción es fiel porque si ax = bx para todo x en M , entonces al tomar x igual al elemento identidad, tenemos a = b .

Para un semigrupo S sin elemento identidad (izquierdo o derecho), tomamos X como el conjunto subyacente del monoide correspondiente a S para realizar S como un semigrupo de transformaciones de X. En particular, cualquier semigrupo finito puede representarse como un subsemigrupo de transformaciones de un conjunto X con | X | ≤ | S | + 1, y si S es un monoide, tenemos la cota más precisa | X | ≤ | S |, como en el caso de los grupos finitos . ^{[ 3 ]}^{: 21}

En ciencias de la computación

En informática , las representaciones de Cayley se pueden aplicar para mejorar la eficiencia asintótica de los semigrupos mediante la reasociación de múltiples multiplicaciones compuestas. La acción dada por la multiplicación izquierda resulta en una multiplicación asociada a la derecha, y viceversa para la acción dada por la multiplicación derecha. A pesar de tener los mismos resultados para cualquier semigrupo, la eficiencia asintótica será diferente. Dos ejemplos de monoides de transformación útiles dados por una acción de multiplicación izquierda son la variación funcional de la estructura de datos de lista de diferencias y la transformación monádica de Codensity (una representación de Cayley de una mónada , que es un monoide en una categoría particular de functores monoidales ). ^[⁴^]

Monoide de transformación de un autómata

Sea M un autómata determinista con espacio de estados S y alfabeto A. Las palabras del monoide libre A ^∗ inducen transformaciones de S que dan lugar a un morfismo de monoide de A ^∗ al monoide de transformación completa T _{S. La imagen de este morfismo es el semigrupo}^de transformaciones de M. ^{[ 3} ] ^{: 78}

Para un lenguaje regular , el monoide sintáctico es isomorfo al monoide de transformación del autómata mínimo del lenguaje. ^{[ 3 ]}^{: 81}

Véase también

Referencias

↑ Dominique Perrin; Jean Eric Pin (2004). Palabras infinitas: autómatas, semigrupos, lógica y juegos . Academic Press. pág. 448. ISBN 978-0-12-532111-2.
↑ Alfred Hoblitzelle Clifford; GB Preston (1967). La teoría algebraica de los semigrupos. Volumen II . American Mathematical Soc. pág. 254. ISBN 978-0-8218-0272-4.
1 2 3 Anderson, James A. (2006). Teoría de autómatas con aplicaciones modernas . Con contribuciones de Tom Head. Cambridge: Cambridge University Press . doi : 10.1017/CBO9780511607202 . ISBN 978-0-521-61324-8. Zbl 1127.68049 .
↑ Rivas, Exequiel; Jaskelioff, Mauro (2017). " Nociones de computación como monoides ". Journal of Functional Programming . 27 (e21). arXiv : 1406.4823 . doi : 10.1017/S0956796817000132 .

Clifford, AH; Preston, GB (1961). La teoría algebraica de los semigrupos. Vol. I. Mathematical Surveys. Vol. 7. Providence, RI: American Mathematical Society . ISBN 978-0-8218-0272-4. Zbl 0111.03403 . {{cite book}}: Incompatibilidad de ISBN/Fecha ( ayuda )
Howie, John M. (1995). Fundamentos de la teoría de semigrupos . Monografías de la Sociedad Matemática de Londres. Nueva serie. Vol. 12. Oxford: Clarendon Press . ISBN 978-0-19-851194-6. Zbl 0835.20077 .
Mati Kilp, Ulrich Knauer, Alexander V. Mikhalev (2000), Monoides, actos y categorías: con aplicaciones a productos de coronas y grafos , Expositions in Mathematics 29 , Walter de Gruyter, Berlín, ISBN 978-3-11-015248-7.

[PerrinPin2004-1] Dominique Perrin; Jean Eric Pin (2004). Palabras infinitas: autómatas, semigrupos, lógica y juegos . Academic Press. pág. 448. ISBN 978-0-12-532111-2.

[CliffordPreston1967-2] Alfred Hoblitzelle Clifford; GB Preston (1967). La teoría algebraica de los semigrupos. Volumen II . American Mathematical Soc. pág. 254. ISBN 978-0-8218-0272-4.

[JAA-3] 1 2 3 Anderson, James A. (2006). Teoría de autómatas con aplicaciones modernas . Con contribuciones de Tom Head. Cambridge: Cambridge University Press . doi : 10.1017/CBO9780511607202 . ISBN 978-0-521-61324-8. Zbl 1127.68049 .

[4] Rivas, Exequiel; Jaskelioff, Mauro (2017). " Nociones de computación como monoides ". Journal of Functional Programming . 27 (e21). arXiv : 1406.4823 . doi : 10.1017/S0956796817000132 .

[ 1 ]

[ 2 ]

[ 3 ]

[