Rewriting systems can be used to generate pictures in two different ways. In the first case, a rewriting system operates directly on two-dimensional objects, such as arrays [Kirsch 1964, Dacey 1970], graphs [Rosenfeld and Milgram 1972, Efate 1972], or "shapes'. [Gips 1975, Stiny 1975]. In the second case, a string grammar (in the broad sense of the word, including parallel rewriting systems) is used to define strings of symbols. A graphic interpretation function subsequently maps these strings into pictures. This paper is devoted to this second approach. After the idea of applying string grammars to pictures is put into a historic perspective in Section 2, attention is focused on L-systems. The necessary definitions related to L-systems are collected in Section 3. Sections 4 and 5 concentrate on pictures generated by OL-systems under two particular interpretations, the chain-code and the turtle interpretation, respectively. Examples of pictures are given and the classes of pictures generated under both interpretations are compared. Two approaches for extending the gamut of generated pictures are discussed in Sections 6 and 7. The first approach relies on extending the generative power of L-systems beyond that of OL-systems. The second approach employs more sophisticated interpretation functions. Section 8 presents some open problems.
Download PDF here (3.3 Mb).