A COMPARISON OF THE DESCRIPTIONAL COMPLEXITY OF CLASSES OF LIMITED LINDENMAYER SYSTEMS: PART I

摘要

We investigate the descriptional complexity of limited Lindenmayer systems and theirndeterministic and tabled variants with respect to the number of rules and the number ofnsymbols. In this part, we confine ourselves to propagating limited Lindenmayer systems.nWe determine the decrease of complexity when the generative capacity is increased. Fornincomparable families, we give languages that can be described more efficiently in eithernof these families than in the other.