Utilize este identificador para referenciar este registo: http://hdl.handle.net/10451/15946
Título: Linguagens reconhecíveis nas variantes de palavras, árvores e florestas: caracterizações e um estudo comparativo
Autor: Branco, Eduardo José Caetano
Orientador: Branco, Mário João de Jesus,1967-
Palavras-chave: Álgebra-floresta sintática
Árvore de aridade
Árvore sem aridade
Autómato
Floresta
Monoide sintático
E-álgebra sintática
Palavra
Reconhecimento de uma linguagem
Teses de mestrado - 2014
Data de Defesa: 2014
Resumo: O principal objetivo deste trabalho foi uniformizar a teoria do reconhecimento linguagens de árvores de aridade, de árvores sem aridade e de orestas, com ênfase especial para as duas últimas, com a teoria do reconhecimento de linguagens de palavras. De facto, apesar de tanto as linguagens de árvores (de e sem aridade) e as linguagens de orestas serem generalizações de linguagens de palavras, o seu desenvolvimento não conhecia o mesmo tratamento sistematizado de que está munida a clássica teoria de linguagens de palavras. Nas páginas que se seguem, procurou-se formalizar e organizar alguns aspetos relativos ao reconhecimento de linguagens de árvores de aridade, de árvores sem aridade e de orestas numa teoria comparável com aquela que faz das linguagens de palavras ferramenta incontornável em inúmeras aplicações à Ciência da Computação. De notar que é também como resposta a novos problemas postos pela Ciência da Computação que outros objetos matemáticos vêm a ser estudados com maior profundidade. Esse é precisamente o caso das árvores e orestas, cujas linguagens dão resposta, por exemplo, a problemas relacionados com a representação/armazenamento e troca de dados informáticos. O texto encontra-se organizado da seguinte forma. No primeiro capítulo, são sumariamente apresentados alguns conceitos e resultados relacionados com teoria de semigrupos; no segundo é recordada a teoria do reconhecimento de linguagens de palavras; nos dois últimos, é então descrita uma teoria de reconhecimento de linguagens de árvores de aridade e de linguagens de orestas, respetivamente, as quais, sendo inspiradas na teoria clássica, constituem uma possível uniformização.
The main aim of this study was to present a uniform theory of recognizable language of ranked trees, unranked trees, and forests as that of words. Indeed, and despite the fact that both languages of (ranked and unranked) trees and languages of forests are generalizations of languages of words, its development had not yet achieved the systematic treatment that has long been known to languages of words. In what follows, we develop a formalization and organization of some aspects concerning language recognition for languages of ranked trees, languages of unranked trees, and languages of forests in a manner that resembles the classical | and powerful | theory of languages of words. And if the classical theory has been the major tool in various problems in computing science, new challenges have recently demanded other approaches. For instance, problems related to data representation and exchange have been solved using trees and forest, prompting renewed interest in these subjects. The text is organized as follows. In the first chapter, we briey present some concepts and results concerning semigroups; in the second, we recall the aspects of the classical theory of languages of words which will allow us to, in the third and fourth chapters, describe a theory of language recognition for ranked trees and for forests, respectively, that compares with the classical theory.
Descrição: Tese de mestrado em Matemática, apresentada à Universidade de Lisboa, através da Faculdade de Ciências, 2014
URI: http://hdl.handle.net/10451/15946
Designação: Mestrado em Matemática
Aparece nas colecções:FC - Dissertações de Mestrado

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
ulfc112553_tm_Eduardo_Branco.pdf543,93 kBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.