String rewriting

A string rewriting system is a substitution system used to transform a given string according to specified rewriting rules. Examples of computational models based on deterministic string rewriting include Markov algorithms and tag systems. String rewriting is also the basis for Post canonical systems and a variety of formal grammars, and has been applied to the creation of certain types of fractals such as the Cantor set and Menger sponge.

See also

• Formal grammar
• L-system
• Markov algorithm
• Semi-Thue system
• Tag system