Branco, Mário João de Jesus,1967-Branco, Eduardo José Caetano2015-02-062015-02-0620142014http://hdl.handle.net/10451/15946Tese de mestrado em Matemática, apresentada à Universidade de Lisboa, através da Faculdade de Ciências, 2014O 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.porÁlgebra-floresta sintáticaÁrvore de aridadeÁrvore sem aridadeAutómatoFlorestaMonoide sintáticoE-álgebra sintáticaPalavraReconhecimento de uma linguagemTeses de mestrado - 2014master thesis201384590