Os sistemas computacionais estão tomando proporções cada vez maiores envolvendo situações bastante complexas, onde muitas vezes erros são inaceitáveis, como em sistemas bancários, sistemas de controle de tráfego aéreo, etc... Para obter software confiável e com desempenho aceitável, pode-se aliar técnicas de desenvolvimento formal de software a técnicas de simulação de sistemas. O ambiente PLATUS reúne essas duas áreas: modelos de simulação são descritos usando gramáticas de grafos uma linguagem de especificação formal. Gramáticas de grafos são uma generalização de gramáticas de Chomsky, substituindo strings por grafos. Neste trabalho, serão tratadas gramáticas de grafos baseados em objetos, um modelo onde vértices e arcos são tipados, e as especificações são modulares (a especificação de um sistema consiste em várias gramáticas de grafos combinadas). Assim, o modelo de um sistema pode ser descrito de forma precisa, e a linguagem de especificação é bastante abstrata e expressiva. Num ambiente de simulação a questão da recuperação de dados merece uma atenção especial, uma vez que a eficiência do simulador está diretamente ligada a agilidade na obtenção das informações. Neste trabalho, o objetivo principal é definir uma representação para gramáticas de grafos que facilite o armazenamento, a recuperação e análise das estruturas identificadas no ambiente PLATUS, ou seja, gramáticas de grafos baseadas em objetos. São definidas também funções que implementam os procedimentos necessários, para a recuperação de dados durante a simulação. A eficiência dessas funções é demonstrada através do cálculo de sua ordem de complexidade. As estruturas são validadas através da implementação de um protótipo de banco de dados.

Um span em uma categoria é um par ordenado de morfismos dessa categoria, ambos com origem num mesmo objeto. O destino do primeiro morfismo é a origem do span e o destino do segundo morfismo é o destino do span. Spans, embora sejam uma estrutura bastante simples numa categoria e tenham uma definição também bastante simples, são versáteis, pois, com especializações sutis apresentadas aqui, são capazes de representar outras estruturas, tais como as tratadas nesses trabalho: relações binárias, multirrelações binárias, grafos e, em conjunto com um morfismo adicional, sistemas de transições etiquetadas (LTS). Permitem ainda, como proposto nesse trabalho, definir de forma também simples, redes de Petri como sendo um endospan em uma categoria. Mostra-se que a composição de spans aplicada a essas estruturas é capaz de expresar a composição de multirrelações — mas não de relações —, uma composição de grafos cujo grafo resultante indica caminhos em que cada parte é uma aresta de um dos grafos operados, uma composição de LTS cujo LTS resultante apresenta transações que podem ser compostas por transições de diferentes LTS e uma composição de redes de Petri cujo resultado também apresenta transações compostas por transições que podem ser realizadas em redes de Petri distintas. Mostra-se algumas propriedades dessas composições, bem como suas provas. Como verificar propriedades de relações e de grafos através de spans também é proposto.

