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. / 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.

Les travaux de cette thèse ont pour cadre la vérification formelle, et plus spécifiquement le projet ANR Blanc CLIMT (Categorical and Logical Methods in Model Transformation) dédié aux grammaires de graphes. Ce projet, qui a démarré en février 2012 pour une durée de 48 mois, a donné lieu à la définition du langage Small-tALC, bâti sur la logique de description ALCQI. Ce langage prend la forme d’un DSL (Domain Specific Language) impératif à base de règles, chacune dérivant structurellement un graphe. Le langage s’accompagne d’un composant de preuve basé sur la logique de Hoare chargé d’automatiser le processus de vérification d’une règle. Cependant, force est de constater que tous les praticiens ne sont pas nécessairement familiers avec les méthodes formelles du génie logiciel et que les transformations sont complexes à écrire. En particulier, ne disposant que du seul prouveur, il s’agit pour le développeur Small-tALC d’écrire un triplet de Hoare {P} S {Q} et d’attendre le verdict de sa correction sous la forme d’un graphe contre-exemple en cas d’échec. Ce contre-exemple est parfois difficile à décrypter, et ne permet pas de localiser aisément l’erreur au sein du triplet. De plus, le prouveur ne valide qu’une seule règle à la fois, sans considérer l’ensemble des règles de transformation et leur ordonnancement d’exécution. Ce constat nous a conduits à proposer un environnement d’assistance au développeur Small-tALC. Cette assistance vise à l’aider à rédiger ses triplets et à prouver ses transformations, en lui offrant plus de rétroaction que le prouveur. Pour ce faire, les instructions du langage ont été revisitées selon l’angle ABox et TBox de la logique ALCQI. Ainsi, conformément aux logiques de description, la mise à jour du graphe par la règle s’assimile à la mise à jour ABox des individus (les nœuds) et de leurs relations (les arcs) d’un domaine terminologique TBox (le type des nœuds et les étiquettes des arcs) susceptible d’évoluer. Les contributions de cette thèse concernent : (1) un extracteur de préconditions ABox à partir d’un code de transformation S et de sa postcondition Q pour l’écriture d’une règle {P} S {Q} correcte par construction, (2) un raisonneur TBox capable d’inférer des propriétés sur des ensembles de nœuds transformés par un enchaînement de règles {Pi} Si {Qi}, et (3) d’autres diagnostics ABox et TBox sous la forme de tests afin d’identifier et de localiser des problèmes dans les programmes. L’analyse statique du code de transformation d’une règle, combinée à un calcul d’alias des variables désignant les nœuds du graphe, permet d’extraire un ensemble de préconditions ABox validant la règle. Les inférences TBox pour un enchaînement de règles résultent d’une analyse statique par interprétation abstraite des règles ABox afin de vérifier formellement des états du graphe avant et après les appels des règles. A ces deux outils formels s’ajoutent des analyseurs dynamiques produisant une batterie de tests pour une règle ABox, ou un diagnostic TBox pour une séquence de règles / The overall context of this thesis is formal verification, and more specifically the ANR Blanc CLIMT project (Categorical and Logical Methods in Model Transformation) dedicated to graph grammars. This project, which started in February 2012 for 48 months, gave rise to the development of the Small- tALC language, a graph transformation language based on the ALCQI description logic. This language takes the form of an imperative DSL (Domain Specific Language) based on rules; from each rule structurally derives a graph. It goes with a proof component based on Hoare's logic designed to automate the process of rule verification. However, it must be assumed that not all developers are familiar with formal methods of software engineering, and that graph transformations are complex to write. In particular, using exclusively the prover, the Small- tALC developer must write a Hoare triple {P} S {Q} and wait for the feedback in the form of a counterexample graph in case of failure. This counter-example is sometimes difficult to interpret, and so it does not allow to easily locate the error within the triple. Moreover, the prover validates only one rule at once, without considering all the transformation rules and their execution order. This fact led us to propose an assistance framework for Small- tALC to help developers write their triples and prove their transformations, providing them more feedback than the prover does. To this purpose, the Small- tALC instructions have been reviewed according to the ABox and TBox aspects of the ALCQI logic. Thus, in accordance with description logics, updating the graph by the rule corresponds to the ABox updating of individuals (nodes) and their relationships (edges) of a TBox terminology domain (nodes concepts and edges labels) that is also expected to evolve. The contributions of this thesis concern: (1) an ABox precondition extractor from a transformation code S and its post-condition Q in order to produce a correct by construction rule {P} S {Q}, (2) a TBox reasoner to infer properties on sets of nodes transformed by a rule sequence {Pi} Si {Qi}, and (3) other ABox and TBox diagnostics based on tests to identify and locate errors in programs. The static analysis of the code of a transformation rule, combined with an alias calculus of the variables that can not designate the same nodes of the graph, allows to extract a set of ABox preconditions validating the rule. TBox inferences related to a sequence of rules result from a static analysis by abstract interpretation of the ABox rules. These inferences formally check graph states before and after rule calls. Beside these two formal tools, the framework features dynamic analyzers that produce test cases for an ABox rule, or a TBox diagnosis for a sequence of rules

