Editing Graph rewriting (section)

{{Short description|Creating a new graph from an existing graph}}
In [[computer science]], '''graph transformation''', or '''graph rewriting''', concerns the technique of creating a new [[graph (discrete mathematics)|graph]] out of an original graph algorithmically. It has numerous applications, ranging from [[software engineering]] ([[software construction]] and also [[Formal verification|software verification]]) to [[layout algorithm]]s 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 [[rewriting]] system usually consists of a set of graph rewrite rules of the form <math>L \rightarrow R</math>, with <math>L</math> being called pattern graph (or left-hand side) and <math>R</math> 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 ([[pattern matching]], thus solving the [[subgraph isomorphism problem]]) and by replacing the found occurrence by an instance of the replacement graph. Rewrite rules can be further regulated in the case of [[labeled graph]]s, such as in string-regulated graph grammars.

Sometimes '''graph grammar''' is used as a synonym for ''graph rewriting system'', especially in the context of [[formal language]]s; 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.