Propriedades algorítmicas envolvendo a pseudovariedade LSl

Abstract

Os problemas de decidibilidade incluem-se entre os mais importantes e mais frutíferos da área dos semigrupos finitos e linguagens formais. É sabido que a decidibilidade não é preservada por alguns dos operadores de pseudovariedades mais comuns, tais como o supremo, o produto semidirecto, o produto de Mal’cev, entre outros [1, 58, 25]. 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 Almeida introduziu uma forma mais forte de decidibilidade, chamada hiperdecidibilidade [5], a qual foi mais tarde refinada em colaboração com Steinberg [16, 17], originando a noção de mansidão. Recentemente foi proposta por Almeida [7] uma extensão da noção de mansidão, designada por mansidão completa.

A noção de mansidão (e suas generalizações) revelou-se uma das mais promissoras para a obtenção de resultados de decidibilidade de pseudovariedades. Motivados por esta observação, dedicamos a parte final deste trabalho a estas noções: mostramos que LSl é completamente mansa e provamos a mansidão de pseudovariedades supremo envolvendo LSl, onde LSl denota a pseudovariedade dos semi-reticulados locais.

Anteriormente, determinamos uma base de ω-identidades para a ω-variedade gerada por LSl. Estudamos também uma outra propriedade algorítmica, relacionada com a mansidão, da pseudovariedade LSl: o cálculo dos seus conjuntos pontuais e pontuais idempotentes.

Decidability problems are among the most important and fruitful of the area of finite semigroups and formal languages. It is known that decidability is not preserved by some of the most common pseudovariety operators, such as join, semidirect product, Mal’cev product, between others [1, 58, 25]. An idea which has been recently explored by several authors is to impose stronger properties on the pseudovarieties upon which the operators are to be applied that will guarantee that the resulting pseudovarieties will be decidable. In this context Almeida introduced a stronger form of decidability, called hyperdecidability [5], which was later refined in collaboration with Steinberg [16, 17], leading to the notion of tameness. Recently it was proposed by Almeida [7] an extension of the notion of tameness, called complete tameness. The notion of tameness (and its generalizations) proved to be one of the most promising for obtaining results decidability of pseudovarieties. Motivated by this observation, we dedicate the final part of this work to these concepts: we show that LSl is completely tame and we prove the tameness of pseudovariety joins involving LSl, where LSl denotes the pseudovariety of local semilattices. Previously, we determine a basis of ω-identities for the ω-variety generated by LSl. We also study another algorithmic property, related with tameness, of pseudovariety LSl: the computation of its pointlike and idempotent pointlike sets.