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.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.