Das Hauptziel dieser Arbeit ist es, einen Ansatz fur die parallele Komposition von Graph- Grammatiken und eine Unfolding-Semantik genannte Semantik fiir Graph-Grammatiken bereitzustcllen, in der die Aspekte Nebenlaufigkeit und Kompositionalitat bzgl. der parallelen Komposition eine zentrale Rolle einnehmen. Die parallele Komposition von Graph-Grammatiken erlaubt die Komposition von Grammatiken bzgl. eines gemeinsamen (moglicherweise leeren) Anteils und basiert auf der parallelen und amalgamierten Komposition von Regeln der komponierten Grammtiken. Dariiber hinaus ist das Kompositionsergebnis syntaktisch und semantisch in geeigneter Weise mit den komponierten Grammatiken verkniipft. Die Unfolding-Semantik einer Graph-Grammatik ist eine echt nebenldufige, verzweigende Semantik, in der sowohl Zustande (Graphen) als auch Zustandsanderungen (Ableitungen) reprasentiert sind. Das Unfolding kann inkrementell konstruiert werden und es wird gezeigt, daß dies das gleiche Result liefert wie die Verklebung der deterministischen Berechnungen einer Grammatik Dartiberhinaus ist das Unfolding einer Graph-Grammatik selbst eine Graph- Grammatik, die einer speziellen Klasse von Graph-Grammatiken angehOrt: den Occurrence- Grammatiken. Hier wird diese Klasse axiomatisch definiert und die Elemente dieser Klasse kOnnen als Grammatiken gesehen werden, die (deterministische und nicht-deterministische) Berechnungen einer anderen Grammatik reprdsentieren. Die Semantik einer Grammatik, die aus der parallelen Komposition anderer Grammatiken entstanden ist, ist isomorph zur Komposition der Semantiken der komponierten Grammatiken. Dieses Kompatibilitatsresultat verbindet die parallele Komposition und die Unfolding Semantik in enger Weise. Da der Zweck der parallelen Komposition die Komposition nebenldufiger Systeme ist, stellt die Kompatibiliat von Komposition und Nebenlaufigkeitssemantik ein attraktives Ergebnis dar. / The main aims of this thesis are to provide an approach to the parallel composition of graph grammars and a semantics for graph grammars, called the unfolding semantics, in which the aspects of concurrency and compositionality with respect to the parallel composition play a central role. The parallel composition of graph grammar allows the composition of grammars with respect to a shared part (that may be empty), and is based on parallel and amalgamated composition of the rules of the component grammars. Moreover, the result of the composition is suitably syntactically and semantically related to the component grammars. The unfolding semantics of a graph grammar is a true concurrent, branching structure semantics in which states (graphs) as well as changes of states (derivations) are represented. The unfolding can be constructed incrementally, and we show that this yields the same result as a construction based on gluing of the deterministic computations of a grammar. Moreover, the unfolding of a graph grammar is itself a graph grammar that belong to a special class of graph grammars: the occurrence graph grammars. Here this class is defined axiomatically, and the members of this class can be seen as grammars that represent (deterministic and non-deterministic) computations of another grammars. The semantics of a grammar obtained as the parallel composition of other grammars is isomorphic to the composition of the semantics of the component grammars. As the purpose of the parallel composition is to be a composition for concurrent and reactive systems, the fact that this composition is compatible with a true concurrency semantics is an attractive result.

Este trabalho vem a dar mais uma contribuição para o já consagrado uso de teoria das categorias para descrever e estabelecer relações entre formalismos diferentes. Esta dissertação tem como objeti principal estabelecer uma relação entre os formalismos de reded de Petri e gramáticas de grafos a partir de suas já difundidas represetações categóricas, utilizando, para isto, a linguagem da teoria das categorias. / This works comes to be one more contribution to the well diffused use of the category theory to describe and stablish relationships between different formalisms. The main goal of this dissertation is to stablish a relationship between the Petri nets and graph grammar fomalisms, using category theory and their categorical representations found in the literature.

