Pictures are important, in everyday life as well as in art, engineering, and most branches of the natural and social sciences. About three decades ago, the observation that simple geometric processes often yield very complex geometric objects (i.e., pictures) gave rise to new branches of mathematics whose purpose was to study such processes and the resulting pictures: fractal geometry, dynamic systems, and chaos theory. More or less in parallel with this development, the increasing availability of computer desktop systems and other graphical output devices made computer scientists think about formal systems to describe sets of pictures. This led to the development of various types of picture-generating devices. This book is about such picture generators, including some of the most basic devices studied in fractal geometry. In the computer science literature, the first devices for picture generation were proposed in the late 1960s and early 1970s, most notably the array grammars 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 the Logo programming language. Each of these lines of research has been continued ever since, and various other approaches have been proposed. However, most books on formal mathematical aspects of picture generation are in fact books on fractal geometry and related areas written from a mathematical point of view. They present deep, interesting, and beautiful mathematics and can be recommended to anyone whose curiosity is spurred by reading the following chapters. Nevertheless, I felt that a text intended mainly for a theory-interested computer science readership ought to be written with a somewhat different focus. This book attempts to present some important types of picture generators in a unified framework that highlights their common algorithmic basis. The techniques used and the general spirit of the presentation have been greatly influenced by the theory of computation, and in particular the theory of formal languages. The text tries to illustrate all major concepts by means of examples and concentrates on theoretical questions regarding, for example, the generative power of the devices considered and their algorithmic properties. As the book is mathematical in character, it requires a certain familiarity with formal mathematical notions and techniques. It is directed towards readers who know and understand the basic notions of the theory of computation, corresponding to a standard course in an average computer science curriculum. In particular, this includes notions and techniques from the theory of formal languages, such as regular expressions, finite automata, right-linear and context-free grammars, derivations, and the use of pumping lemmas. Readers who appreciate these concepts will, hopefully, like this book as well. However, it is neither necessary nor assumed that the reader is a specialist in formal-language theory, picture generation, or any other field.Introduction Line-Drawing Languages Collage Languages Iterated Function Systems Grid Picture Languages Languages of Fractals Languages of Coloured Collages TREEBAG Introduction to Tree Languages
Чтобы скачать этот файл зарегистрируйтесь и/или войдите на сайт используя форму сверху.