STRING REWRITING

A 'string rewriting system' is a substitution system used to transform a given string according to specified rewriting rules.

Contents

Equivalence of basic string rewriting systems

Examples

See also

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\_0x\_1cdots\; x\_n$
ightarrow y_0y_1cdots 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\; )$
ightarrow 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, 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