Sequential Versus Parallel Grammar Formalisms with Respect to Measures of Descriptional Complexity

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

Abstrakty

EN

For tabled Lindenmayer systems and their languages, the degree of synchronization and the degree of nondeterminism are well investigated measures of descriptional complexity. In this paper the sequential counterparts of tabled Lindenmayer systems, namely cooperating distributed grammar systems and their pure variant (working in the so-called t-mode of derivation) are treated with respect to these complexity measures. In the pure case, where no distinction between terminal and nonterminal symbols is made, the sequential mechanisms are compared with the parallel ones, investigating whether one mechanism may have a better descriptional complexity than the other one when the same language is described.

Słowa kluczowe

EN

grammar system; tabled Lindenmayer system; degree of nondeterminism; degree of synchronization

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 55, nr 3,4
• Strony: 243--254
• Opis fizyczny: bibliogr. 11 poz.

Twórcy

autor

Aydin S.

autor

Bordihn H.

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

Bibliografia

• [1] Bordihn, H., Csuhaj-Varj´u, E., Dassow, J.: CD grammar 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., Reichel, B.: On descriptions of context-free languages by CD grammar systems, Journal of Automata, Languages and Combinatorics, 7(4), 2002, 447-454.
• [3] Csuhaj-Varju, E., Dassow, J.: On cooperating/distributed grammar systems, Journal of Information Processing and Cybernetics EIK, 26, 1990, 49-63.
• [4] Csuhaj-Varju, E., Dassow, J., Kelemen J., Pӑun, Gh.: Grammar Systems. A Grammatical Approach to Distribution and Cooperation, Gordon and Breach, London, 1994.
• [5] Dassow, J., Pӑun, Gh.: Regulated Rewriting in Formal Language Theory, Springer-Verlag, Berlin, 1989.
• [6] Dassow, J., Watjen, D.: On the relations between the degree of synchronization and the degree of nondeterminism in -limited and uniformly -limited T0L systems, International Journal of Computer Mathematics, 35, 1990, 69-82.
• [7] Ehrenfeucht, A., Rozenberg, G.: On basic properties of D0S systems and languages, Information and Control, 47, 1980, 137-153.
• [8] Gruska, J.: Descriptional complexity of context-free languages, Proc. 2nd Mathematical Foundations of Computer Science, High Tatras, 1973, 71-83.
• [9] Pӑun, Gh., Dassow, J., Skalla, S.: On the size of components of cooperating grammar systems, in: Results and Trends in Theoretical Computer Science (J. Karhumaki, H. Maurer, G. Rozenberg, Eds.), LNCS 812, Springer Verlag, Berlin, 1994, 325-343.
• [10] Rozenberg, G.: T0L systems and languages, Information and Control, 23, 1973, 357-381.
• [11] Rozenberg, G.: Extension of tabled 0L systems and languages, International Journal of Computer and Information Sciences, 2, 1973, 311-335.