Programa

Semigrupos, Autómatos e Linguagens (D)

Doutoramento Bolonha em Matemática

Programa

Palavra e linguagem. Linguagem racional. Autómato finito e linguagem reconhecível. Algoritmos para a construção de autómatos que reconheçam uma linguagem descrita na forma de expressão racional. Autómato minimal de uma linguagem. Equivalência entre as linguagens reconhecíveis e as racionais - Teorema de Kleene. Reconhecimento algébrico de linguagens. Semigrupo sintáctico. Semigrupos, incluindo semigrupos ciclícos, relações de Green, semigrupos aperiódicos, semigrupos finitos simples e 0-simples. Classificação de linguagens racionais e de semigrupos finitos: Teorema de Eilenberg, Teorema de Birkhoff e Teorema de Reiterman. Nesta disciplina (D) o aluno deverá estudar por si um ou mais tópicos indicados pelo docente e fazer uma exposição oral sobre os mesmos.