Mansidão de supremos envolvendo a pseudovariedade LSl

Sala 0.03 – Dep. Matemática/FCUP
Monday, 24 May, 2010 - 13:30

Uma pseudovariedade diz-se decidível se existe um algoritmo que decida se um dado semigrupo pertence à pseudovariedade. O supremo VvW 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 VvW na literatura. Pretende-se, neste seminário, abordar o problema da κ-mansidão de supremos da forma LSlvV, 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.

Speaker: 

Conceição Nogueira (ESTG-IPLeiria / Centro de Matemática UM)