O problema da ω-palavra para pseudovariedades de semigrupos

• Autor(es): Nogueira, Conceição Veloso
• Data: 2006
• Identificador Persistente: http://hdl.handle.net/1822/6398
• Origem: RepositóriUM - Universidade do Minho
• Tipo de Documento: Dissertação de Mestrado
• Idioma: Português
• Orientador(es): Costa, José Carlos Cruz da

Descrição

Mestrado Matemática A teoria de semigrupos começou, de certa forma, com um resultado sobre semigrupos finitos: o Teorema de Suschekewitsch de 1928 descrevendo a estrutura dos semigrupos finitos sem ideais próprios. Nos anos 50, o desenvolvimento da teoria dos autómatos finitos trouxe motivação nova para o estudo de semigrupos finitos. No entanto, só desde os anos 70 é que esta teoria tem obtido cada vez mais atenção por parte dos investigadores sendo notório o seu crescimento. Desde meados dos anos 60 surgiu a questão de como calcular a complexidade de um semigrupo finito S, questão esta, que quarenta anos volvidos continua a ser a principal motivação para muitos trabalhos sobre semigrupos finitos. O problema da decidibilidade para determinadas pseudovariedades é outro que continua a ocupar os investigadores. Neste trabalho de síntese apresenta-se um pequeno estudo sobre o problema da ω-palavra para as pseudovariedades Sl, N, K, D, LI, J e LSl. É ainda referida uma solução para o problema da ω-palavra sobre R, o qual se provou recentemente ser decidível [13]. O problema da ω-palavra é o de decidir, para uma pseudovariedade e duas ω-palavras dadas, se a pseudovariedade verifica a igualdade das ω-palavras. Um dos principais motivos de interesse deste estudo está relacionado com o facto de o problema da ω-palavra ser decidível para V poder aparecer como uma das condições necessárias para que a pseudovariedade V seja mansa. A noção de mansidão foi introduzida recentemente numa tentativa de definir propriedades mais fortes do que a decidibilidade que pudessem ser úteis para provar a decidibilidade de pseudovariedades definidas por operadores, tais como produto semidirecto, supremo, produto de Mal’cev, etc. In a way, the semigroup theory started with a result about finite semigroup: the 1928 Suschekewitsch’s theorem, describing the structure of finite semigroups without proper ideals. On the 50’s, the development of the finite automata theory brought a new motivation for the study of finite semigroups. However, it’s only since the 70’s that this theory has obtained more and more attention from researchers experiencing a notable growth. The question of how to calculate the complexity of a finite semigroup S has emerged in the midle 60’s, question that even after forty years, is still the main motivation for many works about finite semigroups. The decidability problem for some pseudovarieties is another problem that still occupies researchers. In this synthesis work is presented a small study about the ω-word problem in the pseudovarieties Sl, N, K, D, LI, J e LSl. It’s also referred a solution of the ω-word problem over R, which has been recently proved as being decidable [13]. The ω-word problem is the problem of deciding, for a pseudovariety and two given ω-terms, if the pseudovariety verifies the equality of the ω-terms. One of the main interests of this study is related with the fact that the ω-word problem being decidable in V may appear as one of the necessary conditions for the pseudovariety V to be tame. The notion of tameness has recently emerged as a tentative of defining stronger properties others than decidability that could be useful to prove the decidability of pseudovarieties defined by operators, such as the semidirect product, join, Mal’cev product, etc.