For the modelling of chemistry we use undirected, labelled graphs as explicit models of molecules and graph transformation rules for modelling generalised chemical reactions. This is used to define artificial chemistries on the level of individual bonds and atoms, where formal graph grammars implicitly represent large spaces of chemical compounds. We use a graph rewriting formalism, rooted in category theory, called the Double Pushout approach, which directly expresses the transition state of chemical reactions. Using concurrency theory for transformation rules, we define algorithms for the composition of rewrite rules in a chemically intuitive manner that enable automatic abstraction of the level of detail in chemical pathways. Based on this rule composition we define an algorithmic framework for generation of vast reaction networks for specific spaces of a given chemistry, while still maintaining the level of detail of the model down to the atomic level. The framework also allows for computation with graphs and graph grammars, which is utilised to model non-trivial chemical systems. The graph generation relies on graph isomorphism testing, and we review the general individualisation-refinement paradigm used in the state-of-the-art algorithms for graph canonicalisation, isomorphism testing, and automorphism discovery. We present a model for chemical pathways based on a generalisation of network flows from ordinary directed graphs to directed hypergraphs. The model allows for reasoning about the flow of individual molecules in general pathways, and the introduction of chemically motivated routing constraints. It further provides the foundation for defining specialised pathway motifs, which is illustrated by defining necessary topological constraints for both catalytic and autocatalytic pathways. We also prove that central types of pathway questions are NP-complete, even for restricted classes of reaction networks. The complete pathway model, including constraints for catalytic and autocatalytic pathways, is implemented using integer linear programming. This implementation is used in a tree search method to enumerate both optimal and near-optimal pathway solutions. The formal methods are applied to multiple chemical systems: the enzyme catalysed beta-lactamase reaction, variations of the glycolysis pathway, and the formose process. In each of these systems we use rule composition to abstract pathways and calculate traces for isotope labelled carbon atoms. The pathway model is used to automatically enumerate alternative non-oxidative glycolysis pathways, and enumerate thousands of candidates for autocatalytic pathways in the formose process.

