Graph rewriting

Graph rewriting systems are used for the formal description of the modification of graphene. They are often implemented with computer programs and thus made ​​executable or applicable.

A graph rewriting system is a set of graph rewrite rules. A graph rewrite rule consists of the pattern graph of the left side as well as the replacement graph of the right hand side.

A rule is applied in a direct derivation, is the working graph before the rule application, the modified graph after work. A rule application consists of finding an instance of in (Pattern Matching, here: subgraph isomorphism ) and replacing the instance found by an instance of the right side. A derivation is a sequence of rule applications that transforms a graph output in a resultant graph.

Shifts the focus from changing a given graph towards the creation of all derivable from a start graph graph, is spoken by a graph grammar instead of a graph rewriting system and productions instead of rules. The union of the graphs arising in the systematic enumeration is the language of graph grammar. Most also the graph elements in non-terminals and terminals are differentiated, and replaces only the non-terminals; under the language are understood then only the derived terminal graph.

Well-formedness of graph is often defined via containment within the language of a context-free graph grammar. A given graph can then use a Graphparser which calculates whether it is contained in the language of graph grammar are checked for well-formedness, in case of success also gives its derivative (s).

Graph rewriting systems can be viewed on their trees graphs (also) as a generalization of term rewriting systems (ground) terms /.

• 2.1 Application Examples
• 2.2 General Graph Rewriting Systems
• 2.3 builds on graph rewriting systems

Algebraic approach

Most important in the specification of graph rewriting systems, the algebraic approach has received, which was developed with the aim to generalize Chomsky grammars of words on graphs. Finding an instance. By determining a fretting - Graphhomomorphismus of in defining the replacement by the construction of a single or double pushouts

Graphs

Graphs in terms of algebraic approach are formally modeled as follows: a graph consists of two volumes and carrier, the corners and edges of the graph, and two figures, the set on which corners the edges begin and end. Often the corners and edges are labeled, the definition of the graph is then supplemented by two functions, map the corners and edges to appropriate symbols.

( So it is multi- graphs as diagrams graphically representable structure of nodes (vertices ) and directed edges ( arrows ) as they are used especially in computer science or similar to the formalization of data structures, processes. )

Graph homomorphisms

The semantics of the rewrite rules is explained with the help of graph homomorphisms, these are structure holding mappings between graphs. A graph homomorphism is a graph of such a graph from that a summary of nodes is only possible if the edges are aptly summarized. Formally thus consists of two functions such that:

Substitution

In the definition of replacing the approach of the construction of a simple push -outs (single pushout SPO ) of the construction of a double pushouts ( Double pushout, DPO) is distinguished.

And the relationship between the DPO is produced by an adhesive, and two graphs and Graphhomomorphismen. In the replacement step, the elements are retained, which are deleted from that of added.

In contrast, the relationship between SPO and by a partial Graphhomomorphismus is made. The replacement step remain enforced in relation elements obtained from unrelated will be deleted that are not related from be added.

When replacing two conflict cases can occur:

The rule application in the DPO is described by the construction of two pushouts, which is not possible in the two cases of conflict, so that the rule in these cases can not be applied.

The rule application in the SPO is described by the construction of pushouts, which causes in Case 1 deletion takes precedence over obtaining, and in the air hanging edges are deleted in the second case.

Alternative definitions

Other procedures within the algebraic approach provide the sesqui - pushout and pullback approach dar.

Less powerful, context-free formulations of graph rewriting (outside of the algebraic approach ), the node replacement and the hyperedges replacement. When the node substitution pattern consists only of a node replacement graph is connected based on connection instructions with, before the rule application to the instance of adjacent ( are adjacent ) nodes. In the hyperedges replacement, the pattern consists only of a hyper- edge replacement graph is glued to the, before the rule application at the instance of adjacent ( incident ) node.

Application of graph rewriting

While the graph theory in mathematics graphs and their properties ( such as dyeability ) is considered, and the graph theory in theoretical computer science (eg confluence) directed their attention to graph rewriting systems and their properties, is the provision of efficient graph rewriting systems for practical computer science in foreground, which are used in the context of applied computer science for modeling data in the form of graphs and the specification of computations on the graph by graph rewriting rules.

Graphs offer themselves as more vivid, mathematically precise and expressive formalism for modeling of related objects (entities ), the objects are encoded into nodes and relationships represented by edges. Different objects and relationships are expressed by different node and edge types, depending on the types of the graph elements may be beyond even attributed. Calculations are illustrated in this model by changing the relationships between the objects, but also the change in the attributes. They are described by graph rewriting rules.

In practice, over the indeterministic concept of the pure graph rewriting system is stronger, algorithmischere control of rule application, the indeterminism of the rule (which rule from the rule set is used ) and the indeterminism of the place ( where in the working graph, the rule is applied? ) is restricted. It can control constructs such as sequence, alternative, iteration or the next rule to be applied can be determined ( depending on success or failure of the previous rule application ), or editing a common approach to be ensured by parameter passing between the rules. It is then spoken of " Programmed graph rewriting ".

Graphs are in the form of verzeigerten structures (objects = node = directed edges references / pointers ) implicitly be found in every major program. Are objects, in particular patterns of interconnected objects to search and replace is a make explicit through the use of graph rewriting system rewarding; it can then be used with short, declarative graph rewriting rules, instead of large, hand- programmed search and replace subroutines.

Graph rewriting systems set the focus on the pattern-based processing of graphs in main memory, as opposed to graph databases that are developed with the goal of persistent storage in transaction-safe multi-user operation.

Application Examples

• Compiler: Optimizations on graph -based intermediate code, for example with GrGen / Firm
• Biology, Graphics: Design and implementation of a graph grammar based language for functional -structural plant modeling (PDF, 13.5 MB)
• Product development, product configuration, Systems Engineering: Production graphene-based product architectures, for example with booggie

General graph rewriting systems

• GrGen.NET
• Progres
• AGG

Building on graph rewriting systems

• Triple graph grammar ( model transformation )
• Fujaba ( Visual Programming, model transformation )
• Viatra 2 ( model transformation )