Repositório Digital

A- A A+

Transactional graph transformation systems

.

Transactional graph transformation systems

Mostrar registro completo

Estatísticas

Título Transactional graph transformation systems
Outro título Sistemas de transformação de grafos transacionais
Autor Foss, Luciana
Orientador Ribeiro, Leila
Co-orientador Corradini, Andrea
Data 2008
Nível Doutorado
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Informática. Programa de Pós-Graduação em Computação.
Assunto Gramatica : Grafos
Programação
Programação orientada : Objetos
Teoria da computação
[en] Graph transformation
[en] Interaction pattern
[en] Refinement
[en] Transactions
Resumo Em contraste aos sistemas transformacionais, sistemas reativos são caracterisados por reagir continuamente a estímulos provinientes seu ambiente. Além da reatividade, se considerarmos que muitas aplicações requerem métodos de especificação que possibilitam descrever a distribuição espacial dos estados, sistemas de transformação de grafos parecem ser uma técnica de especificação bastante adequada. Algumas aplicações com essas características são sistemas móveis e vias biológicas. Além disso, diversas abordagens para especificação de sistemas reativos propõem usar linguagens assíncronas para especificar a comunicação entre componentes e definem mecanismos para descrever um conjunto (ou seqüência) de atividades que são realizadas atomicamente. Porém, pouca atenção tem sido dada à idéia de estender sistemas de transformação de grafos para permitir a especificação de atividades atômicas. Recentemente, inspirada nas idéias das redes de Petri “zero-safe” foi definida uma extensão de sistemas de transformação de grafos (GTS) – denominada GTS transacional (T-GTS) – equipando-os com uma noção de transação. Uma transação, nesta abordagem, descreve um conjunto de ações que são executadas de um modo atômico e é definida através de uma distinção entre os recursos visíveis e invisíveis de um ponto de vista externo, onde os últimos são considerados temporários e “esquecidos” em um nível abstrato. Nesta tese é dada uma fundamentação mais teórica para T-GTSs definindo uma noção de morfismos de implementação T-GTS (associando produções de um sistema com transações de outro) e, usando essa noção, é demonstrada a existência de uma adjunção entre as categorias de GTSs e T-GTSs com morfismos de implementação. Além disso, GTSs transacionais são estendidas com um mecanismo para descrever padrões de interação de sistemas reativos através de relações de dependência incluídas nas produções. A idéia é que um sitema interage com seu ambiente consumindo e criando elementos visíveis para à esse ambiente, uma relação de causalidade. Finalmente, propomos uma noção de refinamento para T-GTSs com relação de dependência caracterizada por uma visão “caixa-devidro”, onde alguns aspectos internos são preservados. Em um nível abstrato, o sistema é especificado por produções que descrevem (de uma maneira atômica) reações completas, onde a relação de dependência determina algumas restrições na estrutura interna dessas reações. Um refinamento de um sistema é definido por um morfismo total de implementação que associa cada produção (abstrata) a uma transação. Assim, o sistema refinado preserva todo o comportamento externo do sistema original e as restrições da estrutura interna determinadas pelas relações de dependência.
Abstract Reactive systems, in contrast to transformational systems, are characterised by having to continuously react to stimuli from its environment. If, in addition to reactiveness, we consider that for many applications the specification method should provide a way to describe the spatial distribution of states, graph transformation seems to be a suitable specification technique. Some applications with these characteristics are mobile systems and biological pathways. However, the approaches provided for graph transformations so far are not adequate to explicitly describe interaction patterns. Furthermore, several approaches to specify reactive systems propose to use asynchronous languages to specify communication between components and define mechanisms to describe a set (or sequence) of activities that are performed atomically. However, scarce attention has been devoted to the idea of extending GTSs in order to allow the specification of atomic activities. Inspired by the ideas of zero-safe Petri nets, an extension of graph transformation systems (GTSs) – called transactional GTS (T-GTS) – was defined, equipping them with a transaction notion. A transaction, in this approach, describes a set of actions that are executed in an atomic way and it is defined by distinguishing the resources that are visible or invisible from an external point of view, where the last ones are considered temporary and are forgotten at a more abstract level. In this thesis, we give a more theoretical foundation to T-GTS defining a notion of implementation morphisms between T-GTSs (associating graph productions of a system with transactions of other system) and using this notion we demonstrate the existence of an adjunction between categories of GTSs and T-GTSs with implementation morphisms. Moreover, we extends transactional GTSs with a mechanism to describe interaction patterns of reactive systems, by means of dependency relations included in the graph productions. The idea is that a system interacts with its environment by consuming and creating elements visible to this environment, obeying a causal dependency. Finally, we propose a notion of glass-box refinement for T-GTSs with dependency relations, where some internal aspects are preserved. In an abstract level, the system is specified by productions describing (in an atomic way) complete reactions, where the dependency relations give some constraints on the internal structure of these reactions. A refinement of a system is given by a total implementation morphism, that associates each (abstract) production to a transaction. Hence, the refined system preserves all external behaviour of the original system and the internal constraints given by the dependency relations.
Tipo Tese
URI http://hdl.handle.net/10183/14966
Arquivos Descrição Formato
000673327.pdf (1.183Mb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.