Resumo: Uma pseudovariedade de semigrupos é uma classe de semigrupos finitos fechada para subsemigrupos, imagens homomorfas e produtos directos finitos. Esta noção foi introduzida por Eilenberg em 1976, quando provou o
seu ?teorema das variedades? que estabelece uma correspondência
biunívoca entre estas classes de semigrupos e certas classes
(variedades) de linguagens racionais.
Uma pseudovariedade V diz-se decidível se existe um algoritmo que determine se um dado semigrupo pertence a V.
Um dos problemas centrais da teoria de semigrupos finitos é o de
estabelecer a decidibilidade (ou a indecibilidade) de pseudovariedades,
sendo motivado principalmente pelo teorema das variedades de Eilenberg e
pelo problema da complexidade (de Krohn-Rhodes) de um semigrupo, que
permanece em aberto há 40 anos.
O supremo VÚW de duas pseudovariedades V e W é a menor pseudovariedade que contém V e W. O cálculo de supremos de pseudovariedades é um problema difícil em geral como o mostra um resultado de Albert, Baldinger e Rhodes, de 1992, que
estabelece que o supremo de duas pseudovariedades decidíveis pode ser
indecidível. O objectivo deste seminário é o de apresentar um breve
resumo sobre o problema do cálculo do supremo de duas pseudovariedades.
Começaremos por recordar alguns resultados históricos e explicar algumas
das técnicas utilizadas, e terminaremos com a apresentação de
resultados recentes. |