Nesta tese apresentamos solu c~oes de dois problemas de colora c~ao de grafos. Para as solu c~oes de ambos problemas, utilizamos ferramentas probabil sticas. Em um desses problemas de colora c~ao, consideramos o espa co de probabilidade Gk n;p dos grafos aleat orios coloridos. Provamos que, para cada k 3, o limiar para a propriedade de que um grafo aleat orio colorido cont em uma arvore geradora propriamente colorida e log n=n, que e precisamente o limiar para a conexidade. Para resolver esse problema, utilizamos uma cota para a cardinalidade de um emparelhamento m aximo em Gn;(1+ ) log n=n, provada por Frieze em 1986. Embora tal cota seja su ciente para resolver esse problema, investigamos o problema da cardinalidade de um emparelhamento m aximo no grafo aleat orio Gn;(1+ ) log n=n e obtivemos um resultado mais preciso. O outro problema de colora c~ao e um problema determin stico, por em, para a solu c~ao deste, utilizamos um resultado de enumera c~ao de grafos cuja demonstra c~ao apresenta argumentos probabil sticos. Dados r t 3 e ` 1, procuramos por grafos com n v ertices que admitem o maior n umero de r-colora c~oes tais que no m aximo t1 cores aparecem pelo menos ` vezes em arestas incidentes a cada v ertice, isto e, r-colora c~oes livres de St;`-arco- ris (estrelas com t` arestas coloridas com t cores distintas tal que cada cor e atribu da a exatamente ` arestas). Para n grande, mostramos que, o grafo completo Kn e o unico grafo extremal. / In this thesis, we obtain solutions for two graph coloring problems, both of which rely on probabilistic tools. In one of these coloring problems, we consider the probability space Gk n;p of edge-colored random graphs. We prove that, for all xed k 3, the threshold for the property that an edge-colored random graph contains a properly colored spanning tree is log n=n, precisely the threshold for connectivity. To solve this problem, we used a bound for the size of a maximum matching in Gn;(1+ ) log n=n, proved by Frieze in 1986. Although such bound is su cient to solve this problem, we investigated the problem of the size of a maximum matching in the random graph Gn;(1+ ) log n=n and we obtained a more precise result. Even though the other coloring problem is deterministic, we used a graph enumeration whose proof is probabilistic. Given r t 3 and ` 1, we look for n-vertex graphs that admit the maximum number of r-edge-colorings such that at most t 1 colors appear at least ` times in edges incident with each vertex, that is, r-edge-colorings avoiding rainbow-St;` (stars with t` edges colored with t distinct colors such that each color is assign to exactly ` edges). For large n, we show that, the complete graph Kn is always the unique extremal graph.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, Programa de Pós-Graducação em Informática, 2015. / Submitted by Fernanda Percia França (fernandafranca@bce.unb.br) on 2016-06-07T16:28:08Z No. of bitstreams: 1 2015_RodrigoPinheirodeAlmeida.pdf: 2786870 bytes, checksum: 683fe7a67964204f75f57755f9546e73 (MD5) / Approved for entry into archive by Raquel Viana(raquelviana@bce.unb.br) on 2016-12-21T17:01:19Z (GMT) No. of bitstreams: 1 2015_RodrigoPinheirodeAlmeida.pdf: 2786870 bytes, checksum: 683fe7a67964204f75f57755f9546e73 (MD5) / Made available in DSpace on 2016-12-21T17:01:19Z (GMT). No. of bitstreams: 1 2015_RodrigoPinheirodeAlmeida.pdf: 2786870 bytes, checksum: 683fe7a67964204f75f57755f9546e73 (MD5) / Muitos experimentos científicos na bioinformática são executados como workflows computacionais. Algumas vezes para a validação e reconhecimento de um experimento é necessário reexecutá-lo sob as mesmas circustâncias nas quais foi originado. Proveniência de dados diz respeito à origem ou procedência dos dados. Para facilitar o entendimento e análise dos resultados, é interessante ter os dados de proveniência, que detalham e documentam a história e os caminhos dos dados de entrada, do início do experimento até o final. Portanto, neste contexto, a proveniência de dados pode ser aplicada para realizar a rastreabilidade de um experimento. Considerando que uma execução de um workflow pode ser representado por um grafo, como definido no modelo PROV-DM, este documento apresenta uma arquitetura capaz de realizar a proveniência de dados de expe- rimentos científicos na bioinformática de forma automática e armazenamento em bancos de grafo. / Many scientific experiments in bioinformatics are executed as computational work- flows. Sometimes for the validation and recognition of an experiment is need rerun under same circumstances in which it was originated. Date provenance concers the origin data. To facilate the understanding and analysis of the results is interesting to have the source data, detailing and documeting the history and the paths of the input data, the beginning of the experiment until the end. Therefore, in this context, the data provenance can be applied to realize an experiment traceability. Whereas an execution of a workflow can be represented by a graph, as defined in PROV-DM model, this document presents an architecture able to perform the data provenance of iscientif experiments in bioinformatics automatically and storage graph database.

