Rewriting Systems

Подпись: von Koch curveThe general mechanism of a rewriting system can best be illustrated with the so-called snowflake curve or von Koch curve. This curve is actually the classic example of a rewriting system, and, therefore, it is found in many places in the computer science literature. Rewriting takes place graphically: each edge of a given geometry is replaced by a sequence of edges. The rewriting method is implemented using a so-called generator (see Fig. 5.1a). The successive appli­cation of generators on the edges of the initial object, the initiator, results in a complex figure, which resembles here the outline of a snowflake.

Figure 5.1

Graphical production of the von Koch curve: (a) generator; (b) initiator; (c) illustrations after 1, 2, 3 and 7 rewritings


(a) (b)


Rewriting SystemsRewriting Systems

As already mentioned, graphical rewriting is just one option for the definition of a rewriting system. There are a number of different methods used for various purposes:

■ Graphs

Here edges and nodes of a graph are replaced by subgraphs (see [27]). The original graph is in this way enlarged step by step. The underlying mechanism uses grammars that specify the rewriting rules. In Sect. 5.13 a similar method is outlined that works, however, with textual rules.

■ Cell Grids

Values or value combinations in a cell are replaced with other values. An example is “The Game of Life” (see [70, 71]), which produces complex spatial patterns using simple rules (see also Sect. 4.1). Similar mechanisms are used for the modeling of plant populations and other processes [116].

■ Text

In the already mentioned L-systems, characters in a text are replaced. The mechanism was introduced by Thue (see [185]). Chomsky [26], a linguist, compiled a concept for the description of languages using so-called formal grammars with alphabets, axioms and productions, which incidentally is also the basis for the Lindenmayer systems.