A carregar...
Publicação
Autómatos reversíveis: um estudo algébrico e topológico
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 571.56 KB | Adobe PDF |
Orientador(es)
Resumo(s)
Nesta dissertação será feito o estudo de autómatos reversíveis e das linguagens reconhecidas por estes. Começamos com um capítulo preliminar, que nos dará noções iniciais de Semigrupos, Autómatos e Linguagens, e alguns resultados importantes. Entramos depois na área das Classes de Monoides e Classes de Linguagens, onde é dada a definição de variedades de monoides. A partir dessa definição, e para facilitar o estudo posterior dos autómatos reversíveis, damos as definições de M-variedade, variedade de monoides ordenados, e de MO-variedades, estas últimas essenciais para uma das caracterizações das linguagens reconhecidas por autómatos reversíveis. Iniciamos então um terceiro capítulo, focado no estudo dos subconjuntos racionais do grupo livre, que serão necessários para uma das nossas caracterizações, e que fazem um paralelo com a definição de linguagens racionais, enunciada no primeiro capítulo. No quarto capítulo são então dados os resultados sobre M-variedades e MO-variedades que nos ajudam a caracterizar linguagens reconhecidas por autómatos reversíveis. Neste capítulo focamo-nos principalmente na classe de monoides gerada pelos monoides inversos, quer no caso ordenado, quer no caso não ordenado. No quinto e último capítulo são enunciadas as diferentes caracterizações possíveis para as linguagens reconhecidas por autómatos reversíveis, terminando com um algoritmo para facilitar a descoberta destas linguagens, bem como um resultado final que engloba todas as caracterizações dadas.
In this dissertation we will study reversible automata, and the languages recognized by them. We begin with a preliminary chapter, which will give us initial notions of Semigroups, Automata and Languages, as well as some important results. We then enter the area of Monoid Classes and Language Classes, where the definition of variety of monoids is given. From this definition, and to facilitate the later study of reversible automata, we give the definitions of M-variety, variety of ordered monoids, and MO-varieties, the latter essential for one of the characterizations of the languages recognized by reversible automata. We then start a third chapter, focused on the study of the rational subsets of the free group, which will be necessary for one of our characterizations, and which make a parallel with the definition of rational languages, stated in the first chapter. In the fourth chapter, the results on M-varieties and MO-varieties are given, which help us to characterize languages recognized by reversible automata. In this chapter we focus mainly on the class of monoids generated by inverse monoids, both in the ordered and in the non-ordered cases. In the fifth and last chapter, the different possible characterizations for the languages recognized by reversible automata are listed, ending with an algorithm to facilitate the discovery of these languages, as well as a final result that encompasses all the given characterizations.
In this dissertation we will study reversible automata, and the languages recognized by them. We begin with a preliminary chapter, which will give us initial notions of Semigroups, Automata and Languages, as well as some important results. We then enter the area of Monoid Classes and Language Classes, where the definition of variety of monoids is given. From this definition, and to facilitate the later study of reversible automata, we give the definitions of M-variety, variety of ordered monoids, and MO-varieties, the latter essential for one of the characterizations of the languages recognized by reversible automata. We then start a third chapter, focused on the study of the rational subsets of the free group, which will be necessary for one of our characterizations, and which make a parallel with the definition of rational languages, stated in the first chapter. In the fourth chapter, the results on M-varieties and MO-varieties are given, which help us to characterize languages recognized by reversible automata. In this chapter we focus mainly on the class of monoids generated by inverse monoids, both in the ordered and in the non-ordered cases. In the fifth and last chapter, the different possible characterizations for the languages recognized by reversible automata are listed, ending with an algorithm to facilitate the discovery of these languages, as well as a final result that encompasses all the given characterizations.
Descrição
Tese de mestrado em Matemática, Universidade de Lisboa, Faculdade de Ciências, 2020
Palavras-chave
Monóide Linguagem reconhecível Autómato reversível Variedade de monóides Grupo livre Teses de mestrado - 2020