Title of paper: Cooperating Distributed Grammar Systems: Components with Nonincreasing Competence

Abstract

We study the generative power of CD grammar systems (CDGSs) that use a cooperation protocol based on the level of competence on a sentential form - and the competence of their components does not increase during rewriting. A component of a CDGS is k-competent on a sentential form if it can rewrite exactly k different nonterminals appearing in that string. A CDGS with components that are nonincreasing in competence works in  =k-competence mode of derivation if no  k-competent component can ever become  l-competent, for some l > k. We introduce a static and a dynamic definition to impose this restriction, and we relate the generative power of such CDGSs working either in a sequential or in a parallel manner and according to the aforementioned cooperation protocol, for various k, with that of context-free forbidding random context grammars, (random context) ET0L systems, and context-free programmed grammars with appearance checking.