THE MATHEMATICAL THEORY OF L SYSTEMS

THE MATHEMATICAL THEORY OF L SYSTEMS

July 1974 | G. Rozenberg, A. Salomaa
The paper provides a comprehensive survey of the mathematical theory of L systems, which originated from the work of Lindenmayer. L systems are used to model the development of simple filamentous organisms and have evolved into a branch of formal language theory. The authors discuss various aspects of L systems, including their language-generating capabilities, structural constraints, and sequence generation. Key topics covered include: 1. **L Schemes and L Systems**: Definitions and examples of basic L systems, including TIL, IL, T0L, and 0L systems. 2. **Squeezing Languages Out of L Systems**: Various methods to define languages from L systems, such as exhaustive and selective approaches, using nonterminals, codings, and fragmentation. 3. **Comparing Language Generating Power**: Analysis of the language-generating power of different L system classes, including comparisons with context-free and type-0 grammars. 4. **Fitting L Languages into Formal Language Theoretic Frameworks**: Comparing L systems with classical Chomsky hierarchies and exploring closure properties. 5. **Structural Constraints on L Systems**: Results on the impact of restrictions on L systems, such as the role of erasing productions and the need for "two-sided context" in IL systems. 6. **Squeezing Sequences Out of L Systems**: Investigation of sequences generated by L systems, including DIL and D0L systems. 7. **Growth Functions**: Definitions, basic problems, and classification of growth types for D0L, D1L, and DIL systems. The paper also discusses the decidability of growth equivalence and synthesis problems for these systems. The authors conclude by highlighting the rapid development in the area and the importance of L systems in understanding the mathematical foundations of developmental biology and formal language theory.The paper provides a comprehensive survey of the mathematical theory of L systems, which originated from the work of Lindenmayer. L systems are used to model the development of simple filamentous organisms and have evolved into a branch of formal language theory. The authors discuss various aspects of L systems, including their language-generating capabilities, structural constraints, and sequence generation. Key topics covered include: 1. **L Schemes and L Systems**: Definitions and examples of basic L systems, including TIL, IL, T0L, and 0L systems. 2. **Squeezing Languages Out of L Systems**: Various methods to define languages from L systems, such as exhaustive and selective approaches, using nonterminals, codings, and fragmentation. 3. **Comparing Language Generating Power**: Analysis of the language-generating power of different L system classes, including comparisons with context-free and type-0 grammars. 4. **Fitting L Languages into Formal Language Theoretic Frameworks**: Comparing L systems with classical Chomsky hierarchies and exploring closure properties. 5. **Structural Constraints on L Systems**: Results on the impact of restrictions on L systems, such as the role of erasing productions and the need for "two-sided context" in IL systems. 6. **Squeezing Sequences Out of L Systems**: Investigation of sequences generated by L systems, including DIL and D0L systems. 7. **Growth Functions**: Definitions, basic problems, and classification of growth types for D0L, D1L, and DIL systems. The paper also discusses the decidability of growth equivalence and synthesis problems for these systems. The authors conclude by highlighting the rapid development in the area and the importance of L systems in understanding the mathematical foundations of developmental biology and formal language theory.
Reach us at info@study.space
[slides] The mathematical theory of L systems | StudySpace