Grammatical Picture Generation: A Tree-Based Approach (Texts in Theoretical Computer Science. An EATCS Series)

Picturesareimportant,ineverydaylifeaswellasinart,engineering,andmost branches of the natural and social sciences. About three decades ago, the - servation that simple geometric processes often yield very complex geometric objects (i.e., pictures) gave rise to new branches of mathematics whose p- pose was to study such processes and the resulting pictures: fractal geometry, dynamic systems, and chaos theory. More or less in parallel with this dev- opment, the increasing availability of computer desktop systems and other graphical output devices made computer scientists think about formal s- tems to describe sets of pictures. This led to the development of various types of picture-generating devices. This book is about such picture generators, - cluding some of the most basic devices studied in fractal geometry. In the computer science literature, the ?rst devices for picture generation wereproposedinthelate1960sandearly1970s,mostnotablythearraygr- mars of Rosenfeld, Siromoney, and others, and the shape grammars of Gips and Stiny. About a decade later, picture generators based on string grammars were proposed, using either the chain-code interpretation of Freeman or the turtle geometry known from theLogo programming language. Each of these lines of research has been continued ever since, and various other approaches have been proposed.