Por favor, use este identificador para citar o enlazar este ítem:
http://repositorio.ufc.br/handle/riufc/17249| Tipo: | Dissertação |
| Título : | Sequências convergentes de estruturas discretas e testabilidade |
| Título en inglés: | Convergent Sequences of Discrete Structures and Testability |
| Autor : | Bastos, Antonio Josefran de Oliveira |
| Tutor: | Sampaio, Rudini Menezes |
| Palabras clave : | Ciência da computação;Teoria dos grafos;Linguagens formais |
| Fecha de publicación : | 2012 |
| Citación : | BASTOS, Antonio Josefran de Oliveira. Sequências Convergentes de Estruturas Discretas e Testabilidade. 2012. 61 f. Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2012. |
| Resumen en portugués brasileño: | Neste trabalho, estudamos a teoria recente de convergência de sequências de grafos e suas extensões para permutações e ordens parciais de dimensão fixa. Conjecturamos um lema de regularidade fraca de grafos em intervalos que, se for verdadeira, nos possibilita estender essa teoria para grafos ordenados, que são grafos tais que existe uma ordem total entre os vértices. Mostramos algumas relações interessantes de permutações e ordens parciais com grafos ordenados. Com isso, conseguimos uma prova alternativa para a existência de objetos limites de qualquer sequência convergente de permutações. Provamos também que toda propriedade hereditária de permutações ou grafos ordenados é testável. |
| Abstract: | In this work, we studied the recent theory of convergent graph sequences and its extensions to permutation and partially ordered sets with fix dimension. We’ve conjectured a lemma of weak regularity on intervals that, if this conjecture is true, we can extend this theory to ordered graphs, which are graphs such that there is a total order on its vertices. We show some interesting relations on permutation and partially ordered sets with ordered graphs. Then, we obtain another proof to the existence of limit objects for all convergent permutation sequences. We also proved that all hereditary property of either permutation or ordered graph is testable. |
| URI : | http://www.repositorio.ufc.br/handle/riufc/17249 |
| Aparece en las colecciones: | DCOMP - Dissertações defendidas na UFC |
Ficheros en este ítem:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| 2012_dis_ajobastos.pdf | 816,97 kB | Adobe PDF | Visualizar/Abrir |
Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.