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

Article type: Research Article

Authors: Aydin, Suna | Bordihn, Henning

Affiliations: Universität Potsdam, Institut für Informatik, August-Bebel-Straße 89, 14482 Potsdam, Germany

Abstract: 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.

Keywords: grammar systems, tabled Lindenmayer systems, degree of nondeterminism, degree of synchronization

Journal: Fundamenta Informaticae, vol. 55, no. 3-4, pp. 243-254, 2003