Correct certificate revocation practices are essential to each public-key infrastructure. While there exist a number of protocols to achieve revocation in PKI systems, there has been very little work on the theory behind it: Which different types of revocation can be identified? What is the intended effect of a specific revocation type to the knowledge base of each entity? As a first step towards a methodology for the development of reliable models, we present a graph-based formalism for specification and reasoning about the distribution and revocation of public keys and certificates. The model is an abstract generalization of existing PKIs and distributed in nature; each entity can issue certificates for public keys that they have confidence in, and distribute or revoke these to and from other entities. Each entity has its own public-key base and can derive new knowledge by combining this knowledge with certificates signed with known keys. Each statement that is deduced or quoted within the system derives its support from original knowledge formed outside the system. When such original knowledge is removed, all statements that depended upon it are removed as well. Cyclic support is avoided through the use of support sets. We define different revocation reasons and show how they can be modelled as specific actions. Revocation by removal, by inactivation, and by negation are all included. By policy, negative statements are the strongest, and positive are the weakest. Collisions are avoided by removing the weaker statement and, when necessary, its support. Graph transformation rules are the chosen formalism. Rules are either interactive changes that can be applied by entities, or automatically applied deductions that keep the system sound and complete after the application of an interactive rule. We show that the proposed model is sound and complete with respect to our definition of a valid state. / <p>Report code: LIU-TEK-LIC-2006:1</p>

The complex business applications are increasingly offered as services over the Internet, so-called software-as-a-Service (SaaS) applications. The SAP Netweaver Cloud offers an OSGI-based open platform, which enables multi-tenant SaaS applications to run in the cloud. A multi-tenant SaaS application is designed so that an application instance is used by several customers and their users. As different customers have different requirements for functionality and quality of the application, the application instance must be configurable. Therefore, it must be able to add new configurations into a multi-tenant SaaS application at run-time. In this thesis, we proposed concepts of a configuration management, which are used for managing and creating client configurations of cloud applications. The concepts are implemented in a tool that is based on Eclipse and extended feature models. In addition, we evaluate our concepts and the applicability of the developed solution in the SAP Netwaver Cloud by using a cloud application as a concrete case example.

The complex business applications are increasingly offered as services over the Internet, so-called software-as-a-Service (SaaS) applications. The SAP Netweaver Cloud offers an OSGI-based open platform, which enables multi-tenant SaaS applications to run in the cloud. A multi-tenant SaaS application is designed so that an application instance is used by several customers and their users. As different customers have different requirements for functionality and quality of the application, the application instance must be configurable. Therefore, it must be able to add new configurations into a multi-tenant SaaS application at run-time. In this thesis, we proposed concepts of a configuration management, which are used for managing and creating client configurations of cloud applications. The concepts are implemented in a tool that is based on Eclipse and extended feature models. In addition, we evaluate our concepts and the applicability of the developed solution in the SAP Netwaver Cloud by using a cloud application as a concrete case example.:List of Figures i List of Tables iii 1 Introduction 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 The Structure of This Document . . . . . . . . . . . . . . . . . 2 2 Background 5 2.1 Cloud Computing . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Software Product Line Engineering . . . . . . . . . . . . . . . . 7 2.3 Role Based Access Control . . . . . . . . . . . . . . . . . . . . . 10 2.4 Staged Con guration . . . . . . . . . . . . . . . . . . . . . . . . 12 2.5 Work ow Modeling . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.5.1 Concept . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.5.2 Work ow Modeling Languages . . . . . . . . . . . . . . . 16 2.5.3 Adaptive Work ow . . . . . . . . . . . . . . . . . . . . . 17 2.5.4 Adaptation Patterns . . . . . . . . . . . . . . . . . . . . 17 2.6 Graph Transformation . . . . . . . . . . . . . . . . . . . . . . . 18 2.7 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3 Analysis 23 3.1 Illustrative Example . . . . . . . . . . . . . . . . . . . . . . . . 23 3.1.1 Domain and Exiting Platform . . . . . . . . . . . . . . . 24 3.1.2 Yard Management System as a SaaS Application . . . . 28 3.2 Requirements Identi cation . . . . . . . . . . . . . . . . . . . . 28 4 Concept 31 4.1 Con guration Management Speci cation . . . . . . . . . . . . . 31 4.1.1 Variability Modeling . . . . . . . . . . . . . . . . . . . . 32 4.1.2 Stakeholder Views Modeling . . . . . . . . . . . . . . . . 34 4.1.3 Con guration Work ow Modeling . . . . . . . . . . . . . 36 4.2 Con guration Work ow Adaptations . . . . . . . . . . . . . . . 41 4.3 Mapping between Problem Space and Solution Space . . . . . . 47 4.4 Con guration Process Simulation . . . . . . . . . . . . . . . . . 50 5 Implementation 53 5.1 Con guration Speci cation . . . . . . . . . . . . . . . . . . . . . 54 5.1.1 Extended Feature Model Speci cation . . . . . . . . . . 55 5.1.2 View Model Speci cation . . . . . . . . . . . . . . . . . . 56 5.1.3 Con guration Work ow Model Speci cation . . . . . . . 57 5.2 Graph Transformation Rules . . . . . . . . . . . . . . . . . . . . 62 5.3 Mapping Realization . . . . . . . . . . . . . . . . . . . . . . . . 65 5.4 Con guration Management Tooling . . . . . . . . . . . . . . . . 67 5.5 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 6 Conclusions and Future Work 77 6.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 Bibliography i

