Rewriting

This article is not detailed enough and needs to be expanded. Please help us by adding some more information.

Rewriting denotes a form of computation where a data structure is replaced by a modified form of itself, sometimes repeatedly. Prominent forms of rewriting include:

• String rewriting, where the data structure is a string of symbols. Examples are the languages Thue and ///, Post canonical systems, and regular expression substitution as found in several mainstream languages.
• Graph rewriting, where the data structure is a (usually labeled) graph of vertices with edges between them. This is frequently used as an implementation or formal semantics of languages, especially functional ones. Undirected graph rewriting is addressed in Eodermdrome.
• Tree rewriting, the frequent special case of graph rewriting where the graph is a tree, at least conceptually. In implementations, identical sub-trees may be identified for efficiency, so that the underlying structure is nevertheless a more general graph (directed, without cycles). Examples: Combinatory logic or Clean.