String rewriting

From Free net encyclopedia

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, Post canonical systems (e.g., tag systems), a variety of formal grammars, and L-systems (the latter lending themselves well 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