En matemáticas e informática , la teoría de Krohn-Rhodes (o teoría de autómatas algebraicos ) es un enfoque para el 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 simples finitos que se combinan de manera libre de retroalimentación (lo que se denomina " producto corona " o "cascada").
Krohn y Rhodes descubrieron una descomposición general para los autómatas finitos . Los autores descubrieron y demostraron un resultado inesperado e importante 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 un divisor de T.
El teorema de Krohn-Rhodes para semigrupos finitos establece que cada semigrupo finito S es un divisor de un producto finito en corona alternada de grupos simples finitos , cada uno 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 uno puede expandir los estados a Q' de tal manera que el nuevo autómata A' se incruste en una cascada de autómatas "simples" irreducibles: En particular, A es emulada por una cascada de avance de (1) autómatas cuyos semigrupos de transformación son grupos simples finitos y (2) autómatas que son bancos de flip-flops que funcionan 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.
Además, cada grupo simple ( primo ) o semigrupo irreducible no grupo (subsemigrupo del monoide flip-flop ) que divide al semigrupo de transformación de A debe dividir al semigrupo de transformación de algún componente de la cascada, y sólo los primos que deben aparecer como divisores de los componentes son los que dividen al 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 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 cada 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 cuerpo finito fijo tiene complejidad n (Kambites, 2007).
Un problema abierto de gran importancia 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 multiplicación ? Se han obtenido límites superiores y límites inferiores cada vez más precisos para la complejidad (véase, por ejemplo, Rhodes y Steinberg, 2009). Rhodes ha conjeturado que el problema es decidible. [2]
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 en sí mismos autómatas finitos. Este trabajo conjunto, que tiene implicaciones para la filosofía [ cita requerida ] , 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 de semigrupos algebraicos. Demostraciones 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 los que los primos son los grupos simples finitos), a todos los semigrupos de transformación finitos (para los que los primos son nuevamente los grupos simples finitos más todos los subsemigrupos del "flip-flop" (ver arriba)). Tanto la descomposición de autómatas finitos en grupo como la 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.
Hay que 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 de primos" para autómatas. Sin embargo, los componentes de la descomposición no son autómatas primos (con primo definido de una manera 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 de 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 difícil de aplicar de manera práctica, hasta hace poco, cuando estuvieron disponibles las implementaciones computacionales (Egri-Nagy y Nehaniv 2005, 2008).
HP Zeiger (1967) demostró una variante importante llamada descomposición holonomía (Eilenberg 1976). [nb 2] El método holonomía parece ser relativamente eficiente y ha sido implementado computacionalmente por A. Egri-Nagy (Egri-Nagy y 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 demostraciones y construcciones de descomposiciones de Krohn-Rhodes (p. ej., [Krohn, Rhodes y Tilson 1968], [Ésik 2000], [Diekert et al. 2012]), siendo el método de la 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 demostración de un resultado análogo. [nb 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/monoides. El teorema también sorprendió a muchos matemáticos y científicos informáticos [nb 4] ya que anteriormente se había creído ampliamente que los axiomas de semigrupos/monoides eran demasiado débiles para admitir un teorema de estructura de alguna fuerza, y el trabajo previo (Hartmanis & Stearns) solo pudo 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 holonomía de la descomposición de Krohn-Rhodes extendida con la descomposición relacionada para grupos finitos (las llamadas coordenadas de Frobenius-Lagrange) utilizando el sistema de álgebra computacional GAP .
Actualmente, son factibles computacionalmente otras aplicaciones que no sean las de las teorías de semigrupos y monoides, como los cálculos en biología y sistemas bioquímicos (p. ej., 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).