Graph transformation


Graph transformation

Graph transformation, or Graph rewriting, concerns the technique to create a new graph out of an original graph using some automatic machine. It has numerous applications, ranging from software verification to layout algorithms.

Graph transformations can be used as a computation abstraction. The basic idea is that the state of a computation can be represented as a graph, further steps in that computation can then be represented as transformation rules on that graph. Such rules consist of an original graph, which is to be matched to a subgraph in the complete state, and a replacing graph, which will replace the matched subgraph.

References

* [http://www.gratra.org/ Graph Transformation and Graph Grammars]
* Heckel, R. (2006). "Graph transformation in a nutshell". [http://www.elsevier.com/locate/entcs Electronic Notes in Theoretical Computer Science] 148 (1 SPEC. ISS.), pp. 187-198.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Graph rewriting — In graph theory, graph rewriting is a system of rewriting for graphs, i.e. a set of graph rewrite rules of the form p: L ightarrow R, with L being called pattern graph (or left hand side) and R being called replacement graph (or right hand side… …   Wikipedia

  • transformation curve — graph that depicts boundary possibilities for manufacturing efficiency for two products (Economics) …   English contemporary dictionary

  • transformation — transformational, adj. /trans feuhr may sheuhn/, n. 1. the act or process of transforming. 2. the state of being transformed. 3. change in form, appearance, nature, or character. 4. Theat. a seemingly miraculous change in the appearance of… …   Universalium

  • Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and …   Wikipedia

  • Model transformation — A model transformation, in model driven engineering, is an automatable way of ensuring that a family of models is consistent, in a precise sense which the software engineer can define. The aim of using a model transformation is to save effort and …   Wikipedia

  • Model transformation language — A model transformation language in systems and software engineering is a language for model transformation. Contents 1 Overview 2 Available transformation languages 3 See also 4 …   Wikipedia

  • Tripel-Graph-Grammatik — Als Tripel Graph Grammatik (engl. triple graph grammar, kurz: TGG) bezeichnet man eine spezielle Art von Graphgrammatik, die vor allem für bidirektionale Modell zu Modell Transformationen verwendet wird. Besonderheit von Tripel Graph Grammatiken… …   Deutsch Wikipedia

  • Scene graph — A scene graph is a general data structure commonly used by vector based graphics editing applications and modern computer games. Examples of such programs include AutoCAD, Adobe Illustrator, Acrobat 3D, OpenSceneGraph and CorelDRAW.The scene… …   Wikipedia

  • Legendre transformation — f(x) . The function is shown in red, and the tangent line at point (x 0, f(x 0)) is shown in blue. The tangent line intersects the vertical axis at (0, f^star) and f^star is the value of the Legendre transform f^star(p 0) , where p 0=dot{f}(x 0) …   Wikipedia

  • Data transformation (statistics) — A scatterplot in which the areas of the sovereign states and dependent territories in the world are plotted on the vertical axis against their populations on the horizontal axis. The upper plot uses raw data. In the lower plot, both the area and… …   Wikipedia