Active Symbols in Pure Systems

• Autorzy: Bensch S. , Bordihn H.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

active symbol; Lindenmayer systems; cooperating distributed grammar systems; pure CD grammar systems

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 76, nr 3
• Strony: 239--254
• Opis fizyczny: bibliogr. 15 poz.

Twórcy

autor

Bensch S.

autor

Bordihn H.

• Universität Potsdam, Institut für Informatik, August-Bebel-Strasse 89, 14482 Potsdam, Germany,

Bibliografia

• [1] Bordihn, H., Csuhaj-Varjú, E., Dassow, J.: CD grammars systems versus L systems, in: Grammatical Models of Multi-Agent Systems (Gh. P˘aun, A. Salomaa, Eds. ), Gordon and Breach Publishers, 1999, 18-32.
• [2] Bordihn, H., Holzer, M.: On the number of active symbols in L and CD grammar systems, Journal of Automata, Languages and Combinatorics, 6, 2001, 411-426.
• [3] Csuhaj-Varjú, E., Dassow, J.: On cooperating/distributed grammar systems, Journal of Information Processing and Cybernetics (EIK), 26, 1990, 49-63.
• [4] Csuhaj-Varjú, E., Dassow, J., Kelemen, J., P˘aun, Gh.: Grammar Systems. A Grammatical Approach to Distribution and Cooperation, Gordon and Breach, London, 1994.
• [5] Dassow, J.: L(ET0L[6]) = L(ET0L), unpublished note, 1981.
• [6] Dassow, J., Pǎun, Gh.: Regulated Rewriting in Formal Language Theory, Akademie-Verlag, Berlin, 1989.
• [7] Kari, L., Rozenberg, G., Salomaa, A.: L systems, Handbook of Formal Languages, Vol. 1 (G. Rozenberg, A. Salomaa, Eds.), Springer-Verlag, 1997, 253-328.
• [8] Kleijn, H. C. M., Rozenberg, G.: A study in parallel rewriting systems, Information and Control, 44, 1980, 134-163.
• [9] Nielson, M., Rozenberg, G., Salomaa, A., Skyum, S.: Nonterminals, homomorphisms and codings in different variations of 0L systems, ii. nondeterministic systems, Acta Informatica, 3, 1974, 357-364.
• [10] Pǎun, Gh., Dassow, J.: L(ET0L[5]) = L(ET0L), Elektronische Informationsverarbeitung und Kybernetik (J. Inf. Process. Cybern. EIK), 18, 1982, 345-348.
• [11] Rozenberg, G.: T0L systems and languages, Information and Control, 23, 1973, 357-381.
• [12] Rozenberg, G., Lee, K. P.: Development systems with finite axiom sets, part 1: Systems without interactions, Intern. J. Computer Math., 4, 1974, 43-68.
• [13] Rozenberg, G., Salomaa, A.: The Mathematical Theory of L Systems, Academic Press, New York, 1980.
• [14] Yokomori, T., Wood, D., Lange, K.-J.: A three-restricted normal form for ET0L languages, Information Processing Letters, 14, 1982, 97-100.
• [15] Yokomori, T., Wood, D., Lange, K.-J.: Erratum at a three-restricted normal form for ET0L languages, Information Processing Letters, 21, 1985, 53.