Uma pseudovariedade diz-se decidível se existe um algoritmo que decida se um dado semigrupo pertence à pseudovariedade. 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 [K. Krohn e J. Rhodes, 1965] que permanece em aberto há 40 anos.
Um subconjunto de um semigrupo diz-se pontual com respeito a uma pseudovariedade se para cada morfismo relacional naquela pseudovariedade, todo o conjunto se relacionar com um único ponto. O cálculo efectivo dos conjuntos pontuais permite, em particular, provar a decidibilidade de pseudovariedades, uma vez que podemos verificar que um semigrupo pertence a uma dada pseudovariedade se e só se os únicos conjuntos pontuais para essa pseudovariedade são os singulares.
Pretende-se, neste seminário, apresentar um algoritmo que permite obter os subconjuntos pontuais de um semigrupo finito com respeito à pseudovariedade LSl, dos semigrupos que são localmente semireticulados. Note-se que a pseudovariedade LSl é associada pela correspondência de Eilenberg?s 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. |