La modélisation géométrique est utilisée dans de nombreux domaines pour la construction d’objets 3D, l’animation ou les simulations. Chaque domaine est soumis à ses propres contraintes et nécessiterait un outil dédié. En pratique, un même outil est utilisé pour plusieurs domaines, en factorisant les caractéristiques communes. Ces modeleurs fournissent un ensemble d'opérations types, que l'utilisateur compose pour construire ses objets. Pour des opérations plus spécifiques, les outils actuels offrent des API.La plate-forme Jerboa propose un outil de génération d'opérations géométriques personnalisées. Elles sont définies graphiquement par des règles de transformations de graphes. Des vérifications automatiques de préservation de la cohérence des objets sont faites lors de l’édition qui peuvent être enrichies par des propriétés métiers. Notre contribution a consisté à étendre le langage par des scripts, pour composer les règles et réaliser des opérations complexes. Nous avons étendu les vérifications automatiques, en particulier pour assurer la cohérence géométrique. Enfin, nous avons modifié le processus d'application des opérations pour augmenter les possibilités de contrôle.Pour valider cette approche, nous avons développé un modeleur dédié à la géologie, pour la représentation du sous-sol, en collaboration avec l'entreprise Géosiris. Nous avons défini un flux d'activité avec Géosiris en suivant des contraintes spécifiques à la géologie. Grâce à la rapidité de développement des opérations dans Jerboa, nous avons pu prototyper et tester rapidement plusieurs algorithmes de reconstruction du sous-sol, pour les appliquer sur des données réelles fournies par l'entreprise. / Geometric modeling is used in various scopes for 3D object construction, animation or simulations. Each domain must cope with its constraints and should have its dedicated tool. In fact, several common characteristics of different domains are factored in a single tool. These modelers contain sets of basic operations that the user composes to build his objects. For more specific operations, current common tools offer API.Jerboa’s platform allows to generate personalized geometrical operations. These are defined by graph transformation rules. During their design, many automated verifications are done for the preserving of object consistency. They also be enriched with additional properties. Our contribution consists in extending the Jerboa language with scripts to compose rules and define complex operations. We also extended automated verifications, in particular to ensure geometric consistaency. Finally, we modified operations application process, in order to increase user control possibilities.To validate this approach, we have implemented a geological dedicated modeler for subsoil modeling, in collaboration with Geosiris Company. We defined a workflow with Geosiris that follows specific geological reconstruction constraints. Thanks to the Jerboa rapid prototyping mecanism, we developped and quickly tested several subsoil reconstruction algorithms, and apply them to real data provided by the company.

