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.

Cooperating distributed grammar systems: components with nonincreasing competence

Maurice H ter Beek;
2011

Abstract

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.
2011
Istituto di Scienza e Tecnologie dell'Informazione "Alessandro Faedo" - ISTI
Inglese
Jozef Kelemen, Alica Kelemenová
Computation, Cooperation, and Life. Essays Dedicated to Gheorghe P?un on the Occasion of His 60th Birthday
70
89
978-3-642-19999-8
http://link.springer.com/chapter/10.1007%2F978-3-642-20000-7_7?LI=true
Springer-Verlag
Berlin
GERMANIA
Grammar systems
competence
ID PUMA: /cnr.isti/2011-A1-013
1
02 Contributo in Volume::02.01 Contributo in volume (Capitolo o Saggio)
268
restricted
Maurice H. ter Beek ; Erzsébet CsuhajVarjú ; Markus Holzer ; György Vaszil
info:eu-repo/semantics/bookPart
File in questo prodotto:
File Dimensione Formato  
prod_201906-doc_44551.pdf

solo utenti autorizzati

Descrizione: capitolo
Tipologia: Versione Editoriale (PDF)
Dimensione 350.94 kB
Formato Adobe PDF
350.94 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.14243/10751
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 0
social impact