Álgebras de estabilização

Tese de mestrado, Matemática, Universidade de Lisboa, Faculdade de Ciências, 2018Este trabalho explora uma generalização da teoria algébrica das Linguagens Formais. Tendo os trabalhos de Thomas Colcombet e de Laure Daviaud, Denis Kuperberg e Jean-Éric Pin sobre funções de custo como ponto de partida, apresentamos os conceitos de ideal de ordem, álgebra de estabilização e autómato de estabilização. Obtemos generalizações de resultados conhecidos no âmbito das Linguagens Formais, como por exemplo do Teorema de Eilenberg e do Teorema de Schützenberger sobre identidades associadas a variedades, e também obtemos uma resposta para o Problema da Igualdade. Provamos também que o conceito de ideal de ordem reconhecível é uma generalização do conceito de função custo reconhecível pelo que a teoria desenvolvida se aplica também no estudo das funções de custo.This thesis explores a generalisation of the algebraic theory of Formal Languages. Having the work of Thomas Colcombet and of Laure Daviaud, Denis Kuperberg and Jean-Éric Pin about cost functions as a starting point, we present the concepts of ordered ideal, stabilisation algebra and stabilisation automata. We generalize various known results in Formal Languages, for example, the Eilenberg Theorem and the Schützenberger Theorem about identities associated to varieties, besides we answer to the Equality Problem. We also prove that the concept of recognisable ordered ideal is a generalisation of the concept of recognizable cost function, whence the theory developed in this thesis also applies to the study of cost functions