A Teoria Espectral de Grafos tem como objetivo descobrir propriedades de um grafo G através da análise do espectro de uma matriz associada ao grafo. Nesta dissertação estudamos a matriz de adjacência A(G), a matriz laplaciana L(G) e a matriz laplaciana sem sinal Q(G). Para cada uma dessas matrizes estudamos o comportamento dos autovalores no que diz respeito `a integralidade. Mais especificamente, estudamos os grafos integrais, os grafos Q-integrais e os grafos L-integrais, que são os grafos que têm espectro inteiro em relação `as matrizes A(G), Q(G) e L(G), respectivamente. Estudamos a variação espectral inteira via adição de aresta para a matriz laplaciana. Vimos que se os autovalores da matriz laplaciana variam de maneira inteira, então um dos autovalores aumenta em duas unidades ou dois dos autovalores aumentam em uma unidade cada um. Esses dois tipos de variações são conhecidas como variação espectral inteira em um lugar e dois lugares [26, 33], respectivamente. Essas duas variações foram cruciais para estabelecermos uma estratégia para construção de grafos L-integrais por adição de arestas. Além disso, estudamos os grafos construtivelmente laplaciano integrais [28], que são um subconjunto dos grafos L-integrais. Caracterizamos este subconjunto através dos subgrafos induzidos e mostramos uma técnica alternativa para calcular o seu espectro. Estudamos também algumas famílias com infinitos grafos integrais e grafos Q-integrais construídos através do join de grafos regulares [12, 15, 24]. / The spectral graph theory aims to discover properties of a graph G by analyzing the spectrum of a matrix associated to the graph. In this thesis, we study the adjacency matrix A(G), Laplacian matrix L(G) and the signless Laplacian matrix Q(G). For each of these matrices we study the behavior of eigenvalues with respect to integrality. More specifically, we study integral graphs, Q-integral graphs and L-integral graphs, which are graphs that have integral spectrum with regard to the matrices A(G), Q(G) and L(G), respectively. We study the spectral integral variation for the Laplacian matrix under the addition of an edge. We have seen that if the eigenvalues of the Laplacian matrix change by integer quantities, then one of the eigenvalues increases by two units or two of the eigenvalues increase by one unit each. These two types of variation are known as spectral integral variation in one place and two places [26, 33], respectively. These two variations were crucial to establish a strategy for building L-integral graphs by adding edges. Moreover, we studied the class of constructably Laplacian integral graphs, that are a subset of L-integral graphs. We characterize this subset through vertex-induced subgraphs and show an alternative technique for calculating their spectrum. We also study some families with infinite integral graphs and Q-integral graphs built through the join of regular graphs [12, 15, 24].

Neste trabalho abordaremos a an alise espectral de grafos por dois estudos: técnicas de probabilidade quântica e por polinômios ortogonais com valores em matrizes. No Capítulo 1, consideraremos a matriz de adjacência do grafo tal como um operador linear e sua decomposição quântica permitir a uma an alise espectral que produzir a um teorema do limite central para tal grafo. No Capítulo 2, consideraremos uma medida com valores em matrizes induzida por polinômios ortogonais com valores em matrizes. Sob certas condições, e possível exibir explicitamente uma expressão de tal medida. Algumas aplicações em teoria dos grafos são dadas quando nos restringimos as matrizes estoc asticas e com valores em 0-1. Do nosso conhecimento, os cálculos e exemplos obtidos nas seçõoes 0.3.2, 0.3.3, 2.4 e 2.5 são novos. / In this work we focus on the spectral analysis of graphs via two studies: quantum probabilistic techniques and by orthogonal matrix-valued polynomials. In Chapter 1 we consider the adjacency matrix of a graph as a linear operator, and its quantum decomposition will allow a spectral analysis that will produce a central limit theorem for such graph. In Chapter 2, we consider a matrix-valued measure induced by orthogonal matrix-valued polynomials. Under certain conditions, it is possible to display an explicit expression for such measure. Some applications to combinatorics and graph theory are given when we restrict to the stochastic and 0-1 matrices. Up to our knowledge, the calculations and examples obtained in sections 0.3.2, 0.3.3, 2.4 and 2.5 are new.

