On the Number of Active Symbols in L and CD Grammar Systems
Henning Bordihn, Markus Holzer · Journal of automata, languages and combinatorics · 2001
The number of active symbols known as a measure of descriptional complexity for ET0L systems is revisited. It is known that at least two but at most three active symbols per table are sufficient to generate every ET0L language. In this paper, we first prove that the results for ET0L systems carry over to the special case of deterministic ET0L systems (EDT0L systems). Then we consider this concept of active symbols in the framework of cooperating distributed (CD) grammar systems working in $t$-mode of derivation, the sequential counterpart to ET0L systems. Although ET0L and these CD grammar systems generate the same family of languages, we show that the hierarchies with respect to the number of active symbols collapse to different levels: only one active symbol per grammar component is sufficient in the sequential case. Furthermore, we introduce a dynamic variant of activity of symbols. Also in that dynamic interpretation the corresponding hierarchies for ET0L and CD grammar systems collapse. There we find that one dynamically measured active symbolis sufficient in both cases. Moreover, all our results carry over to deterministic systems, as well. Finally, ET0L systems with random context and their deterministic variant are considered, too.