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

Abstract

Cooperating distributed (CD) grammar systems are grammatical models for the blackboard model of problem solving. In this paper we consider three very natural cooperation protocols for these constructions, introduced in [BCHV02a] and [BCHV02b], in the context of CD grammar systems with E0L components, that is, context-free grammars working with a variant of totally parallel derivations. An E0L grammar represents a problem solver which is able perfom several (as many as possible) actions in one step. According to the examined cooperation protocols, a component of the CD grammar system is enabled to rewrite a sentential form only if it is <=k-competent, =k-competent, or >=k-competent, respectively, on that sentential form and must continue the derivation as long as it has this property. 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. Similarly to the results for context-free CD grammar systems, we obtain that the above cooperation protocols are very powerful in the case of CD grammar systems with E0L component as well, since the grammar systems working in any of the the <=2-competence, the =2-competence mode, or the >=2-competence mode of derivation characterize the family of languages generated by random context ET0L systems, a very large, parallel class of languages.


[BCHV02a] 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.

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