Vários métodos de especificação procuram realizar a modelagem de sistemas sob três visões: uma visão funcional, que procura apresentar as informações que trafegam entre os diversos componentes do sistema, uma visão de dados, que apresenta as relações entre as estruturas de dados estáticas do sistema e a visão dinâmica, que mostra as transformações que o sistema pode sofrer ao longo do tempo. Alguns modelos procuram integrar mais de uma visão, mas, em geral, os modelos possuem sérias deficiências ao tentarem representar mais de um aspecto do sistema ao mesmo tempo, sendo necessário o apoio de outros métodos. Este trabalho apresenta um método de especificação de sistemas que procura integrar a modelagem de dados com a modelagem funcional e dinâmica utilizando-se, para isso, das Gramáticas de Grafos como método formal de especificação. Sendo um grafo formado por vértices, arestas e rótulos, pode-se facilmente criar uma camada de abstração em que o usuário (em geral responsável pela análise de sistemas) manipule um método de especificação com o qual já convive, agora com uma semântica formal definida. Espera-se, com a aplicação do método, gerar modelos passíveis de prova, não ambíguos e que promovam um incremento de qualidade no sistema gerado. / Several specification methods try to realize system modeling following three visions: the functional vision, which is based on representing the information exchange among the several components of the system; the data vision, which represents the relations among the static data structures of the system; and the dynamic vision, which presents the transformations the system may endure over the time. Some models exist that try to integrate more than one of these visions, but, in general, they suffer from deficiencies when trying to represent more than one aspect of the system at the same time, in which case the use of other methods is necessary. This work presents a novel method of systems specification that attempts to integrate data modeling with functional and dynamic modelings using, for this, Graph Grammars as its formal specification method. A graph, being made of nodes, edges and labels, is appropriate for creating, easily, an abstraction layer in which the user (usually responsible for the system analysis) manipulates a specification method which is known to him, but now with a well defined formal semantics. We hope, by applying this method, to generate provable, unambiguous models which promote an increase in the quality of the generated system.

Programas sofrem diversas modificações ao longo das etapas de desenvolvimento, implantação e manutenção. A evolução de um software pode ter várias causas: correção de erros, inclusão de novas funcionalidades ou até mesmo, como é o caso de programas orientados a aspecto, transformações estruturais podem fazer parte da semântica do sistema. Apesar de modificações serem comuns, não é tarefa trivial prever como estas afetam o comportamento dos programas, já que os componentes de software normalmente interagem de forma complexa, o que faz com que mesmo pequenas alterações possam introduzir comportamentos indesejados. Transformação de grafos, também conhecida como reescrita de grafos, é um importante paradigma para modelagem e análise de sistemas. Modelos baseados em transformação de grafos, como gramáticas de grafos, permitem uma modelagem ao mesmo tempo intuitiva e com semântica precisa, permitindo a aplicação de técnicas de análise como verificação de modelos e análise de par crítico no estudo do comportamento de sistemas. A teoria por trás de transformação de grafos vem sendo desenvolvida a várias décadas, e atualmente está descrita de uma forma bastante abstrata. Contudo, ainda não possui uma definição natural de reescritas de alta ordem, que facilitaria a definição de evolução de especificações compostas por regras de reescrita de grafo, tais como gramáticas de grafos. Nesta tese são abordadas a modelagem e a análise de sistemas sob modificações programadas no contexto de gramáticas de grafos. A generalização da abordagem de pushout duplo para reescrita de grafos é utilizada como o princípio geral para descrever, simultaneamente, a semântica do sistema e modificações estruturais. Para tal, introduzimos uma noção de reescrita de segunda ordem para modificar a estrutura de regras de transformação de grafos, e usando isso, definimos modelos equipados simultaneamente de regras de primeira e segunda ordem, chamados gramáticas de grafos de segunda ordem. Através destes modelos podemos representar simultaneamente transformações estruturais e execução do sistema, e relacionar formalmente ambos tipos de reescrita. Também propomos novas técnicas para investigar o efeito da modificação de regras sobre a aplicação destas. Finalmente, como um exemplo de aplicação da teoria, caracterizamos construções de sistemas orientados a aspectos através de gramáticas de grafos de segunda ordem, e discutimos como utilizar as novas técnicas para estudar o efeito da combinação aspectual sobre o sistema inicial. / Software systems are not static entities: they usually undergo several changes along their development and maintenance cycles. Software evolution may be required for several reasons, such as the inclusion of new functionalities, the correction of errors or even as part of the system semantics, as it is the case of aspect-oriented systems. However, it is usually not trivial to foresee how structural changes can affect the system behaviour, since system components often interact in very complex ways, and even trivial modifications may introduce new problems. Graph transformation, also known as graph rewriting, has been used throughout the years as an important paradigm for system modelling and analysis. Models based on graph transformation, such as graph grammars, allow an intuitive but formal representation of the system behaviour, allowing the usage of analysis techniques such as model checking and static analysis of rule interaction. The theory behind graph transformation is quite general, and has been studied since the 1970s. However, it still lacks a general notion of higher-order rewriting that would allow a natural definition of model transformations for graph grammars. The lack of general second-order characterization presents difficulties for employing graph grammars as targets of model transformations, and studying how model transformations affect their natural behaviour. In this thesis we address the problem of modelling and analysing systems undergoing programmed modifications in the context of graph grammars. We use the generalization of the double-pushout approach for graph rewriting as a principle for defining simultaneously the system semantics and structural modifications. To achieve this, we introduce a notion of second-order graph rewriting that acts on graph transformation rules. Based on secondorder rewriting we are able to define second-order graph grammars, models equipped with a first-order layer, representing the original system execution, and a second-order layer, representing a model transformation. Using second-order graph grammar we can encode simultaneously model transformations and system execution, allowing us to formally relate them. Moreover, we propose new techniques to investigate the effect of rule modification over their effect on graphs. As an application example, we characterize aspect-oriented constructions for graph grammars, and discuss how to relate the aspect weaving layer with the base system semantics.

