No Access

ON THE NUMBER OF ACTIVE SYMBOLS IN LINDENMAYER SYSTEMS

JÜRGEN DASSOW

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

Search for more papers by this author

and

GYÖRGY VASZIL

Computer and Automation Institute, Hungarian Academy of Sciences, Kende u. 13–17, H-1111 Budapest, Hungary

Search for more papers by this author

https://doi.org/10.1142/S0129054111007976Cited by:2 (Source: Crossref)

Abstract

A symbol a is called active in an L system G if there is a rule a → υ with a ≠ υ in some table of G. By Ac_X(L) we denote the number of active symbols necessary to generate L by L systems of type X. For two types X and Y of L systems such that the corresponding languages families and satisfy , we say that Y is more efficient than X, if there is a sequence of languages , n ≥ 1, such that Ac_X(L_n) ≥ n and Ac_Y(L_n) ≤ k for some constant k. In this paper we shall show that the inclusion implies that Y is more efficient than X. Analogous results are presented for some modifications of the measure of active symbols.

Keywords:

AMSC: 22E46, 53C35, 57S20

References

S. Bensch and H. Bordihn, Fundamenta Informaticae 76, 239 (2007). Web of Science, Google Scholar
H. Bordihn and M. Holzer, Journal of Automata, Languages and Combinatorics 6, 411 (2001). Google Scholar
W. Bucheret al., Theor. Comp. Sci. 14, 227 (1981), DOI: 10.1016/0304-3975(81)90044-X. Crossref, Web of Science, Google Scholar
J. Dassow, Intern. J. Foundations Comp. Sci. 15, 663 (2004). Link, Web of Science, Google Scholar
J. Dassow, On the descriptional complexity of Lindenmayer systems, in Pre-Proceedings of 6th International Workshop on Formal Systems, eds. L. Lucian, H. Jürgensen and D. Wotschke, University of Western Ontario, Report No. 619, pp. 28–36 . Google Scholar
J. Dassow, T. Nishida and B. Reichel, Developments in Language Theory, Lecture Notes in Computer Science 2450, eds. M. Ito and M. Toyama (Springer, Berlin, 2003) pp. 128–139. Crossref, Google Scholar
J. Dassow and Gh. Păun , Regulated Rewriting in Formal Language Theory ( Springer , Berlin , 1989 ) . Crossref, Google Scholar
H. Fernau, Machines, Computations, and Universality, Lecture Notes in Computer Science 2076, eds. M. Margenstern and Y. Rogozhin (Springer, Berlin, 2001) pp. 202–213. Crossref, Google Scholar
J. Gruska, Mathematical Foundations of Computer Science 1976, Lecture Notes in Computer Science 45, ed. A. Mazurkiewicz (Springer, Berlin, 1976) pp. 65–80. Crossref, Google Scholar
K. Hashiguchi, Internat. Colloquium Automata, Languages and Programming, Lecture Notes in Computer Science 510, eds. L. Albert, B. Monien and B. Rodriguez-Artelejo (Springer, Berlin, 1991) pp. 641–648. 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 pp. 239–258. Google Scholar
J. Kleijn and G. Rozenberg, Inform. Control 44, 134 (1980). Crossref, Google Scholar
T. Masopust and A. Meduna, Fundamenta Informaticae 87, 407 (2008). Web of Science, Google Scholar
A. Meduna, Intern. J. Comp. Math. 69, 57 (1998), DOI: 10.1080/00207169808804709. Crossref, Web of Science, Google Scholar
G. Rozenberg and A. Salomaa , The Mathematical Theory of L Systems ( Academic Press , New York , 1980 ) . 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