Some New Modes of Competence-Based Derivations in CD Grammar Systems

摘要

We introduce some new cooperation protocols for cooperating distributed (CD) grammar systems. They depend on the number of different nonterminals present in the sentential form if a component has finished its work, i.e. on the final competence or efficiency of the grammar on the string (the competence is large if the number of the different nonterminals is small). We prove that if the underlying derivation mode is the t-mode derivation, then some variants of these systems determine the class of random context ETOL languages. If these CD grammar systems use the k step limited derivations (for k ≥ 3) as underlying derivations, they are able to generate any recursively enumerable language.