Usually, a Ph.D. Thesis reports on some scientific results, and, after it has accomplished its purpose of being a catalyst in the transformation of its author to a Ph.D., it is carved up into one or more pieces which are presented to the scientific community in media with a wider circulation. Here, I have followed the converse course. This work wants to present a unified treatment of research, done by its author, most of which has been published previously in reports, journals and conference proceedings. Where it was necessary to my purpose I have drawn from the work of other investigators. A bibliographical comment accompanies each chapter, disclosing its sources. Whereas it has not been my contention to give a complete account of the mathematical theory of L systems, part of the field seems reasonably covered. The treatment of the subject is self-contained and, hopefully, easy to follow, but it is obvious that a rudimentary knowledge of formal language theory is more or less required from the reader.
Author(s): Paul M.B. Vitányi
Publisher: Mathematisch Centrum
Year: 1978
Language: English
Pages: 228
City: Amsterdam
Cover ......Page 1
Preface ......Page 7
Table of contents ......Page 9
Chapter 1. Introduction ......Page 11
2.1. Formal grammars ......Page 17
2.2. Lindenmayer systems ......Page 20
2.3. Bibliographical comments ......Page 23
Chapter 3. L Systems, sequences, and languages ......Page 25
3.1.1. DOL languages ......Page 26
3.1.1.1. Functions which relate size of language with size of alphabet ......Page 34
3.1.1.2. Asymptotic approximations of S and P ......Page 39
3.1.1.3. Classification and closure properties ......Page 43
3.1.2. Structure of DOL systems with applications to growth functions, local catenativeness, and characterizations ......Page 44
3.1.2.1. Growth functions ......Page 48
3.1.2.2. The locally catenative property ......Page 55
3.1.2.3. Regularity and context freeness ......Page 61
3.1.2.4. Biological interpretation ......Page 62
3.2. Deterministic context sensitive Lindenmayer systems without tables ......Page 64
3.2.1. Lindenmayer systems and Turing machines ......Page 67
3.2.2. Nonrecursive L languages ......Page 69
3.2.3. Deterministic L languages and the Chomsky hierarchy ......Page 72
3.2.4. Extensions and homomorphic closures of deterministic L languages ......Page 75
3.2.5. Extensions and homomorphic closures of propagating deterministic L languages ......Page 87
3.2.6. Combining the results of Section 3.2 ......Page 96
3.3. Context sensitive table Lindenmayer systems and a trade-off equivalent to the LBA problem ......Page 102
3.4. Stable string languages of L systems ......Page 110
3.4.1. Stable string languages of L systems without tables ......Page 112
3.4.2. Stable string languages of table L systems ......Page 115
3.4.3. Stable string languages of deterministic table L systems ......Page 123
3.4.4. Relevance to theoretical biology and formal language theory ......Page 125
3.5. Context variable L systems and some simple regenerating structures ......Page 126
3.5.1. The extended French Flag problem ......Page 132
3.6. Bibliographical comments ......Page 136
Chapter 4. Growth functions ......Page 137
4.1. DOL growth functions: analytical approach ......Page 140
4.2. DOL growth functions: combinatorial approach ......Page 150
4.3. Growth functions of context sensitive L systems ......Page 154
4.3.1. Bounds on unbounded growth ......Page 156
4.3.2. Synthesis of context sensitive growth functions ......Page 160
4.3.3. The hierarchy ......Page 164
4.3.4. Decision problems ......Page 170
4.4. Bibliographical comments ......Page 176
Chapter 5. Physical time growth functions associated with Lindenmayer systems operating in physiological time ......Page 179
5.1. Sigmoidal growth functions of Lindenmayer systems operating in physiological time ......Page 184
5.2. Some possible extensions and an interpretation in terms of table L systems ......Page 192
5.3. Final remarks ......Page 194
5.4. Bibliographical comments ......Page 195
Chapter 6. Epilogue: Evaluation of results ......Page 197
Bibliography ......Page 205
Samenvatting ......Page 217
Stellingen ......Page 222
