Нашли опечатку? Выделите ее мышкой и нажмите Ctrl+Enter
Название: The mathematical theory of L systems
Авторы: Rozenberg G., Salomaa A.
Formal language theory is by its very essence an interdisciplinary area of science: the need for a formal grammatical or machine description of specific languages arises in various scientific disciplines. Therefore, influences from outside the mathematical theory itself have often enriched the theory of formal languages.
Perhaps the most prominent example of such an outside stimulation is provided by the theory of L systems. L systems were originated by Aristid Lindenmayer in connection with biological considerations in 1968. Two main novel features brought about by the theory of L systems from its very beginning are (i)parallelism in the rewriting process-due originally to the fact that languages were applied to model biological development in which parts of the developing organism change simultaneously, and (ii) the notion of a grammar conceived as a description of a dynamic process (taking place in time), rather than a static one. The latter feature initiated an intensive study of sequences (in contrast to sets) of words, as well as of grammars without nonterminal letters. The results obtained in the very vigorous initial period-up to 1974-were covered in the monograph "Developmental Systems and Languages" by G. Herman and G. Rozenberg (North-Holland, 1975).
Since this initial period, research in the area of L systems has continued to be very active. Indeed, the theory of L systems constitutes today a considerable body of mathematical knowledge. The purpose of this monograph is to present in a systematic way the essentials of the mathematical theory of L systems. The material common to the present monograph and that of Herman and Rozenberg quoted above consists only of a few basic notions and results. This is an indication of the dynamic growth in this research area, as well as of the fact that the present monograph focuses attention on systems without interactions, i.e., context-independent rewriting.
The organization of this book corresponds to the systematic and mathematically very natural structure behind L systems: the main part of the book (the first five chapters) deals with one or several iterated morphisms and one or several iterated finite substitutions. The last chapter, written in an overview style, gives a brief survey of the most important areas within L systems not directly falling within the basic framework discussed in detail in the first five chapters.
Today, L systems constitute a theory rich in original results and novel techniques, and yet expressible within a very basic mathematical framework. It has not only enriched the theory of formal languages but has also been able to put the latter theory in a totally new perspective. This is a point we especially hope to convince the reader of. It is our firm opinion that nowadays a formal language theory course that does not present L systems misses some of the very essential points in the area. Indeed, a course in formal language theory can be based on the mathematical framework presented in this book because the traditional areas of the theory, such as context-free languages, have their natural counterparts within this framework. On the other hand, there is no way of presenting iterated morphisms or parallel rewriting in a natural way within the framework of sequential rewriting.
No previous knowledge of the subject is required on the part of the reader, and the book is largely self-contained. However, familiarity with the basics of automata and formal language theory will be helpful. The results needed from these areas will be summarized in the introduction. Our level of presentation corresponds to that of graduate or advanced undergraduate work.
Although the book is intended primarily for computer scientists and mathematicians, students and researchers in other areas applying formal language theory should find it useful. In particular, theoretical biologists should find it interesting because a number of the basic notions were originally based on ideas in developmental biology or can be interpreted in terms of developmental biology. However, more detailed discussion of the biological aspects lies outside the scope of this book. The interested reader will find some references in connection with the bibliographical remarks in this book.
The discussion of the four areas within the basic framework studied in this book (single or several iterated morphisms or finite substitutions) builds up the theory starting from the simple and proceeding to more complicated objects. However, the material is organized in such a way that each of the four areas can also be studied independently of the others, with the possible exception of a few results needed in some proofs. In particular. a mathematically minded reader might find the study of single iterated morphisms (Chapters 1 and 111) a very interesting topic in its own right. It is an area where very intriguing and mathematically significant problems can be stated briefly ab ova.
Exercises form an important part of the book. Many of them survey topics not included in the text itself. Because some exercises are rather difficult, the reader may wish to consult the reference works cited. Many open research problems are also mentioned throughout the text. Finally, the book contains references to the existing literature both at the end and scattered elsewhere. These references are intended to aid the reader rather than to credit each result to some specific author(s).
Read more at http://ebookee.org/Grzegorz-Rozenberg-The-Mathematical-Theory-of-L-Systems_622209.html#Uxf6QhFklpuBFloE.99