En matemáticas e informática , la teoría de Krohn-Rhodes (o teoría de los autómatas algebraicos ) es una aproximación al estudio de semigrupos finitos y autómatas que busca descomponerlos en términos de componentes elementales. Estos componentes corresponden a semigrupos aperiódicos finitos y grupos simples finitos que se combinan sin retroalimentación (llamado " producto corona " o "cascada").
Krohn y Rhodes encontraron una descomposición general para autómatas finitos . Los autores descubrieron y demostraron un importante resultado inesperado en la teoría de semigrupos finitos, revelando una conexión profunda entre los autómatas finitos y los semigrupos.
Sea T un semigrupo. Un semigrupo S que es una imagen homomórfica de un subsemigrupo de T se dice que es divisor de T.
El teorema de Krohn-Rhodes para semigrupos finitos establece que cada semigrupo finito S es un divisor de un producto corona alternante finito de grupos simples finitos , cada uno de ellos 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 , alfabeto de salida U , entonces se pueden expandir los estados a Q' de modo que el nuevo autómata A' se incruste en una cascada de autómatas "simples" e irreducibles: en particular, A es emulado por una cascada de retroalimentación de (1) autómatas cuyos semigrupos de transformación son grupos simples finitos 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 que A . Aquí, tanto los estados como las entradas de los autómatas en cascada tienen una forma de coordenadas jerárquica muy especial.
Es más, cada grupo simple ( primo ) o semigrupo irreducible no grupal (subsemigrupo del monoide flip-flop ) que divide el semigrupo de transformación de A debe dividir el semigrupo de transformación de algún componente de la cascada, y sólo los primos que deben ocurrir como Los divisores de los componentes son aquellos que dividen el semigrupo de transformación de A.
La complejidad de Krohn-Rhodes (también llamada complejidad de grupo o simplemente complejidad ) de un semigrupo finito S es el menor número de grupos en una corona producto de grupos finitos y semigrupos aperiódicos finitos de los cuales S es 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 cualquier complejidad entera no negativa . Por ejemplo, para cualquier n mayor 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 importante problema abierto en la teoría de semigrupos finitos es la capacidad de decisión 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 límites inferiores cada vez más precisos sobre la complejidad (ver, por ejemplo, Rhodes y Steinberg, 2009). Rhodes ha conjeturado que el problema es decidible. [2]
En una conferencia celebrada en 1962, Kenneth Krohn y John Rhodes anunciaron un método para descomponer un autómata finito (determinista) en componentes "simples" que son en sí mismos autómatas finitos. Este trabajo conjunto, que tiene implicaciones para la filosofía [ cita necesaria ] , comprendió tanto la tesis doctoral de Krohn en la Universidad de Harvard como la tesis doctoral de Rhodes en el MIT . [3] Desde entonces se han publicado pruebas más simples y generalizaciones del teorema a estructuras infinitas (consulte el capítulo 4 del libro de Rhodes y Steinberg de 2009, The q-Theory of Finite Semigroups, para obtener una descripción general).
En el artículo de 1965 de Krohn y Rhodes, la demostración del teorema sobre la descomposición de autómatas finitos (o, equivalentemente, máquinas secuenciales) hizo un uso extensivo de la estructura algebraica de semigrupos . Las pruebas posteriores contenían importantes simplificaciones 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 los que los primos son los grupos finitos simples), a todos los semigrupos de transformación finitos (para los cuales los primos son nuevamente los grupos finitos simples más todos los subsemigrupos del "flip-flop" ( véase más arriba)). Tanto la descomposición de grupos como la de autómatas finitos más general requieren expandir el conjunto de estados de lo general, pero permiten la misma cantidad de símbolos de entrada. En general, estos están integrados en una estructura más grande con un "sistema de coordenadas" jerárquico.
Hay que tener cuidado al comprender la noción de "primo", ya que Krohn y Rhodes se refieren explícitamente a su teorema como un "teorema de descomposición prima" para autómatas. Los componentes de la descomposición, sin embargo, no son autómatas primos (con los primos definidos de forma ingenua); más bien, la noción de primo es más sofisticada y algebraica: los semigrupos y grupos asociados a los autómatas constituyentes de la descomposición son primos (o irreducibles) en un sentido algebraico estricto y natural con respecto al producto corona ( Eilenberg , 1976). Además, a diferencia de los teoremas de descomposición anteriores, las descomposiciones de Krohn-Rhodes generalmente requieren la expansión del conjunto de estados, de modo que el autómata expandido cubra (emule) al que se está descomponiendo. 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 estuvieron disponibles (Egri-Nagy y Nehaniv 2005, 2008).
HP Zeiger (1967) demostró una variante importante llamada descomposición de la holonomía (Eilenberg 1976). [nb 2] 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 previamente desarrollada 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 y 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 monoides y 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. [nota 3]
El teorema de Krohn-Rhodes para semigrupos/monoides es un análogo del teorema de Jordan-Hölder para grupos finitos (para semigrupos/monoides en lugar de grupos). Como tal, el teorema es un resultado profundo e importante en la teoría de semigrupos/monoide. El teorema también sorprendió a muchos matemáticos e informáticos [nb 4] ya que anteriormente se creía ampliamente que los axiomas de semigrupo/monoide eran demasiado débiles para admitir un teorema de estructura de alguna solidez, y el trabajo anterior (Hartmanis & Stearns) solo era 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 holonómica de la descomposición de Krohn-Rhodes ampliada con la descomposición relacionada para grupos finitos (las llamadas coordenadas de Frobenius-Lagrange) utilizando el sistema de álgebra informática GAP .
Las aplicaciones fuera de las teorías de semigrupos y 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 (ver, por ejemplo, Rhodes 2009).