![Sample our Computer Science journals, sign in here to start your access, latest two full volumes FREE to you for 14 days]({"type":"image" , "src" : "/sda/5928/TOC-Subject-Sample-2021-Computer-Science.jpg"})
Abstract
In this paper we examine context-free cooperating distributed (CD) grammar systems where the cooperation protocol is based on the competence (capability) of the component grammars in rewriting. We study the power of a derivation mode where every component is allowed to start the generation only if it has a prescribed level of competence and it is allowed to finish the work if it is not competent anymore. The competence level of a component on a string is the number of different nonterminals in this word that can be rewritten by the production set of the grammar. We show that if the prescribed level of competence of the grammar to start the derivation is equal to k or is at least k, for some natural number k ≥ 2, then these CD grammar systems are as powerful as the ET0L systems with random context conditions. If this competence level is exactly one, or at least one, or it is at most k, where k ≥ 2, then the class of ET0L languages is determined by these constructions.
Acknowledgements
The work of the first two authors was supported by a research cooperation, performed in the frame of the Hungarian-German Intergovernmental S&T Cooperation Programme, supported by the Office of Research and Development Division of the Hungarian Ministry of Education and its foreign contractual partner, BMBF. The work of the third author was supported by project Centre of Excellence in Information Technology, Computer Science and Control, ICA1-CT-2000-70025, HUN-TING project, workpackage 5.