Vários métodos de especificação procuram realizar a modelagem de sistemas sob três visões: uma visão funcional, que procura apresentar as informações que trafegam entre os diversos componentes do sistema, uma visão de dados, que apresenta as relações entre as estruturas de dados estáticas do sistema e a visão dinâmica, que mostra as transformações que o sistema pode sofrer ao longo do tempo. Alguns modelos procuram integrar mais de uma visão, mas, em geral, os modelos possuem sérias deficiências ao tentarem representar mais de um aspecto do sistema ao mesmo tempo, sendo necessário o apoio de outros métodos. Este trabalho apresenta um método de especificação de sistemas que procura integrar a modelagem de dados com a modelagem funcional e dinâmica utilizando-se, para isso, das Gramáticas de Grafos como método formal de especificação. Sendo um grafo formado por vértices, arestas e rótulos, pode-se facilmente criar uma camada de abstração em que o usuário (em geral responsável pela análise de sistemas) manipule um método de especificação com o qual já convive, agora com uma semântica formal definida. Espera-se, com a aplicação do método, gerar modelos passíveis de prova, não ambíguos e que promovam um incremento de qualidade no sistema gerado. / Several specification methods try to realize system modeling following three visions: the functional vision, which is based on representing the information exchange among the several components of the system; the data vision, which represents the relations among the static data structures of the system; and the dynamic vision, which presents the transformations the system may endure over the time. Some models exist that try to integrate more than one of these visions, but, in general, they suffer from deficiencies when trying to represent more than one aspect of the system at the same time, in which case the use of other methods is necessary. This work presents a novel method of systems specification that attempts to integrate data modeling with functional and dynamic modelings using, for this, Graph Grammars as its formal specification method. A graph, being made of nodes, edges and labels, is appropriate for creating, easily, an abstraction layer in which the user (usually responsible for the system analysis) manipulates a specification method which is known to him, but now with a well defined formal semantics. We hope, by applying this method, to generate provable, unambiguous models which promote an increase in the quality of the generated system.