Mathematical Theory of L Systems (eBook)

Front Cover 1
The Mathematical Theory of L Systems 4
Copyright Page 5
Contents 8
Preface 10
Acknowledgments 14
Lisr of Symbols 16
INTRODUCTION 18
CHAPTER I. SINGLE HOMOMORPHISMS ITERATED 27
1. Basics about D0L Systems 27
2. Basics about Locally Catenative Systems 37
3. Basics about Growth Functions 46
CHAPTER II. SINGLE FINITE SUBSTITUTIONS ITERATED 60
1. Basics about 0L and E0L Systems 60
2 . Nonterminals versus Codings 79
3. Other Language-Defining Mechanisms 87
4. Combinatorial Properties of E0L Languages 100
5. Decision Problems 115
6. E0L Forms 121
CHAPTER III. RETURNING TO SINGLE ITERATED HOMOMORPHISMS 138
1. Equality Languages and Elementary Homomorphisms 138
2. The Decidability of the D0L Equivalence Problems 151
3. Equality Languages and Fixed Point Languages 161
4. Growth Functions: Characterization and Synthesis 171
5. D0L Forms 193
CHAPTER IV. SEVERAL HOMOMORPHISMS ITERATED 205
1. Basics about DT0L and EDT0L Systems 205
2. The Structure of Derivations in EPDT0L Systems 209
3. Combinatorial Properties of EDT0L Languages 219
4. Subword Complexity of DTOL Languages 223
5 . Growth in DT0L Systems 231
CHAPTER V. SEVERAL FINITE SUBSTITUTIONS ITERATED 248
1. Basics about T0L and ET0L Systems 248
2. Combinatorial Properties of ET0L Languages 262
3. ET0L Systems of Finite Index 278
CHAPTER VI. OTHER TOPICS AN OVERVIEW 297
1. IL Systems 297
2. Iteration Grammars 309
3. Machine Models 317
4. Complexity Considerations 327
5. Multidimensional L Systems 333
HISTORICAL AND BIBLIOGRAPHICAL REMARKS 354
References 358
Index 366