Made available in DSpace on 2016-08-29T15:33:24Z (GMT). No. of bitstreams: 1 tese_9681_Ata de Defesa.pdf: 637986 bytes, checksum: 049a7d2723e6d0c1208ad9aad2eb9d0d (MD5) Previous issue date: 2016-03-28 / Um dos problemas clássicos da Teoria de Grafos é o problema de isomorfismo de grafos. Esse problema trata de determinar se, dado dois grafos, é possível definir um mapeamento entre seus vértices de forma que sejam respeitadas as conexões definidas por suas arestas. Um algoritmo proposto recentemente para resolver esse problema é o IVL (Iterated Vertex Labelling) [Baroni (2012)]. O GROOVE (GRaph-based Object-Oriented VErification) é uma ferramenta de verificação de modelos baseados em grafos que faz uso de algoritmos de isomorfismo. No contexto do GROOVE, o problema de isomorfismo de grafos se apresenta de uma maneira diferente do problema clássico: não se deseja determinar se dois grafos são isomorfos, e sim se, dado um grafo, ele é isomorfo a algum dos elementos de um conjunto de grafos. Neste trabalho, propõe-se a adaptação do IVL para o GROOVE e a realiza- ção de experimentos computacionais com o objetivo de determinar se essa adaptação traz ganhos de performance para a ferramenta. Os resultados levam à conclusão de que o IVL tem desempenho análogo ao algoritmo de isomorfismos que já está implementado no GROOVE. Além desses resultados, foi investigado em um cenário similar o uso de filtros de não-isomorfismo, com a intenção de determinar o não-isomorfismo entre dois grafos a um custo computacional baixo. Os resultados dos testes indicam que essa abordagem é bastante promissora, sendo capaz de detectar não-isomorfismos com eficiência de quase 100% , com tempos de execução bem mais baixos que os performados pelo algoritmo atual do GROOVE quando executado nesse cenário adaptado. / The graph isomorphism is a classical problem in Graph Theory, which consists of determining if, given two graphs, it is possible to define a mapping between their vertexes in a way so that the connection defined by their edges are respected. An algorithm proposed recently to solve this problem is the IVL (Iterated Vertex Labelling) [Baroni (2012)]. GROOVE (GRaph-based Object-Oriented VErification) is a graph-based model checking tool which makes use of isomorphism algorithms. In GROOVE’s context, the graph isomorphism problem is set differently from the classical problem: they are not interested on determining if two graphs are isomorphic, instead, they want to determine if, given a graph, it is isomorphic to one of the elements of a graph set. In this work, it’s proposed the IVL adaptation to GROOVE and computational experiments in order to test if this new adapted algorithm brings performance gains to the tool. It can be concluded from the results that IVL has a similar performance compared to the current implementation in GROOVE. Beyond those results, it was investigated in a similar framework the use of non-isomorphism filters, intending to determine the non-isomorphism between two graphs in a low computational cost. The test results point out that this is a promising approach, being able to detect non-isomorphisms with almost 100% efficiency, with a much lower running time when compared to current GROOVE algorithm when executed in this framework.

Made available in DSpace on 2016-08-29T15:33:23Z (GMT). No. of bitstreams: 1 tese_9288_Ata de Defesa.pdf: 225566 bytes, checksum: 6da0bfa73a8135bc0ede55dc01438148 (MD5) Previous issue date: 2015-10-30 / CAPES / A modelagem de situações para aplicações sensíveis ao contexto, também chamadas de aplicações sensíveis a situações, é, por um lado, uma tarefa chave para o funcionamento adequado dessas aplicações. Por outro lado, essa também é uma tafera árdua graças à complexidade e à vasta gama de tipos de situações possíveis. Com o intuito de facilitar a representação desses tipos de situações em tempo de projeto, foi criada a Linguagem de Modelagem de Situações (Situation Modeling Language - SML), a qual se baseia parcialmente em ricas teorias ontológicas de modelagem conceitual, além de fornecer uma plataforma de detecção de situação em tempo de execução. Apesar do benefício da existência dessa infraestrutura, a tarefa de definir tipos de situação é ainda não-trivial, podendo carregar problemas que dificilmente são detectados por modeladores via inspeções manuais. Esta dissertação tem o propósito de melhorar e facilitar ainda mais a definição de tipos de situação em SML propondo: (i) uma maior integração da linguagem com as teorias ontológicas de modelagem conceitual pelo uso da linguagem OntoUML, visando aumentar a expressividade dos modelos de situação; e (ii) uma abordagem para validação de tipos de situação usando um método formal, visando garantir que os modelos criados correspondam à intenção do modelador. Tanto a integração quanto a validação são implementadas em uma ferramenta para especificação, verificação e validação de tipos de situação ontologicamente enriquecidos. / The modeling of situation types for context-aware applications, also called situationaware applications, is, on the one hand, a key task to the proper functioning of those applications. On the other hand, it is also a hard task given the complexity and the wide range of possible situation types. Aiming at facilitating the representation of those types of situations at design-time, the Situation Modeling Language (SML) was created. This language is based partially on rich ontological theories of conceptual modeling and is accompanied by a platform for situation-detection at runtime. Despite the benefits of the availability of this suitable infrastructure, the definition of situation types, being a non-trivial task, can still pose problems that are hardly detected by modelers by manual model inspection. This thesis aims at improving and facilitating the definition of situation types in SML by proposing: (i) the integration between the language and the ontological theories of conceptual modeling by using the OntoUML language, with the purpose of increasing the expressivity of situation type models; and (ii) an approach for the validation of situation type models using a lightweight formal method, aiming at increasing the correspondence between the created models’ instances and the modeler’s intentions. Both the integration and the validation are implemented in a tool for specification, verification and validation of ontologically-enriched situation types.