Nas aplicações da teoria de semigrupos finitos na Informática, o problema mais comum consiste em
Nas aplicações da teoria de semigrupos finitos na Informática, o problema mais comum consiste em decidir se um dado semigrupo finito satisfaz uma propriedade fixada. Tais propriedades traduzem-se em muitas situações em verificar certas igualdades no semigrupo sempre
que certos sistemas de equações, nos quais às variáveis são impostas restrições determinadas pelo semigrupo, admitem soluções "módulo" uma pseudovariedade V fixada. O problema de decidir se um tal sistema tem solução por sua vez parece em geral intratável. No entanto, ele
torna-se acessível se for possível garantir que, caso existam soluções, então existem soluções "periódicas". Esta ideia está presente em muitas áreas da Matemática e e o essencial da propriedade de uma pseudovariedade a que se chama "mansidão" ("completa", se não
houver quaisquer restrições sobre os sistemas considerados) que foi introduzida por Almeida e Steinberg.
Na teoria elementar do monóide livre, Makanin usou uma ideia semelhante para decidir se um sistema de equações com restrições racionais sobre as variáveis tem solução. O objectivo da palestra e mostrar como os metodos de Makanin podem ser adaptados para estabelecer resultados de mansidão para pseudovariedades de semigrupos. O resultado principal, obtido recentemente em colaboração com Jose Carlos Costa e Marc Zeitoun, ilustra esta nova tecnica. Ele afirma que a pseudovariedade R, dos semigrupos finitos em que elementos com os mesmos prefixos são iguais, e completamente mansa.
Date and Venue
Start Date
Venue
Anfiteatro 0.04
Speaker
Jorge Almeida (CMUP)
Area
Semigroups, Automata and Languages