Neste trabalho tratamos de um problema clássico bem conhecido em Teoria dos Grafos: o problema da existência de um ciclo hamiltoniano. Um grafo é dito hamiltoniano se possui um ciclo hamiltoniano, ou seja, apresenta um ciclo que percorre todos os vértices do grafo. Estudamos problemas clássicos associados a este problema em termos do número de arestas, do grau mínimo e da sequência de graus dos vértices de um grafo. Além disso, estudamos resultados espectrais para o problema de hamiltonicidade referentes às matrizes de adjacências e laplaciana. A principal contribuição deste trabalho é a apresentação detalhada de condições suficientes e condições necessárias que garantem um ciclo hamiltoniano em um grafo já existentes na bibliografia. / In this work we study a well-known problem in Graph Theory: the existence of a Hamilton cycle, namely a cycle that goes through every vertex in the graph. We consider classical su cient conditions related with this problem in terms of the number of edges, the minimum degree and the vertex degree sequence of a graph. Furthermore, we study spectral results for the hamiltonian problem in terms of the adjacency and laplacian matrix. The main contribution of this work is our detailed presentation of necessary and su cient conditions for the existence of a Hamilton cycle in a graph.

Cografos representam uma classe de grafos que pode ser de nida e caracterizada de diversas maneiras. A estrutura de relacionamento entre seus vértices, permite que um cografo possa ser construído de forma recursiva a partir de um único vértice. Neste trabalho estudamos algumas caracterizações clássicas de cografos, dentre as quais abordamos: livre de P4, formas recursivas utilizando união, complemento e junção, diâmetro de todo subgrafo induzido 2, vértices irmãos, propriedade CK(clique Kernel), e formas recusivas utilizando duplicação e coduplica ção de vértices. A principal contribuição foi relacionar algumas das diferentes formas de caracterizações de um cografo com a de nição de grafo complementar redutível. Apresentamos algumas formas de representar cografos, que podem ser encontradas em diversos trabalhos, como forma normalizada, coárvore e matriz de adjacência. Estudamos um algoritmo que auxilia na localização de autovalores em cografos, como contribuição apresentamos os detalhes teóricos sobre seu funcionamento através da Lei na Inércia de Sylvester, e da obtenção de matrizes congruentes à matriz A+xI, onde A é a matriz de adjacência de um cografo, x é um número real e I é a matriz identidade de mesma ordem de A. Com este algoritmo, estudamos alguns resultados clássicos sobre o espectro de um cografo, que são: a multiplicidade dos autovalores 1 e 0, e que um cografo não possui autovalores no intervalo (1; 0). Além disso, apresentaremos algumas aplicações para obter famílias de cografos com a mesma energia de grafos completos Kn. / Cographs are a class of graphs that can be de ned and characterized in several ways. The structure given in terms of vertices enable a cograph to be built by recursive form from a single vertice. In this work, we study some classical characterizations of cographs, among which: P4 - free, recursive form with union, complement and join, diameter of all induced subgraph connected 2, siblings vertices, property CK(cliqueKernel), and recursive form by duplication and coduplication of vertices. As main contribution, we establish a relationship between some characterizations of cographs, which is a complement reducible graph. We also show some ways to make a mathematical representation that can be found in various works, as normalized form, cotree and adjacency matrix. We study an algorithm that can help us to nd eigenvalues in cographs, as an additional contribution we provide the theoretical details about its operation through the Sylvester Law of Inertia and how to get congruent matrices from A+xI, where A is the adjacency matrix of a cograph, x is a real number and I is a identity matrix with the same order of A. Using the algorithm, we study some classical results about spectral set of a cograph, as the multiplicity of eigenvalues 1 and 0, and the statement of no cographs have eigenvalues in (1; 0). In addition, we show some applications to nd cograph families with the same energy of complete graphs Kn.