Istituto di Scienza e Tecnologie dell'Informazione     
Ter Beek M., Csuhaj-Varju E., Holzer M., Vaszil G. Cooperating distributed grammar systems: components with nonincreasing competence. J. Kelemen, A. Kelemenová (eds.). (Lecture Notes in Computer Science, vol. 6610). Berlin: Springer-Verlag, 2011.
We study the generative power of CD grammar systems (CDGSs) that use a cooperation protocol based on the level of competence on a sentential form - and the competence of their components does not increase during rewriting. A component of a CDGS is k-competent on a sentential form if it can rewrite exactly k different nonterminals appearing in that string. A CDGS with components that are nonincreasing in competence works in =k-competence mode of derivation if no k-competent component can ever become l-competent, for some l > k. We introduce a static and a dynamic definition to impose this restriction, and we relate the generative power of such CDGSs working either in a sequential or in a parallel manner and according to the aforementioned cooperation protocol, for various k, with that of context-free forbidding random context grammars, (random context) ET0L systems, and context-free programmed grammars with appearance checking.
DOI: http://dx.doi.org/10.1007/978-3-642-20000-7_7
Subject Grammar systems
F.4.2 Grammars and Other Rewriting Systems. Grammar types

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional