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.

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.

Atualmente, o uso de sistemas de informação está amplamente difundido, sendo que praticamente todas as áreas de negócio têm necessidade de tais sistemas. Estes sistemas são formados por funcionalidades que implementam regras do negócio e persistem os dados em bases de dados. Os usuários podem utilizar estes sistemas através das interfaces de usuário, que são as unidades onde estão implementadas as funcionalidades, que estão estruturadas por meio de menus. Através destes menus, o usuário pode navegar e selecionar aquela interface de usuário que contenha a funcionalidade que ele está buscando. A motivação para este trabalho veio da grande dificuldade que é manter sistemas, em uma linha de produção de software, íntegros do ponto de vista das interfaces do usuário. A cada sistema novo ou manutenção em sistema já existente, garantir que as interfaces do usuário tenham os mesmos padrões de aparência e comportamento, exige um grande esforço de verificação e validação, o que pode ser minimizado por um processo onde a estrutura das interfaces do usuário esteja em um modelo baseado em padrões. Sempre que uma aparência ou comportamento for alterado para um padrão, ele pode ser replicado em todos os sistemas modelados, permitindo, assim, não somente uma melhoria na produtividade como também um ganho em qualidade. O objetivo principal deste trabalho é definir e validar um metamodelo que permita modelar a estrutura destas interfaces de usuário de um sistema de informação. Para construir este metamodelo, foi escolhida uma estrutura de grafos. Esta escolha foi devido à naturalidade com que uma interface de usuário pode ser representada como um vértice e os relacionamentos por arestas. Inicialmente foram identificados e normalizados os padrões das interfaces de usuário de uma grande amostra de sistemas de informação. O metamodelo foi construído com base nestes padrões. Utilizando este metamodelo, foi possível construir modelos completos para um sistema hipotético e para três sistemas reais, comprovando que ele pode ser usado na modelagem das interfaces de usuário de outros sistemas similares.

Orientador: Celia Picinin de Mello / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-21T04:18:30Z (GMT). No. of bitstreams: 1 PerezLozada_LuisArturo_M.pdf: 2819086 bytes, checksum: a6afd3f6ffb1a048ced4a84733ff7e66 (MD5) Previous issue date: 1996 / Resumo: Uma dique de um grafo G é um conjunto de vértices que induz um subgrafo completo maximal de G. O grafo dique K(G) de um grafo G é o grafo interseção das diques de G. Indutivamente define-se o i-ésimo grafo dique iterado de G como Ki(G) = K(Ki-l(G)). Apresenta-se de maneira organizada uma compilação de pesquisas realizadas nos últimos anos a respeito de diversos tópicos na dasse dos grafos dique, entre eles: o estudo das propriedades dos grafos dique de conhecidas dasses de grafos; a convergência; divergência e diâmetro dos grafos clique-iterados / Abstract: A clique of a graph G is a set of vertices that induce a maximal complete subgraph of G. The dique graph K (G) of a graph G is the intersection graph of the diques of G. Inductively we denote the ith iterated dique graph of G by Ki(G) = X(Ki-l(G)). We wiil present in an organized way a compilation of investigations made in the last years with respect to the several topics on this class of graphs, such as: the study of proprieties of dique graphs of weil-known class of graphs; convergence; divergence and diameters of iterated dique graphs / Mestrado / Mestre em Ciência da Computação

Orientador: Claudina Izepe Rodrigues / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-07-26T16:57:25Z (GMT). No. of bitstreams: 1 Carvalho_MarceloDantasde_M.pdf: 1298387 bytes, checksum: 14167c08257e5465066717df5f9963e6 (MD5) Previous issue date: 2000 / Resumo: 0 objetivo principal deste trabalho é apresentar uma classificação para os dígrafos semicompletos hamiltonianos, extendendo os resultados obtidos para os torneios. Para isso utilizamos da teoria da homotopia regular de grafos de Davide C. Demaria, apresentando resultados sobre torneios simplemente desconexos, a caracterização de torneios por 3-ciclos e o conceito de ciclo conado e não-conado para dígrafos, introduzido por Kiihl e Tironi. Com a noção de ciclo minimal e característico para dígrafo uma classificação para os dígrafos semicompletos hamiltonianos surge então naturalmente. Esses resultados, quando encontrados para torneios, proporcionaram a obtenção de uma classe de torneios reconstrutíveis (torneios normais) e pesquisa nesse sentido deve ser efetuada para dígrafos. Apresentamos em apêndice a matriz de um dígrafo, os torneios de moon, normais e, brevemente, o problema da reconstrução de grafos / Abstract: The main target in this work is to present a classification for the hamiltonian semicomplete digraphs, extending the results previously obtained for the tournaments. In this way we apply the regular homotopy of finite directed graphs theory developed by Davide G. Demaria, presenting results on simply disconnected tournaments, on the caracterization of tournaments by 3-cicles and the concept of coned and non-coned cicle for digraphs, introduced by Kiihl and Tironi. With the notion of minimal and caracteristic cicle we naturally get a classification of the semicomplete hamiltonian digraphs. These results, when used for tournaments led to a new class of reconstructible ones (named normal) and future research on the extension of these results for digraphs in general seems to be interesting. We present in appendixes the array of a digraph, the tournaments of Moon, Normal and, briefly, the reconstruction problem for graphs / Mestrado / Mestre em Matemática

Orientador: João Meidanis / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-27T09:25:12Z (GMT). No. of bitstreams: 1 Braga_MariliaDiasVieira_M.pdf: 1562326 bytes, checksum: e2bde728b7016815f56abc118722d3d4 (MD5) Previous issue date: 2000 / Resumo: Este trabalho está relacionado à Biologia Computacional, uma área da Ciência da Computação cuja existência é motivada pela busca de métodos computacionais que resolvam ou ajudem a resolver problemas de origem biológica. Esta ciência tem sido largamente utilizada no âmbito da genética, contribuindo essencialmente no seqüenciamento de cadeias de DNA e no mapeamento de genomas [11]. O foco do nosso projeto foi uma família de problemas denominada Minimum Contig Problems (MCP) [4], que é um modelo teórico para a abordagem da Montagem de Fragmentos de DNA [11] e que possui uma grande semelhança com um problema de grafos denominado Cobertura de Vértices por Caminhos (CVC) [4]. O principal resultado da nossa pesquisa foi a apresentação de provas formais da NP-dificuldade dos problemas de MCP. A partir daí, complementamos o nosso trabalho propondo um algoritmo de aproximação para instâncias restritas de cada problema de MCP. / Abstract: Not informed. / Mestrado / Mestre em Ciência da Computação

Submitted by Marcele Costal de Castro (costalcastro@gmail.com) on 2017-09-19T18:35:05Z No. of bitstreams: 1 EUGENIO RANGEL MARINS M.pdf: 4071711 bytes, checksum: 2dcc07b50f8a006ccb9c8498d0561d65 (MD5) / Made available in DSpace on 2017-09-19T18:35:05Z (GMT). No. of bitstreams: 1 EUGENIO RANGEL MARINS M.pdf: 4071711 bytes, checksum: 2dcc07b50f8a006ccb9c8498d0561d65 (MD5) Previous issue date: 1997-05 / Grafos hierárquicos são amplamente utilizados em muitas áreas do conhecimento, tais como economia, eletrônica e ciência da computação. Uma boa visualização da informação estrutural permite ao leitor se focalizar no conteúdo informativo do desenho. A necessidade de se obter estes desenhos de forma rápida levou ao desenvolvimento de programas de computador para o traçado de tais grafos. Estes programas buscam a otimização de uma série de critérios que definem como deve ser um bom traçado. O principal critério para a obtenção de um bom traçado é a minimização do número de cruzamentos entre arestas, e este se constitui em um problema NP- completo. Neste trabalho são apresentados, analisados e comparados vários algoritmos heurísticos para a redução de cruzamentos de arestas no traçado automático de grafos hierárquicos. Analisa-se também algoritmos de reconhecimento de planaridade em grafos hierárquicos.

Made available in DSpace on 2014-06-12T18:28:59Z (GMT). No. of bitstreams: 2 arquivo648_1.pdf: 827994 bytes, checksum: 5bd18eefcbed6a0d647716cdc47627b9 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2011 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / Bixby e Cunningham relacionaram graficidade de matroides binárias 3-conexas e cocircuitos não separadores, generalizando um critério de planaridade de grafos 3-conexos de Tutte. Lemos estudou o conjunto de cocircuitos não-separadores que evita um elemento de uma matroide binária 3-conexa e conseguiu outra caracterização: M é gráfica se e só se cada elemento de M evita exatamente r (M)¡1 cocircuitos não separadores. Aqui estudamos o conjunto Y (M), dessas obstruções para graficidade, formado pelos elementos de M que evitam no mínimo r (M) cocircuitos não-separadores. Mostramos que, numa matroide binária 3-conexa existem 3 circuitos contidos em Y (M), cada qual não contido na união dos outros dois. Isso implica numa generalização do resultado de Lemos. No caso em que M não possui menor M¤(K000 3,3) ou M não é regular, conseguimos resultado muito melhor: jE(M)¡Y (M)j · 1. A demonstração desses resultados se baseia numa extensão de alguns resultados de Whittle a respeito demenores de matroide 3-conexas, que também são desenvolvido aqui: Seja M uma matroide binária e 3-conexa com um menor 3-conexo N. Suponha que r (M) ¸ r (N)Å3. Então existe um 3-coindependente I ¤ de M tal que co(M\e) é 3-conexa com menor isomorfo a N para todo e 2 I ¤. No mesmo capítulo desse teorema mostramos ainda uma versão para grafos que, porém, não se extende para matroides binárias

Orientador: João Meidanis / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-25T23:05:16Z (GMT). No. of bitstreams: 1 Cerqueira_FabioRibeiro_M.pdf: 3328400 bytes, checksum: b5fc969ee438ff4785221a8b86e87d7b (MD5) Previous issue date: 2000 / Mestrado / Mestre em Ciência da Computação

Orientadores: Celia Picinin de Mello, Anamaria Gomide / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-04T17:24:05Z (GMT). No. of bitstreams: 1 Almeida_SheilaMoraisde_M.pdf: 420796 bytes, checksum: 2ffdaaee7ece5527360d5a4d0a2827ff (MD5) Previous issue date: 2005 / Resumo: Uma representação PI consiste em duas retas paralelas, r e s, e triângulos com um vértice em r e um lado em s. Considere R uma representação PI. O grafo interseção de R é chamado grafo P I quando cada vértice do grafo corresponde a um triângulo de R e existe aresta entre dois vértices se, e somente se, os triângulos correspondentes se intersectam. Segundo o livro Graph Classes - a Survey (1999) [3], escrito por Brandstiidt, Le e Spinrad, os problemas de reconhecer e de caracterizar a classe dos grafos PI ainda não estão resolvidos. Essa é a principal motivação para o estudo da classe PI. Nesta dissertação, apresentamos um estudo dos grafos PI baseado nas suas relações com outras classes de grafos tais como os grafos de intervalos e permutação, que são classes amplamente conhecidas de grafos interseção, e os grafos trapezóides, que possuem uma estrutura muito semelhante à dos grafos PI. Esta dissertação é uma síntese de trabalhos existentes sobre a classe PI e apresenta novas condições necessárias e/ou suficientes para que um grafo seja PI / Abstract: A PI-representation consists of two parallellines, r and s, and triangles with one vertex on r and the other two on s. Let R be a PI-representation. The intersection graph of R is called PI graph when each vertex in the graph corresponds to a triangle in R and there exists an edge between two vertices if and only if their corresponding triangles intersect. According to the book Graph Classes - a Survey (1999) [3], by Brandstiidt, Le and Spinrad, the PI graph characterization and recognition problems are still open. This is the main motivation for the study of the PI graph class. In this dissertation, we present a study of PI graphs based on their relationship with other graph classes such as the interval and permutation graphs, which are well known intersection graph classes, and trapezoid graphs, which have a very similar structure to that of PI graphs. This dissertation is a survey on existing work on the PI graph class and presents new necessary andj or sufficient conditions for a graph to be PI / Mestrado / Teoria da Computação / Mestre em Ciência da Computação