String rewriting
From Wikipedia, the free encyclopedia
A string rewriting system is a substitution system — a special type of Post canonical system — used to transform a given string according to specified rewriting rules.
[edit] Equivalence of basic string rewriting systems
Certain basic forms of string rewriting systems are essentially equivalent to term rewriting systems. Suppose we have strings over some alphabet A, and we are only given a list of transformation rules on substrings of the form
indicating that any substring x0x1...xn is to be replaced with y0y1...ym.
We can reformulate such a system into a term rewriting system -- the transformation rules now become
where each xi and yi constitute the function symbols in the term rewriting system.
Strings in this term rewriting systems are then ground terms.
[edit] Examples
Examples of computational models based on deterministic string rewriting include Markov algorithms, 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).
