Teorema de Krohn-Rhodes
 | Foram assinalados vários problemas nesta página ou se(c)ção: |
Em matemática e na ciência da computação, o Teorema de Krohn-Rhodes (ou Teoria dos Autômatos Algebraica) é uma abordagem para o estudo dos semigrupos e automatas finitos que busca decompô-los em termos de componentes elementares. Esses componentes correspondem a semigrupos finitos aperiódicos e grupos simples finitos que são combinados de uma maneira livre de feedback (chamado de produtos coroa ou cascata).
Krohn e Rhodes encontraram a decomposição geral para autômatos finitos. Ao fazer sua pesquisa, no entanto, os autores descobriram e provaram um grande resultado inesperado na teoria dos semigrupos finitos, revelando uma profunda conexão entre autômatos finitos e semigrupos.
Definição e descrição do Teorema de Krohn-Rhodes[editar | editar código-fonte]
Um semigrupo S que é uma imagem homomorfica de um subsemigrupo de T é dito ser um divisor de T.
O Teorema de Krohn-Rhodes para semigrupos finitos afirma que cada semigrupo finito S é um divisor de um produto coroa finito alternante de um Grupo simples finito, cada divisor de S, e finitos semigrupos aperiodicos. (que não contenha nenhum subgrupo não trivial).[1]
Na formulação dos autômatos, o Teorema de Krohn-Rhodes para autômatos finitos afirma que dado um autômato finito A com estados Q e conjunto de entradas I, alfabeto de saída U, então um pode expandir os estados para Q de tal forma que o novo autômato A' pode ser imerso em uma cascata de autômatos irredutíveis "simples": Em particular, A' é emulado por uma cascata feed-foward de (1) autômatos quais os semigrupos de transição são finitos grupos simples e (2) autômatas que são bancos de flip-flops rodando em paralelo.[nb 1] O novo autômato A' tem a mesmos símbolos de entrada e saídas de A. Aqui, ambos os estados e as entradas dos autômatos em cascata tem uma forma coordenada hierárquica muito especial.
Além disso, cada grupo simples (primo) ou não-grupo semigrupo irredutível (subsemigrupo do monoide do flip-flop) que divide o semigrupo de transformação de A deve dividir o semigrupo de transição de algum componente da cascata, e somente os primos que têm que ocorrer como divisores dos componentes são aqueles que dividem o semigrupo de transição A 's.
Complexidade do grupo[editar | editar código-fonte]
A Complexidade de Krohn-Rhodes (também chamada Complexidade do grupo ou somente complexidade) de um semigrupo finito S é o numero minimo de grupos em um produto coroa de grupos finitos e semigrupos aperiódicos finitos o qual S é um divisor.
Todos semigrupos aperiódicos finitos têm complexidade 0, enquanto grupos não-triviais finitos tem complexidade 1. De fato, existem semigrupos com complexidade igual à qualquer inteiro positivo. Por exemplo, para cada n maior que 1, o semigrupo multiplicativo de todos (n+1)x(n+1) matriz triangular superior sobre qualquer corpo fixo finito têm complexidade n (Kambites, 2007).
Um grande problema em aberto na teoria dos semigrupos finitos é a decidibilidade de complexidade: dado uma tabuada de multiplicar para um semigrupo finito, existe um algoritmo que irá computar a complexidade Krohn-Rhodes dele? Limitantes superiores e limitantes inferiores ainda mais precisos da complexidade têm sido encontrados (veja, e.g. Rhodes & Steinberg, 2009). Rhodes conjecturou que o problema é decidivel. [nb 2]
História e Aplicações[editar | editar código-fonte]
Em uma conferência em 1962, Kenneth Krohn e John Rhodes anunciaram um metodo para decompor autômatos finitos determinísticos em componentes "simples" que são autômatos finitos eles mesmos. Esse trabalho em conjunto, cujas implicações para a filosofia, compreende tanto a tese de doutorado de Krohn na Universidade de Harvard quanto a tese de doutorado de Rhodes no MIT. [nb 3] Provas simples e generalizações do teorema de estruturas infinitas foram publicados desde então (ver capitulo 4 do livro de Steinberg e Rhodes de 2009, The q-Theory of Finite Semigroups para uma visão global do assunto).
Em um artigo de 1965 publicado por Krohn e Rhodes, a prova do teorema do teorema sobre a decomposição de autômatos finitos (ou equivalentemente maquinas sequenciais (ou, de forma equivalente máquinas sequenciais) fizeram uso extensivo da estrutura de semigrupos algébricos. Provas posteriores continham importantes simplificações usando produtos coroa finito de semigrupos de transformação finitos. O teorema generaliza o decomposição Jordan-Hölder para grupos finitos (em que os números primos são os grupos finitos simples), para todos os semigrupos de transformação finita (por que os números primos são novamente os grupos finitos simples, mais todos subsemigroups do "flip flop-" (veja acima)). Tanto o grupo e decomposição autômatos finitos mais geral requerem a expansão do Estado-set da geral, mas permitir que o mesmo número de símbolos de entrada. No caso geral, estes são incorporados numa estrutura hierárquica com um maior "sistema de coordenadas".
Um deve ter cuidado na compreensão da noção do "primos" como Krohn e Rhodes explicitamente se referem no seu teorema como um "teorema de decomposição de primos" para autômatos. Os componentes na decomposição , no entanto , não são autômatos primos (com primo definido de uma forma ingênua); em vez disso, a noção de primo é mais sofisticada e algébrica: os semigrupos e grupos associados à autômatos constituinte da decomposição são primos (ou irredutíveis) em um sentido estrito e natural com respeito ao produto coroa ( Eilenberg , 1976). Além disso, ao contrário de teoremas de decomposição anteriores, a decomposição Krohn-Rhodes geralmente requerem expansão do conjunto de estados, de modo que o autômato expandidos abranja (emula) o que está sendo decomposto. Esses fatos fizeram o teorema difícil de entender, e desafiador quando se pensava em aplicar-lo de forma prática até recentemente, quando as implementações computacionais se tornaram disponíveis ( Egri -Nagy & Nehaniv 2005, 2008 ) .
H.P. Zeiger (1967) provou uma importante variante chamada de decomposição holonomia (Eilenberg 1976).[nb 4] O método de holonomia parece ser relativamente eficiente e tem sido implementado computacionalmente por A. Egri-Nagy (Egri-Nagy & Nehaniv 2005).
Meyer e Thompson (1969) dão uma versão da decomposição Krohn-Rhodes para autômatos finitos que é equivalente à decomposição previamente desenvolvida por Hartmanis e Stearns, mas para decomposições uteis, a noção de expandir o grupo de estados do autômato original é essencial (para os casos de autômatos não-permutados).
Muitas provas e construções já existem de decomposições Krohn-Rhodes (por exemplo, [Krohn, Rhodes & Tilson 1968], [Ésik 2000]), com o método de holonomia geralmente sendo o mais popular e eficiente (embora não sendo todos os casos). Devido a relação intima entre monoides e categorias, a versão do Teorema de Krohn-Rhodes é aplicável para a Teoria das categorias. Essa observação e a prova de um resultado análogo foram oferecidos por Wells (1980).[nb 5]
O teorema de Krohn-Rhodes para semigrupos/monoides é um analogo do Teorema de Jordan-Hölder para grupos finitos (para semigrupos/monoides em vez de grupos). Como tal, o teorema é um resultado profundo e importante na teoria de semigrupos/monoides. O teorema também foi surpreendente para muitos matemáticos e cientistas da computação [nb 6] uma vez que já havia uma crença que os axiomas de semigrupos/monoides eram muito fracos para admitirem uma estrutura de teorema de qualquer força, e o trabalho anterior (Hartmanis & Stearns) só foi capaz de mostrar resultados de decomposição de autômatos finitos eram muito mais rígidos e muito menos gerais.
Trabalhos por Egri-Nagy e Nehaniv (2005, 2008-) continuam a automatizar a versão holonomia da Decomposição Estendida de Krohn-Rhodes com a decomposição para grupos finitos relacionada (tão chamada Coordenadas de Frobenius-Lagrange usando o sistema de algebra computacional GAP).
Aplicações fora da teoria de semigrupos ou monoides agora são computacionalmente factíveis. Elas incluem computações na Biologia e em sistemas bioquímicos (ex: Egri-Nagy & Nehaniv, 2008), Inteligência Artificial, estados finitos na física, psicologia e Teoria dos jogos (veja, por exemplo, Rhodes 2009).
Ver também[editar | editar código-fonte]
Notas[editar | editar código-fonte]
- ↑ Holcombe (1982) pp.141-142
- ↑ O flip-flop é um autômato de dois estados com três operações de entrada: a identidade (que mantém ele no mesmo estado) e as duas operações de reset (que substitui o estado atual resetando-o para um dos dois estados em particular). Isso pode ser considerado uma unidade leitura-escrita de memoria de um-bit: a identidade corresponde a leitura do bit (deixando seu valor inalterado), e as duas operações de reset como a de escrita dos valores para o bit 0 ou 1. Note que o reset é um operador irreversível já que ele substitui o valor atual do bit que está guardado. NB: O semigrupo do flip-flop e todos seus subsemigrupos são irreduzíveis.
- ↑ J. Rhodes, Keynote talk at the International Conference on Semigroups & Algebraic Engineering (Aizu, Japan), 26 de Março 1997.
- ↑ Morris W. Hirsch, "Foreword to Rhodes' Applications of Automata Theory and Algebra". Em J. Rhodes, Applications of Automata Theory and Algebra: Via the Mathematical Theory of Complexity to Biology, Physics, Philosophy and Games" (ed. C. L. Nehaniv), World Scientific Publishing Co., 2010.
- ↑ Eilenberg 1976, também como Dömösi e Nehaniv, 2005, provas atuais que corrigem um erro no artigo de Zeiger.
- ↑ Ver também (Tilson 1989)
- ↑ C.L. Nehaniv, Preface to (Rhodes, 2009)
Referências[editar | editar código-fonte]
- Barrington, David A. Mix (1992). «Some problems involving Razborov-Smolensky polynomials». In: Paterson, M.S. Boolean function complexity, Sel. Pap. Symp., Durham/UK 1990. Col: London Mathematical Society Lecture Notes Series. 169. [S.l.: s.n.] pp. 109–128. ISBN 0-521-40826-1. Zbl 0769.68041
- Pál Dömösi; Chrystopher L. Nehaniv (2005). Algebraic theory of automata networks: an introduction. [S.l.]: Society for Industrial Mathematics. ISBN 978-0-89871-569-9
- Egri-Nagy, A.; and Nehaniv, C. L. (2005), "Algebraic Hierarchical Decomposition of Finite State Automata: Comparison of Implementations for Krohn–Rhodes Theory", in 9th International Conference on Implementation and Application of Automata (CIAA 2004), Kingston, Canada, July 22–24, 2004, Revised Selected Papers, Editors: Domaratzki, M.; Okhotin, A.; Salomaa, K.; et al.; Springer Lecture Notes in Computer Science, Vol. 3317, pp. 315–316, 2005
- Egri-Nagy, Attila; Nehaniv, Chrystopher L. (verão de 2008). «Hierarchical Coordinate Systems for Understanding Complexity and its Evolution with Applications to Genetic Regulatory Networks». Massachusetts Institute of Technology. Artificial Life. 14 (3): 299–312. ISSN 1064-5462. doi:10.1162/artl.2008.14.3.14305
- Eilenberg, Samuel (1976). Automata, Languages and Machines. Col: Pure and applied mathematics, Lecture notes in mathematics. New York: Academic Press. ISBN 978-0-12-234001-7 Two chapters are written by Bret Tilson.
- Ésik, Z. (março de 2000). «A proof of the Krohn–Rhodes decomposition theorem». Essex, UK: Elsevier. Theoretical Computer Science. 234 (1–2): 287–300. ISSN 0304-3975. doi:10.1016/s0304-3975(99)00315-1
- Hartmanis, Juris; Stearns, R. E. (1966). Algebraic structure theory of sequential machines. [S.l.]: Prentice–Hall. ASIN B0006BNWTE
- Holcombe, W.M.L. (1982). Algebraic automata theory. Col: Cambridge Studies in Advanced Mathematics. 1. [S.l.]: Cambridge University Press. ISBN 0-521-60492-3. Zbl 0489.68046
- Kambites, Mark (2007). «On the Krohn–Rhodes complexity of semigroups of upper triangular matrices». International Journal of Algebra and Computation. 17 (1): 187–201. ISSN 0218-1967. doi:10.1142/S0218196707003548
- Krohn, K. R.; and Rhodes, J. L. (1962), "Algebraic theory of machines", Proceedings of the Symposium on Mathematical Theory of Automata (editor: Fox, J.), (Wiley–Interscience)
- Krohn, Kenneth; Rhodes, John (abril de 1965). «Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines» (PDF). American Mathematical Society. Transactions of the American Mathematical Society. 116: 450–464. ISSN 0002-9947. doi:10.2307/1994127. Consultado em 18 de setembro de 2010
- Krohn, Kenneth; Rhodes, John L. (agosto de 1968). Arbib, Michael A., ed. Algebraic Theory of Machines, Languages and Semigroups. [S.l.]: Academic Press. ISBN 978-0-12-059050-6
- Lallement, Gerard (1 de março de 1971). «On the prime decomposition theorem for finite monoids». New York: Springer. Theory of Computing Systems. 5 (1): 8–12. ISSN 1433-0490. doi:10.1007/BF01691462. Consultado em 18 de setembro de 2010
- Meyer, A. R.; Thompson, C. (1 de junho de 1969). «Remarks on algebraic decomposition of automata» (PDF). New York: Springer. Theory of Computing Systems. 3 (2): 110–118. ISSN 1432-4350. doi:10.1007/BF01746516
- John Rhodes; Benjamin Steinberg (17 de dezembro de 2008). The q-theory of finite semigroups. [S.l.]: Springer Verlag. ISBN 978-0-387-09780-0
- Straubing, Howard; Thérien, Denis (2002). «Weakly iterated block products of finite monoids». In: Raisbaum, Sergio. Lecture Notes in Computer Science. LATIN 2002: Theoretical Informatics. 2286. Berlin: Springer. pp. 91–104. ISBN 978-3-540-43400-9. doi:10.1007/3-540-45995-2_13. Consultado em 18 de setembro de 2010
- Rhodes, John L. (3 de setembro de 2009). Nehaniv, Chrystopher L., ed. Applications of Automata Theory and Algebra via the Mathematical Theory of Complexity to Finite-State Physics, Biology, Philosophy, and Games. Singapore: World Scientific Publishing Company. ISBN 978-981-283-696-0
- Tilson, Bret (setembro de 1987). «Categories as algebra: an essential ingredient in the theory of monoids». North-Holland. Journal of Pure and Applied Algebra. 48 (1–2): 83–198. ISSN 0022-4049. doi:10.1016/0022-4049(87)90108-3
- Wells, C. (1980). «A Krohn–Rhodes theorem for categories». Elsevier. Journal of Algebra. 64: 37–45. ISSN 0021-8693. doi:10.1016/0021-8693(80)90130-1
- Zeiger, H. P. (abril de 1967). «Cascade synthesis of finite state machines». Churchill Livingstone. Information and Control. 10 (4): 419–433. ISSN 1462-3889. doi:10.1016/S0019-9958(67)90228-8 Erratum: Information and Control 11(4): 471 (1967), plus erratum.
Bibliografia[editar | editar código-fonte]
- Rhodes, John L. (2010). Chrystopher L. Nehaniv, ed. Applications of automata theory and algebra: via the mathematical theory of complexity to biology, physics, psychology, philosophy, and games. [S.l.]: World Scientific Pub Co Inc. ISBN 978-981-283-696-0
- Rhodes, John; Steinberg, Benjamin (17 de dezembro de 2008). The q-theory of finite semigroups. [S.l.]: Springer Verlag. ISBN 978-0-387-09780-0
- Straubing, Howard (1994). Finite automata, formal logic, and circuit complexity. Col: Progress in Theoretical Computer Science. Basel: Birkhäuser. ISBN 3-7643-3719-2. Zbl 0816.68086
Ligações externas[editar | editar código-fonte]
- Prof. John L. Rhodes, University of California at Berkeley webpage
- SgpDec: Hierarchical Composition and Decomposition of Permutation Groups and Transformation Semigroups, developed by A. Egri-Nagy and C. L. Nehaniv. Open-source software package for the GAP computer algebra system.
- John L. Rhodes (2010). Chrystopher L. Nehaniv, ed. Applications of automata theory and algebra: via the mathematical theory of complexity to biology, physics, psychology, philosophy, and games. [S.l.]: World Scientific Pub Co Inc. ISBN 978-981-283-696-0