Graph Transformation

Graphical structures of various kind (like graphs, diagrams, visual sentences and others) are very useful to describe complex structures and systems in a direct and intuitive way. For instance, graphs can be used to represent the logical and topological relations among the components of a distributed system, the connectivity in a network, the rights that system entities have over resources, the structure of the heap for a program with dynamic pointer structures. The field of Graph Transformation is concerned with computational formalisms which add to this static description a further dimension, modeling the evolution of systems via rule-based transformation of such graphical structures. In the tutorial I will first overview the theoretical foundations of Graph Transformation, focusing on the so-called ”algebraic approach” and stressing the relationship with other rule-based computational formalisms, like Term Rewriting and Petri Nets. Next I will survey some application fields where Graph Transformations have been exploited usefully, as well as the available tools which provide some automated support for the development and analysis of such systems. I will conclude by discussing some ongoing advances in the theory of Graph Transformation Systems, including original analysis and verification techniques and the generalization of the algebraic approach to more general structures.

http://www.lbd.dcc.ufmg.br/colecoes/sbmf/2005/007.pdf

Biblioteca Digital Brasileira de Computação - Contato: bdbcomp@lbd.dcc.ufmg.br