Resumo: Uma pseudovariedade diz-se decidível se
existe um algoritmo que decida se um dado semigrupo pertence à
pseudovariedade. O supremo *V*v*W* de duas pseudovariedades *V* e *W* é a menor pseudovariedade contendo ambas *V* e *W*.
Um resultado bem conhecido de D. Albert, R. Baldinger e J. Rhodes
estabelece que o supremo de duas pseudovariedades decidíveis pode não
ser decidível. A decidibilidade também não é preservada por alguns
outros operadores comuns de pseudovariedades.
Uma ideia
recentemente explorada por vários autores consiste na imposição de
propriedades mais fortes nas pseudovariedades sob as quais os operadores
serão aplicados de forma a garantir que as pseudovariedades resultantes
serão decidíveis. Neste contexto J. Almeida introduziu uma forma mais
forte de decidibilidade, chamada hiperdecidibilidade, a qual foi mais
tarde refinada em colaboração com B. Steinberg, originando a noção de
mansidão.
A mansidão é parametrizada por uma assinatura
implícita ?. A assinatura canónica ?, contendo a multiplicação e a
(?-1)-potência, é uma das assinaturas mais usadas. Existem vários
exemplos de pseudovariedades ?-mansas da forma *V*v*W* na literatura. Pretende-se, neste seminário, abordar o problema da ?-mansidão de supremos da forma *LSl*v*V*, onde *LSl*
denota a pseudovariedade dos semigrupos finitos localmente
semi-reticulados, e apresentar algumas aplicações. Note-se que a
pseudovariedade *LSl*
é associada pela correspondência de Eilenberg com a classe das
linguagens localmente testáveis. Devido à sua importância, as linguagens
localmente testáveis e a pseudovariedade *LSl* têm sido muito estudadas. |