En matemáticas e informática , la teoría de Krohn-Rhodes (o teoría de 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 juntos de una manera libre de retroalimentación (llamado " 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 demostraron un resultado importante 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
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 una corona alterna finita producto de grupos simples finitos , 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 , alfabeto de salida U , entonces uno puede expandir los estados a Q 'de modo que el nuevo autómata A' se incrusta en una cascada de autómatas "simples" e irreducibles: En particular, A es emulado por una cascada de avance de (1) autómatas cuyas transiciones semigrupos son grupos 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 de coordenadas jerárquica muy especial.
Ademá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 transición de algún componente de la cascada, y solo los primos que deben ocurrir como Los divisores de los componentes son los que dividen el semigrupo de transición de A.
Complejidad del grupo
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 campo finito fijo tiene complejidad n (Kambites, 2007).
Un gran problema abierto 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 límites inferiores de complejidad cada vez más precisos (véase, por ejemplo, Rhodes y Steinberg, 2009). Rhodes ha conjeturado que el problema es decidible. [2]
Historia y aplicaciones
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, 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 demostraciones más sencillas y generalizaciones del teorema a 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 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 semigrupo . Las pruebas posteriores contenían simplificaciones importantes utilizando productos de corona finitos de semigrupos de transformación finita. 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 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.
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 de primos" para los autómatas. Los componentes de la descomposición, sin embargo, no son autómatas primos (con el primo definido de 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 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 generalmente requieren la expansión del conjunto de estados, de modo que el autómata expandido cubre (emula) 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 & Nehaniv 2005, 2008).
HP Zeiger (1967) demostró una variante importante llamada descomposición holonómica (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 & 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 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 fue sorprendente para 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 fuerza, y el trabajo anterior (Hartmanis y Stearns) fue 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 holonomía de la descomposición de Krohn-Rhodes extendida con la descomposición relacionada para grupos finitos (las llamadas coordenadas de Frobenius-Lagrange ) usando el sistema de álgebra computarizada GAP .
Las aplicaciones fuera de las teorías de semigrupos y monoides ahora son computacionalmente viables. 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).
Ver también
- Acción de semigrupo
- Semigrupo de transformación
- Relaciones de Green
Notas
- ^ Holcombe (1982) págs. 141-142
- ^ J. Rhodes, discurso de apertura en la Conferencia Internacional sobre Semigroups & Algebraic Engineering ( Aizu , Japón ), 26 de marzo de 1997.
- ^ Morris W. Hirsch , "Prólogo a las aplicaciones de Rhodes de la teoría de los autómatas y el álgebra ". En J. Rhodes, Applications of Automata Theory and Algebra: Via the Mathematical Theory of Complexity to Biology, Physics, Philosophy and Games ", (ed. CL Nehaniv), World Scientific Publishing Co., 2010.
- ^ El flip-flop es el autómata de dos estados con tres operaciones de entrada: la identidad (que deja su estado sin cambios) y las dos operaciones de reinicio (que sobrescriben el estado actual mediante un reinicio a uno en particular de los dos estados). Esto se puede considerar unaunidad de almacenamiento de lectura-escritura deun bit : la identidad corresponde a la lectura del bit (sin alterar su valor), y los dos se restablecen para establecer el valor del bit en 0 o 1. Tenga en cuenta que un restablecimiento es un operador irreversible ya que destruye el valor de bit actualmente almacenado. NB: El semigrupo del flip-flop y todos sus subsemigrupos son irreductibles.
- ↑ Eilenberg 1976, así como Dömösi y Nehaniv, 2005, presentan pruebas que corrigen un error en el artículo de Zeiger.
- ^ Ver también (Tilson 1989)
- ^ CL Nehaniv, Prefacio a (Rhodes, 2009)
Referencias
- Barrington, David A. Mix (1992). "Algunos problemas relacionados con polinomios de Razborov-Smolensky". En Paterson, MS (ed.). Complejidad de la función booleana, Sel. Papilla. Symp., Durham / Reino Unido 1990 . Serie de notas de conferencias de la London Mathematical Society. 169 . págs. 109-128. ISBN 978-0-521-40826-4. Zbl 0769.68041 .
- Diekert, Volker; Kufleitner, Manfred; Steinberg, Benjamin (2012). "El teorema de Krohn-Rhodes y los divisores locales". Fundamenta Informaticae . 116 (1–4): 65–77. arXiv : 1111.1585 . doi : 10.3233 / FI-2012-669 . ISSN 0169-2968 .
- Pál Dömösi; Chrystopher L. Nehaniv (2005). Teoría algebraica de las redes de autómatas: una introducción . Monografías SIAM sobre Matemática Discreta y Aplicaciones. Sociedad de Matemáticas Industriales y Aplicadas. ISBN 978-0-89871-569-9.
- Egri-Nagy, A .; y Nehaniv, CL (2005), "Descomposición jerárquica algebraica de autómatas de estado finito: comparación de implementaciones para la teoría de Krohn-Rhodes", en la 9ª Conferencia Internacional sobre Implementación y Aplicación de Autómatas (CIAA 2004), Kingston, Canadá, 22-24 de julio , 2004, Revised Selected Papers , Editores: Domaratzki, M .; Okhotin, A .; Salomaa, K .; et al. ; Springer Lecture Notes in Computer Science , vol. 3317, págs. 315–316, 2005
- Egri-Nagy, Atila; Nehaniv, Chrystopher L. (verano de 2008). "Sistemas de coordenadas jerárquicas para comprender la complejidad y su evolución con aplicaciones a redes reguladoras genéticas" (PDF) . Vida artificial . 14 (3): 299–312. doi : 10.1162 / artl.2008.14.3.14305 . hdl : 2299/16600 . ISSN 1064-5462 . PMID 18489252 .
- Eilenberg, Samuel (1976). Autómatas, lenguajes y máquinas . Matemática pura y aplicada, Apuntes de matemáticas. Nueva York: Academic Press. ISBN 978-0-12-234001-7. Bret Tilson ha escrito dos capítulos.
- Ésik, Z. (marzo de 2000). "Una prueba del teorema de descomposición de Krohn-Rhodes" . Informática Teórica . 234 (1–2): 287–300. doi : 10.1016 / s0304-3975 (99) 00315-1 . ISSN 0304-3975 .
- Hartmanis, Juris ; Stearns, RE (1966). Teoría de la estructura algebraica de máquinas secuenciales . Prentice Hall. ASIN B0006BNWTE .
- Holcombe, WML (1982). Teoría de autómatas algebraicos . Estudios de Cambridge en Matemáticas Avanzadas. 1 . Prensa de la Universidad de Cambridge . ISBN 978-0-521-60492-5. Zbl 0489.68046 .
- Kambites, Mark (2007). "Sobre la complejidad de Krohn-Rhodes de semigrupos de matrices triangulares superiores". Revista Internacional de Álgebra y Computación . 17 (1): 187-201. CiteSeerX 10.1.1.657.4000 . doi : 10.1142 / S0218196707003548 . ISSN 0218-1967 .
- Krohn, KR; y Rhodes, JL (1962), "Teoría algebraica de las máquinas", Actas del Simposio sobre teoría matemática de los autómatas (editor: Fox, J.), ( Wiley-Interscience )
- Krohn, Kenneth; Rhodes, John (abril de 1965). "Teoría algebraica de máquinas. Teorema de descomposición de I. Prime para semigrupos finitos y máquinas" (PDF) . Transacciones de la American Mathematical Society . 116 : 450–464. doi : 10.2307 / 1994127 . ISSN 0002-9947 . JSTOR 1994127 . Consultado el 18 de septiembre de 2010 .
- Krohn, Kenneth; Rhodes, John L. (agosto de 1968). Arbib, Michael A. (ed.). Teoría algebraica de máquinas, lenguajes y semigrupos . Prensa académica. ISBN 978-0-12-059050-6.
- Lallement, Gerard (1 de marzo de 1971). "Sobre el teorema de descomposición prima para monoides finitos". Teoría de los sistemas informáticos . 5 (1): 8-12. doi : 10.1007 / BF01691462 . ISSN 1433-0490 .
- Meyer, AR; Thompson, C. (1 de junio de 1969). "Observaciones sobre la descomposición algebraica de autómatas" (PDF) . Teoría de los sistemas informáticos . 3 (2): 110-118. CiteSeerX 10.1.1.649.4716 . doi : 10.1007 / BF01746516 . ISSN 1432-4350 .
- John Rhodes; Benjamin Steinberg (17 de diciembre de 2008). La teoría q de semigrupos finitos . Springer Verlag. ISBN 978-0-387-09780-0.
- Straubing, Howard; Thérien, Denis (2002). "Productos de bloque débilmente iterados de monoides finitos" . En Raisbaum, Sergio (ed.). Apuntes de conferencias en Ciencias de la Computación . LATIN 2002: Informática Teórica. 2286 . Berlín: Springer. págs. 91-104. doi : 10.1007 / 3-540-45995-2_13 . ISBN 978-3-540-43400-9. Consultado el 18 de septiembre de 2010 .
- Rhodes, John L. (3 de septiembre de 2009). Nehaniv, Chrystopher L. (ed.). Aplicaciones de la teoría de los autómatas y el álgebra a través de la teoría matemática de la complejidad a la física de estados finitos, la biología, la filosofía y los juegos . Singapur: World Scientific Publishing Company. ISBN 978-981-283-696-0.
- Tilson, Bret (septiembre de 1987). "Categorías como álgebra: un ingrediente esencial en la teoría de los monoides" . Revista de álgebra pura y aplicada . 48 (1–2): 83–198. doi : 10.1016 / 0022-4049 (87) 90108-3 . ISSN 0022-4049 .
- Wells, C. (1980). "Un teorema de Krohn-Rhodes para categorías" . Revista de álgebra . 64 : 37–45. doi : 10.1016 / 0021-8693 (80) 90130-1 . ISSN 0021-8693 .
- Zeiger, HP (abril de 1967). "Síntesis en cascada de máquinas de estados finitos" . Información y control . 10 (4): 419–433. doi : 10.1016 / S0019-9958 (67) 90228-8 . ISSN 1462-3889 .Errata: Información y control 11 (4): 471 (1967), más errata.
Otras lecturas
- Rhodes, John L. (2010). Chrystopher L. Nehaniv (ed.). Aplicaciones de la teoría de autómatas y el álgebra: a través de la teoría matemática de la complejidad a la biología, la física, la psicología, la filosofía y los juegos . World Scientific Pub Co Inc. ISBN 978-981-283-696-0.
- Rhodes, John ; Steinberg, Benjamin (17 de diciembre de 2008). La teoría q de semigrupos finitos . Springer Verlag. ISBN 978-0-387-09780-0.
- Straubing, Howard (1994). Autómatas finitos, lógica formal y complejidad de circuitos . Progreso en Informática Teórica. Basilea: Birkhäuser. ISBN 978-3-7643-3719-3. Zbl 0816.68086 .
enlaces externos
- Prof. John L. Rhodes, página web de la Universidad de California en Berkeley
- SgpDec: Composición jerárquica y descomposición de grupos de permutación y semigrupos de transformación , desarrollado por A. Egri-Nagy y CL Nehaniv . Paquete de software de código abierto para el sistema de álgebra computacional GAP .
- John L. Rhodes (2010). Chrystopher L. Nehaniv (ed.). Aplicaciones de la teoría de autómatas y el álgebra: a través de la teoría matemática de la complejidad a la biología, la física, la psicología, la filosofía y los juegos . World Scientific Pub Co Inc. ISBN 978-981-283-696-0.
- Una introducción al Teorema de Krohn-Rhodes (Sección 5); parte del MOOC Complexity Explorer Introducción a la Renormalización del Instituto Santa Fe , por Simon DeDeo.