String rewriting

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.

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

$x_{0}x_{1}\cdots x_{n}\rightarrow y_{0}y_{1}\cdots y_{m},\quad x_{i},y_{i}\in A$

indicating that any substring x₀x₁...x_n is to be replaced with y₀y₁...y_m.

We can reformulate such a system into a term rewriting system -- the transformation rules now become

$x_{0}(x_{1}(\cdots (x_{n}(x)))\cdots )\rightarrow y_{0}(y_{1}(\cdots (y_{m}(x))\cdots ),$

where each x_i and y_i constitute the function symbols in the term rewriting system.

Strings in this term rewriting systems are then ground terms.

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).

Example of an online automatically content rewrite engine [1]. This free rewrite software rewrites your string, text, articles and other content types easily. It uses similar techniques as described above. Pleas use it as experiment/inspiration/non-commercial.

See also

• Formal grammar
• L-system
• Markov algorithm
• Semi-Thue system
• Post canonical system