Title of paper: On Competence in Cooperating Distributed Grammar Systems

Abstract

We introduce a very natural cooperation protocol for cooperating distributed (CD) grammar systems with context-free components. Under this protocol, the components of a CD grammar systems are enabled (and disabled) to rewrite the sentential form according to their level of competence on that sentential form and must continue the derivation as long as they have this property. Intuitively, a component is k-competent on a sentential form if it is able to rewrite exactly k (no more and no less) nonterminals appearing in the sentential form. Since CD grammar systems are a language-theoretic framework for modelling blackboard systems, we thus provide a formal interpretation of the requirement that agents must be competent enough before being able to participate in the problem solving taking place on a blackboard. We show that this cooperation protocol is very powerful. CD grammar systems with 1-competent components can generate all forbidding random context grammars, while already 2-competent components suffice to generate all recursively enumerable languages. By applying the cooperation protocol to a specific type of CD grammar system we shed new light on a longstanding open problem in formal language theory: Is the inclusion of the family of recurrent programmed grammars with appearance checking into the family of programmed grammars with appearance checking strict?