Semigrupo de transformación - Transformation semigroup

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 se cierra bajo la composición de funciones . Si se incluye la función identidad , es un monoide , llamada transformación (o composición ) monoid . Este es el análogo de semigrupo de un grupo de permutación .

Un semigrupo de transformación de un conjunto tiene una acción de semigrupo tautológica en ese conjunto. Tales 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 se puede realizar 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. Existe una correspondencia entre las dos nociones .

Transformación de semigrupos y monoides

Un semigrupo 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 solo una función del 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 el semigrupo de todas las transformaciones parciales (o el semigrupo de transformación parcial en X ), típicamente denotado por .

Si S incluye la transformación de identidad de X , entonces se denomina monoide de transformación . Obviamente, cualquier semigrupo de transformación S determina un monoide de transformación M tomando la unión de S con la transformación de 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 una transformación monoid llamado el monoid completa transformación (o semigrupo ) de X . También se le llama el semigrupo simétrica de X y se representa por T X . Así, un semigrupo transformación (o monoide) es sólo un subsemigroup (o submonoide ) de la monoid transformación completa de X .

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

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

El rasgo característico de los semigrupos de transformación, como acciones, es que son fieles , es decir, si

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

El mapa envío de s a t s es inyectiva si y sólo si ( X ,  T ) es fiel, en cuyo caso la imagen de este mapa es una transformación semigrupo isomorfo a S .

Representación 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), por lo 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, a través de 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 de identidad (izquierda o derecha), tomamos X para el conjunto subyacente de la monoid correspondiente a S para darse cuenta de S como un semigrupo transformación de X . En particular, cualquier semigrupo finito se puede representar como un subgrupo de transformaciones de un conjunto X con | X | ≤ | S | + 1, y si S es un monoide, tenemos el límite más agudo | X | ≤ | S |, como en el caso de grupos finitos .

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 por la izquierda da como resultado la multiplicación asociada a la derecha, y viceversa para la acción dada por la multiplicación por la 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 por la izquierda son la variación funcional de la estructura de datos de la lista de diferencias y la transformación de Codensidad monádica (una representación de Cayley de una mónada , que es un monoide en una categoría de functor monoidal particular ).

Monoide de transformación de un autómata

Deje que M sea un determinista autómata con el espacio de estados S y el alfabeto A . Las palabras en el monoide libre A * inducen transformaciones de S dando lugar a un morfismo monoid de A * a la transformación completa monoid T S . La imagen de este morfismo es la transformación de semigrupo M .

Para un lenguaje regular , el monoide sintáctico es isomorfo al monoide de transformación del autómata mínimo del lenguaje.

Ver también

Referencias