Graph rewriting

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, graph transformation, or graph rewriting, concerns the technique of creating a new <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graph</a> out of an original graph algorithmically. It has numerous applications, ranging from <a href="/facts/Software_engineering/KX6cE9kz">software engineering</a> (<a href="/facts/Software_construction/Y55GsClm">software construction</a> and also <a href="/facts/Formal_verification/BYD4GnJR">software verification</a>) to <a href="/facts/Layout_algorithm/CWAwEwXW">layout algorithms</a> and picture generation.
Graph transformations can be used as a computation abstraction. The basic idea is that if 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.
Formally, a graph <a href="/facts/Rewriting/9PHlnnnJ">rewriting</a> system usually consists of a set of graph rewrite rules of the form 
 
 
 
 L
 →
 R
 
 
 {\displaystyle L\rightarrow R}
 
, with 
 
 
 
 L
 
 
 {\displaystyle L}
 
 being called pattern graph (or left-hand side) and 
 
 
 
 R
 
 
 {\displaystyle R}
 
 being called replacement graph (or right-hand side of the rule). A graph rewrite rule is applied to the host graph by searching for an occurrence of the pattern graph (<a href="/facts/Pattern_matching/CEwptMs9">pattern matching</a>, thus solving the <a href="/facts/Subgraph_isomorphism_problem/86LLWRg4">subgraph isomorphism problem</a>) and by replacing the found occurrence by an instance of the replacement graph. Rewrite rules can be further regulated in the case of <a href="/facts/Labeled_graph/ux5jKRD7">labeled graphs</a>, such as in string-regulated graph grammars.
Sometimes graph grammar is used as a synonym for graph rewriting system, especially in the context of <a href="/facts/Formal_language/crDTyP8q">formal languages</a>; the different wording is used to emphasize the goal of constructions, like the enumeration of all graphs from some starting graph, i.e. the generation of a graph language – instead of simply transforming a given state (host graph) into a new state.

Graph rewriting open-in-new

Graph rewriting