Title of paper: On Competence in Cooperating Distributed Grammar Systems, part II

Abstract

In this paper we continue the investigations of the power of context-free cooperating distributed (CD) grammar systems cooperating under competence-based cooperation protocols. As natural extensions of the =k-competence mode of derivation for CD grammar systems, we introduced in [BCHV02], we have introduced the <=k-competence mode of derivation and the >=k-competence mode of derivation. A component grammar is said to be k-competent on a sentential form if it is able to rewrite exactly k nonterminals appearing in the sentential form. According to the examined protocols, a component of a CD grammar system is enabled to rewrite a sentential form only if it is <=k-competent or >=k-competent, respectively, on that sentential form and it must continue the derivation as long as it has this property. Both cooperation protocols are very powerful, since CD grammar systems working in the <=2-competence mode of derivation characterize the family of languages generated by random context grammars, while CD grammar systems working in the >=2-competence mode of derivation characterize the family of languages generated by random context ET0L systems. Since CD grammar systems are syntactic models of the blackboard model for problem solving, the results demonstrate that effective problem solving is possible even with cooperating partners of a very low, limited level of competence.


[BCHV02] M.H. ter Beek, E. Csuhaj-Varjú, M. Holzer, and Gy. Vaszil, On Competence in Cooperating Distributed Grammar Systems. Technical Report 2002/1, Research Group on Modelling Multi-Agent Systems, Computer and Automation Research Institute, Hungarian Academy of Sciences, 2002.