No Access

ON THE DESCRIPTIONAL COMPLEXITY OF LINDENMAYER SYSTEMS

JÜRGEN DASSOW

Otto-von-Guericke-Universiät Magdeburg, Fakultät für Informatik, PSF 4120, D-39016 Magdeburg, Germany

https://doi.org/10.1142/S0129054104002674Cited by:5 (Source: Crossref)

Abstract

We define the number of productions and the number of symbols as measures of descriptional complexity for tabled interactionless Lindenmayer systems and their special cases. We investigate the decrease of the descriptional complexities if we go from a family to another one which has a larger generative capacity.

Keywords:

References

H. Bordihn and J. Dassow, Developments in Language Theory, A note on the degree of nondeterminism, eds. G. Rozenberg and A. Salomaa (World Scientific, Singapore, 1994) pp. 70–79. Google Scholar
J. Dassow, T. Nishida and B. Reichel, Developments in Language Theory, On the descriptional complexity of some variants of Lindenmayer systems, eds. M. Ito and M. Toyoma (Springer-Verlag, Berlin, 2003) pp. 128–139. Crossref, Google Scholar
J. Dassow, Gh. Păun and A. Salomaa, Handbook of Formal Languages, Grammars with controlled derivations II, eds. G. Rozenberg and A. Salomaa (Springer-Verlag, Berlin, 1997) pp. 101–154. Crossref, Google Scholar
J. Gruska, Mathematical Foundations of Computer Science 1976, Descriptional Complexity (of languages) – a short survey, ed. A. Mazurkiewicz (Springer-Verlag, Berlin, 1976) pp. 65–80. Crossref, Google Scholar
G. T. Herman and G. Rozenberg , Developmental Systems and Languages ( North-Holland , Amsterdam , 1974 ) . Google Scholar
A. Kelemenova, Grammatical complexity of context free languages and normal forms of context free grammars, Proc. Second Czechoslovak-Soviet Conference of Young Computer Scientists, ed. P. Mikulecky (Bratislava, 1982) pp. 239–258. Google Scholar
A. Kelemenova and M. Removcikova, AOL and CFG-size of languages, in [12], pp. 177–182 . Google Scholar
J. Kleijn and G. Rozenberg, Inform. Control 44, 134 (1980), DOI: 10.1016/S0019-9958(80)90066-2. Crossref, Google Scholar
A. Meduna, Intern. J. Comp. Math. 69, 57 (1998), DOI: 10.1080/00207169808804709. Crossref, Web of Science, Google Scholar
T. Y. Nishida, J. Automata, Languages and Combinatorics 6, 507 (2001). Web of Science, Google Scholar
G. Rozenberg and A. Salomaa , The Mathematical Theory of L Systems ( Academic Press , New York , 1980 ) . Google Scholar
G. Rozenberg and A. Salomaa (eds.) , Lindenmayer Systems ( Springer-Verlag , Berlin , 1992 ) . Crossref, Google Scholar
T. Yokomori, D. Wood and K.-J. Lange, Inform. Proc. Letters 14, 97 (1982), DOI: 10.1016/0020-0190(82)90061-8. Crossref, Web of Science, Google Scholar