Teorema de Krohn-Rhodes

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa
Ambox important.svg
Foram assinalados vários aspectos a serem melhorados 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]

  1. Holcombe (1982) pp.141-142
  1. 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.
  2. J. Rhodes, Keynote talk at the International Conference on Semigroups & Algebraic Engineering (Aizu, Japan), 26 de Março 1997.
  3. 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.
  4. Eilenberg 1976, também como Dömösi e Nehaniv, 2005, provas atuais que corrigem um erro no artigo de Zeiger.
  5. Ver também (Tilson 1989)
  6. C.L. Nehaniv, Preface to (Rhodes, 2009)

Referências[editar | editar código-fonte]

Bibliografia[editar | editar código-fonte]

Ligações externos[editar | editar código-fonte]