Problemas de decisão para semigrupos finitos

Abstract

Os passos mais importantes no desenvolvimento da teoria de semigrupos finitos foram tomados na década de 1950. Motivados pela teoria dos autómatos finitos, Krohn e Rhodes [29] enunciaram um resultado que permitia definir o grau de complexidade de um semigrupo finito S. Este problema tem sido considerado fundamental na teoria de semigrupos finitos e permanece ainda em aberto. Vários outros problemas de decisão têm sido importantes no desenvolvimento da teoria de semigrupos finitos. Um problema de decisão é o de descobrir se existe ou não um algoritmo que é capaz de responder se cada uma das afirmações de uma colecção de instâncias é verdadeira ou não. Se tal algoritmo existir então diz-se que o problema é decidível. Caso contrário diz-se que é indecidível. Neste trabalho apresentam-se alguns exemplos de problemas de decisão, salientando o Problema da Paragem para Maquinas de Turing (problema histórico) e o Problema da Pertença a uma pseudovariedade. Este último problema é uma das questões centrais desta teoria e consiste num problema de decidir se para um dado semigrupo finito este pertence ou não à pseudovariedade. Um outro problema tópico abordado foi o Problema da Palavra, que consiste em decidir quando duas pseudopalavras são ou não iguais numa pseudovariedade. A motivação principal destes problemas na teoria de semigrupos finitos está relacionado com as aplicações às ciências da computação através da ligação entre semigrupos, linguagens racionais e os autómatos. O facto de duas pseudovariedades serem decidíveis não implica, por exemplo, que o seu produto semidirecto seja decidível. No entanto, foram surgindo novos conceitos para tentar obter novas formas para resolver alguns dos problemas de decidabilidade. Nesse sentido surgiu o conceito de mansidão, uma propriedade mais forte que a decidabilidade, com o objectivo de provar a decidabilidade de pseudovariedades. Terminaremos esta monografia com uma breve abordagem destes desenvolvimentos mais recentes.

The most important steps in the development of the ¯nite semigroups theory were done in the 1950 decade. Motivated by the theory of ¯nite automata, Krohn and Rhodes [29], enunciated a result that allowed to de¯ne the degree of com- plexity of a ¯nite semigroup S. This problem has been considered fundamental in the theory of ¯nite semigroups and remains open. Several other decision problems have been important in developing the theory of ¯nite semigroups. One problem of decision is the discovery whether or not there is an algorithm that is able to answer whether each statement of a collection of instances is true or not. If this algorithm exists then it is said that the problem is decidable. Otherwise it is said undecidable. This work presents some examples of decision problems, emphasizing the Halting Problem for Turing machines (historical problem) and the Membership Problem to a pseudovariety. This last problem is one of the central issues of this theory and is the problem of deciding whether a given ¯nite semigroup belongs or not to a gives pseudovariety. Another typical problem addressed was the Word Problem, which is to decide whether or not two pseudowords are equal in a pseudovariety. The main motivation of these problems in the ¯nite semigroups theory is related to the applications of computing science by the link between semigroups, rational languages and automata. The fact that two pseudovarieties is decidable does not imply, for example, that their semidirect product is decidable. However, new concepts were emerging for seeking new ways to solve some decidability problems. In this sense, came the concept of tameness, a property stronger than the decidability, with the aim to prove decidability for pseudovarieties. We end this monograph with a brief approach to these latest developments.