Active Symbols in Pure Systems

Issue title: SPECIAL ISSUE ON DEVELOPMENTS IN GRAMMAR SYSTEMS

Article type: Research Article

Authors: Bensch, Suna | Bordihn, Henning

Affiliations: Universität Potsdam, Institut für Informatik, August-Bebel-Str. 89, 14482 Potsdam, Germany. E-mails: aydin@cs.uni-potsdam.de; henning@cs.uni-potsdam.de

Abstract: In this paper, we consider the number of (statically measured) active symbols for Lindenmayer systems without interaction and some variants thereof as well as for pure CD grammar systems, where no distinction between terminal and nonterminal symbols is made. This measure of descriptional complexity gives rise to infinite hierarchies in all cases considered here. Moreover, all the devices under consideration are compared with respect to their generative power when the number of active symbols is bounded. Finally, some closure and many non-closure properties of the corresponding language families with a fixed number of active symbols are proved.

Keywords: Active symbols, Lindenmayer systems, cooperating distributed grammar systems, pure CD grammar systems

Journal: Fundamenta Informaticae, vol. 76, no. 3, pp. 239-254, 2007