teoría de Krohn-Rhodes (o teoría de los autómatas algebraicos ) es una aproximación al estudio de semigrupos y autómatas finitos que busca descomponerlos en términos de componentes elementales. Estos componentes corresponden a semigrupos aperiódicos finitos y grupos finitos simples que se combinan de manera libre de retroalimentación (llamado " producto corona " o "cascada").
Krohn y Rhodes encontraron una descomposición general para autómatas finitos . Sin embargo, al hacer su investigación, los autores descubrieron y demostraron un importante resultado inesperado en la teoría de semigrupos finitos, revelando una conexión profunda entre autómatas finitos y semigrupos.
Definiciones y descripción del teorema de Krohn-Rhodes. [ editar ]
Un semigrupo S que es un homomorphic imagen de un subsemigroup de T se dice que es un divisor de T .
El teorema de Krohn-Rhodes para semigrupos finitos establece que cada semigrupo finito S es un divisor de un producto de corona finita alternante de grupos finitos simples , cada uno un divisor de S , y semigrupos aperiódicos finitos (que no contienen subgrupos no triviales ). [1]
En la formulación de autómatas, el teorema de Krohn-Rhodes para autómatas finitos establece que, dado un autómata finito A con estados Q y conjunto de entrada I , salida del alfabeto U , entonces uno puede expandir los estados a Q ' , de manera que el nuevo autómata A' se incrusta en una cascada de autómatas irreducibles "simples": en particular, A es emulada por una cascada de (1) autómatas cuyas semiciones de transiciones songrupos finitos simples y (2) autómatas que son bancos de flip-flops que se ejecutan en paralelo. [nb 1] El nuevo autómata A ' tiene los mismos símbolos de entrada y salida como A . Aquí, tanto los estados como las entradas de los autómatas en cascada tienen una forma jerárquica de coordenadas muy especial.
Además, cada semigrupo irreductible de grupo simple ( primo ) o no grupal (subgrupo del monoide flip-flop ) que divide el semigrupo de transformación de A debe dividir el semigrupo de transición de algún componente de la cascada, y solo los números primos que deben aparecer como Los divisores de los componentes son los que dividen el semigrupo de transición de A.
Complejidad del grupo [ editar ]
La complejidad de Krohn-Rhodes (también llamada complejidad de grupo o simplemente complejidad ) de un semigrupo S finito es el menor número de grupos en un producto de corona de grupos finitos y semigrupos aperiódicos finitos de los cuales S es un divisor.
Todos los semigrupos aperiódicos finitos tienen complejidad 0, mientras que los grupos finitos no triviales tienen complejidad 1. De hecho, hay semigrupos de toda complejidad entera no negativa . Por ejemplo, para cualquier nmayor que 1, el semigrupo multiplicativo de todas las matrices triangulares superiores ( n +1) × ( n +1) sobre cualquier campo finito fijo tiene complejidad n (Kambites, 2007).
Un problema abierto importante en la teoría de semigrupos finitos es la decidibilidad de la complejidad : ¿existe un algoritmo que calcule la complejidad de Krohn-Rhodes de un semigrupo finito, dada su tabla de multiplicar ? Se han obtenido límites superiores y cada vez más precisos límites de complejidad (ver, por ejemplo, Rhodes & Steinberg, 2009). Rhodes ha conjeturado que el problema es decidible. [nb 2]
Historia y aplicaciones [ editar ]
En una conferencia en 1962, Kenneth Krohn y John Rhodes anunciaron un método para descomponer un autómata finito (determinista) en componentes "simples" que son ellos mismos autómatas finitos. Este trabajo conjunto, que tiene implicaciones para la filosofía, comprendió tanto la tesis doctoral de Krohn en la Universidad de Harvard como la tesis doctoral de Rhodes en el MIT . [nb 3] Desde entonces, se han publicado pruebas más simples y generalizaciones del teorema de estructuras infinitas (consulte el Capítulo 4 del libro de Steinberg y Rhodes de 2009, The q- Theory of Finite Semigroups, para una descripción general).
En el artículo de 1965 de Krohn y Rhodes, la prueba del teorema sobre la descomposición de autómatas finitos (o, máquinas equivalentes secuenciales ) hizo un uso extensivo de la estructura de semigrupos algebraicos . Las pruebas posteriores contenían simplificaciones importantes utilizando productos de corona finitos de semigrupos de transformación finitos. El teorema generaliza la descomposición de Jordan-Hölder.para grupos finitos (en donde los primos son los grupos simples finitos), para todos los semigrupos de transformación finitos (para los cuales los primos son nuevamente los grupos simples finitos más todos los subgrupos del "flip-flop" (ver arriba)). Tanto el grupo como la descomposición de autómatas finitos más general requieren expandir el conjunto de estados del general, pero permiten el mismo número de símbolos de entrada. En el caso general, estos están integrados en una estructura más grande con un "sistema de coordenadas" jerárquico.
Se debe tener cuidado al entender la noción de "primo", ya que Krohn y Rhodes se refieren explícitamente a su teorema como un "teorema de descomposición primordial" para los autómatas. Sin embargo, los componentes de la descomposición no son autómatas primarios (con primos definidos de manera ingenua); más bien, la noción de primees más sofisticado y algebraico: los semigrupos y grupos asociados a los autómatas constituyentes de la descomposición son primos (o irreductibles) en un sentido algebraico estricto y natural con respecto al producto de la corona (Eilenberg, 1976). Además, a diferencia de los teoremas de descomposición anteriores, las descomposiciones de Krohn-Rhodes por lo general requieren la expansión del conjunto de estados, de modo que el autómata expandido cubre (emula) al que está descompuesto. Estos hechos han hecho que el teorema sea difícil de entender y desafiante de aplicar de manera práctica, hasta hace poco, cuando las implementaciones computacionales estaban disponibles (Egri-Nagy y Nehaniv 2005, 2008).
HP Zeiger (1967) demostró una importante variante denominada descomposición de holonomía (Eilenberg 1976). [nb 4] El método de holonomía parece ser relativamente eficiente y ha sido implementado computacionalmente por A. Egri-Nagy (Egri-Nagy & Nehaniv 2005).
Meyer y Thompson (1969) dan una versión de la descomposición de Krohn-Rhodes para autómatas finitos que es equivalente a la descomposición desarrollada previamente por Hartmanis y Stearns, pero para descomposiciones útiles, la noción de expandir el conjunto de estados del autómata original es esencial ( para el caso de autómatas sin permutación).
Actualmente existen muchas pruebas y construcciones de las descomposiciones de Krohn-Rhodes (por ejemplo, [Krohn, Rhodes & Tilson 1968], [Ésik 2000], [Diekert et al. 2012]), siendo el método de holonomía el más popular y eficiente en general (aunque no en todos los casos). Debido a la estrecha relación entre los monoides y las categorías, una versión del teorema de Krohn-Rhodes es aplicable a la teoría de categorías . Wells (1980) ofreció esta observación y una prueba de un resultado análogo. [nb 5]
El teorema de Krohn-Rhodes para semigroups / monoids es un análogo del teorema de Jordan-Hölder para grupos finitos (para semigroups / monoids en lugar de grupos). Como tal, el teorema es un resultado profundo e importante en la teoría de semigrupos / monoides. El teorema también sorprendió a muchos matemáticos e informáticos [nb 6] ya que anteriormente se creía ampliamente que los axiomas semiegrupos / monoides eran demasiado débiles para admitir un teorema de estructura de alguna fuerza, y el trabajo anterior (Hartmanis y Stearns) era solo capaz de mostrar resultados de descomposición mucho más rígidos y menos generales para autómatas finitos.
El trabajo de Egri-Nagy y Nehaniv (2005, 2008–) continúa automatizando aún más la versión de holonomía de la descomposición de Krohn-Rhodes extendida con la descomposición relacionada para grupos finitos (denominados coordenadas de Frobenius-Lagrange ) utilizando el sistema de álgebra computacional GAP .
Las aplicaciones fuera del semigrupo y las teorías monoides ahora son computacionalmente factibles. Incluyen cálculos en biología y sistemas bioquímicos (por ejemplo, Egri-Nagy y Nehaniv 2008), inteligencia artificial , física de estados finitos , psicología y teoría de juegos (véase, por ejemplo, Rhodes 2009).
anillo monoide es un anillo construido a partir de un anillo y un monoide , al igual que un anillo grupal se construye a partir de un anillo y un grupo .
Definición [ editar ]
Sea R un anillo y sea G un monoide. El anillo monoide o álgebra monoide de G sobre R , denotado como R [ G ] o RG , es el conjunto de sumas formales, dónde para cada y r g = 0 para todos, pero un número finito g , equipado con adición coeficiente a gota, y la multiplicación en la que los elementos de Rconmutan con los elementos de G . Más formalmente, R [ G ] es el conjunto de funciones φ: G → R tal que { g : φ ( g ) ≠ 0 } es finito, equipado con la suma de funciones y con la multiplicación definida por
- .
Propiedad universal [ editar ]
Dados R y G , hay un anillo homomorfismo α: R → R [ G ] enviando cada r a r 1 (donde 1 es el elemento de identidad de G ), y un homomorfismo monoide β: G → R [ G ] (donde este último se ve como un monoide en multiplicación) enviando cada g a 1 g (donde 1 es la identidad multiplicativa de R ). Tenemos que α ( r ) conmuta con β ( g ) para todos ren R y g en G .
La propiedad universal del anillo monoide indica que, dado un anillo S , un homomorfismo de anillo α ': R → S , y un homomorfismo monoide β': G → S al monoide multiplicativo de S , de manera que α '( r ) conmuta con β '( g ) para todos r en R y g en G , existe un homomorfismo de anillo único γ: R [ G ] → S tal que la composición de α y β con γ produce α' y β '.
Aumento [ editar ]
El aumento es el homomorfismo de anillo η : R [ G ] → R definido por
El kernel de η se llama ideal de aumento . Es un libre de R - módulo con base consiste en 1- g para todos g en G no es igual a 1.
Ejemplos [ editar ]
Dado un anillo R y el (aditivo) monoid de los números naturales N (o { x n } visto multiplicativa), obtenemos el anillo R [{ x n }] =: R [ x ] de polinomios más de R . El monoid N n (con la adición) da el anillo polinomial con n variables: R [ N n ] =: R [X 1 , ..., X n ].
Generalización [ editar ]
semigrupo de transformación (o semigrupo de composición ) es una colección de funcionesde un conjunto a sí mismo que se cierra bajo la composición de la función . Si se incluye la función identidad , es un monoide , llamada transformación (o composición ) monoid . Este es el anólogo semigrupo de un grupo de permutación .
Un semigrupo de transformación de un conjunto tiene una acción de semigrupo tautológico en ese conjunto. Dichas acciones se caracterizan por ser efectivas, 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 usan el término semigrupo de transformación para referirse a un semigrupo que actúa fielmente en un conjunto de "estados" diferentes del conjunto base del semigrupo. [1] Hay una correspondencia entre las dos nociones .
Semigrupos de transformación y monoides [ editar ]
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 de X a sí misma, no necesariamente invertible, y por lo tanto S es simplemente un conjunto de transformaciones de X que se cierra bajo la composición de funciones . Si S incluye la transformación de identidad de X , 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 . La transformación completa monoide es un semigrupo regular .
Si ( X , S ) es un semigrupo de transformación, entonces X se puede convertir en una acción de semigrupo de Spor 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 efectivos , es decir, si
entonces s = t . A la inversa, si un semigrupo S actúa en 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 de enviar s a T s es inyectiva si y sólo si ( X , T ) es eficaz, en cuyo caso la imagen de este mapa es una transformación semigrupo isomorfo a S .
Representación de Cayley [ editar ]
En la 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 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 efectiva porque si ax = bx para todas las x en M , entonces al tomar x igual al elemento de identidad, tenemos a = b.
Para un semigrupo S sin (izquierda o derecha) elemento de identidad, 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 puede representarse 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 [ editar ]
En ciencias de la computación , las representaciones de Cayley se pueden aplicar para mejorar la eficiencia asintótica de los semigrupos al reasociar múltiples multiplicaciones compuestas. La acción dada por la multiplicación a la izquierda da como resultado una multiplicación asociada a la derecha, y viceversa para la acción dada por la multiplicación a 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 Codensity monádica (una representación de Cayley de una mónada , que es un monoide en una categoría de funtor monoidal particular ). [2]
Transformación monoide de un autómata [ editar ]
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 . [3]
Para un lenguaje regular , el monoide sintáctico es isomorfo a la transformación del monoide del autómata mínimo del lenguaje.
No hay comentarios:
Publicar un comentario