Leftmost Derivations in CD Grammar Systems
Henning Bordihn, György Vaszil · International Journal of Foundations of Computer Science · 2025
We investigate the power of CD grammar systems using different types of leftmost derivations for all standard cooperation strategies including the so-called full-competence mode of derivation. It is proved that, for some types of leftmost restrictions and cooperation strategies, CD grammar systems generate the same language classes as in the unrestricted, “non-leftmost” case, but the generative power is also increased or decreased in several cases. Thereby, some new relations to well-known Chomsky and Lindenmayer classes are presented.