Universidade do Minho  

           
 
  Autenticação/Login
 
Contacts
Site Map
   
  print
 
back 
Mansidão de supremos envolvendo a pseudo-variedade LSl

Abstract:  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.
 
back 
 
  © 2024 Universidade do Minho  - Legal Terms  - updated by CMAT Símbolo de Acessibilidade na Web D.