Semigrupo de transformación

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

Un semigrupo de transformación de un conjunto tiene una acción de semigrupo tautológica sobre dicho 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" diferentes del conjunto base del semigrupo. ^[1] Existe una correspondencia entre ambas nociones .

Semigrupos y monoides de transformación

Un semigrupo de transformación 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 está 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 transformación parcial en X ), típicamente denotado por . ^[2] ${\displaystyle {\mathcal {PT}}_{X}}$

Si S incluye la transformación identidad de X , entonces se denomina monoide de transformación . Obviamente, cualquier semigrupo de transformación S determina un monoide de transformación M al tomar la unión de S con la transformación identidad. Un monoide de transformación cuyos elementos son invertibles es un grupo de permutación .

El conjunto de todas las transformaciones de X es un monoide de transformación llamado monoide de transformación completo (o semigrupo ) de X . También se llama semigrupo simétrico de X y se denota por T _X . Por lo tanto, un semigrupo de transformación (o monoide) es simplemente un subsemigrupo (o submonoide ) del monoide de transformación 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:

${\displaystyle s\cdot x=s(x){\text{ for }}s\in S,x\in X.}$

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

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

${\displaystyle s\cdot x=t\cdot x{\text{ for all }}x\in X,}$

entonces s = t . Por el contrario, si un semigrupo S actúa sobre un conjunto X por T ( s , x ) = s • x entonces podemos definir, para s ∈ S , una transformación T _s de X por

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

La función que envía s a T _s es inyectiva si y sólo si ( X ,  T ) es fiel, en cuyo caso la imagen de esta función 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 permutación . 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 izquierda (o 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 un elemento identidad (izquierdo o derecho), tomamos a X como el conjunto subyacente del monoide correspondiente a S para realizar a 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 nítida | X | ≤ | S |, como en el caso de los grupos finitos . ^{[3] : 21}

En informática

En informática , las representaciones de Cayley se pueden aplicar para mejorar la eficiencia asintótica de los semigrupos reasociando múltiples multiplicaciones compuestas. La acción dada por la multiplicación izquierda da como resultado 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 Codensity (una representación de Cayley de una mónada , que es un monoide en una categoría de funtor monoidal particular ). ^[4]

Transformación monoide 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 dando lugar a un morfismo monoide desde A ^∗ hasta el monoide de transformación completo T _S . La imagen de este morfismo es el semigrupo de transformación 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

• Semiautomático
• Teoría de Krohn-Rhodes
• Semigrupo inverso simétrico
• Conjunto bioordenado
• Clases especiales de semigrupos
• Anillo de composición

Referencias

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.
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.
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 ". Revista de programación funcional . 27 (e21). arXiv : 1406.4823 . doi :10.1017/S0956796817000132.

• Clifford, AH; Preston, GB (1961). La teoría algebraica de semigrupos. Vol. I. Encuestas matemáticas. Vol. 7. Providence, RI: American Mathematical Society . ISBN. 978-0-8218-0272-4.Zbl 0111.03403  .
• Howie, John M. (1995). Fundamentos de la teoría de semigrupos . Monografías de la London Mathematical Society. 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 corona y gráficos , Exposiciones en matemáticas 29 , Walter de Gruyter, Berlín, ISBN 978-3-11-015248-7 .