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 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 (llamados " producto de 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 probaron un resultado importante inesperado en la teoría de los semigrupos finitos, que revela 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 de corona alterna finita de grupos simples finitos , cada uno de los cuales es 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 A finito con estados Q y un conjunto de entrada I , el alfabeto de salida U , entonces uno puede expandir los estados a Q' de tal 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 avance de (1) autómatas cuyos semigrupos de transiciones 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árquicas muy especial.
Además, cada grupo simple ( primo ) o semigrupo irreductible no grupal (subsemigrupo del monoide flip-flop ) que divide el semigrupo de transformación de A debe dividir el semigrupo de transición de alguna componente de la cascada, y solo los primos que deben ocurrir como los divisores de las componentes son los que dividen el semigrupo de transición de A.