Este
projecto é dedicado à Teoria dos Semigrupos e à Teoria das Linguagens,
dois tópicos intrinsecamente ligados entre si e ambos, por sua vez,
relacionados com a Teoria dos Autómatos Finitos. Por um lado, temos
como objectivo estudar certas classes de semigrupos finitos, as
pseudovariedades, e as classes de linguagens reconhecíveis que lhes
estão associadas. Por outro lado, planeamos investigar certos
semigrupos específicos quer do ponto de vista estrutural quer da sua
representação por meio de apresentações. Estes são dois problemas
interligados e, em particular, um melhor conhecimento do segundo
contribuirá de modo determinante para o estudo do primeiro. Os
semigrupos de pavimentações e os semigrupos de transformações sobre uma
cadeia finita respeitando propriedades sobre a ordem são exemplos
específicos a considerar. Determinadas construções de semigrupos, como
as expansões ou as coberturas, que têm por base a utilização de
elementos mais simples, serão estudadas. Em particular, pretendemos
descrever as classes de linguagens reconhecíveis associadas a tais
tipos de semigrupos. As apresentações podem ser encaradas como sistemas
de reescrita, sendo este facto de grande importância na Computação
Teórica. Será estudado o modo como a propriedade geométrica FDT dos
sistemas de reescrita é preservada por certas construções de
semigrupos. Num contexto mais geral, iremos considerar o monóide dos
endomorfismos de uma álgebra de independência. Estas incluem, por
exemplo, os conjuntos e os espaços vectoriais. Organizámos este
projecto em três tarefas:
- Cálculo de congruências, apresentações e sistemas de reescrita;
- Semigrupos de transformações;
- Construções de semigrupos e linguagens associadas.
- Cálculo de congruências, apresentações e sistemas de reescrita;
- Semigrupos de transformações;
- Construções de semigrupos e linguagens associadas.