Skip to Main Content (Press Enter)

Logo CNR
  • ×
  • Home
  • People
  • Outputs
  • Organizations
  • Expertise & Skills

UNI-FIND
Logo CNR

|

UNI-FIND

cnr.it
  • ×
  • Home
  • People
  • Outputs
  • Organizations
  • Expertise & Skills
  1. Outputs

Cooperating distributed grammar systems: components with nonincreasing competence

Chapter
Publication Date:
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.
Iris type:
02.01 Contributo in volume (Capitolo o Saggio)
Keywords:
Grammar systems; competence
List of contributors:
TER BEEK, MAURICE HENRI
Authors of the University:
TER BEEK MAURICE HENRI
Handle:
https://iris.cnr.it/handle/20.500.14243/10751
Book title:
Computation, Cooperation, and Life. Essays Dedicated to Gheorghe P?un on the Occasion of His 60th Birthday
  • Overview

Overview

URL

http://link.springer.com/chapter/10.1007%2F978-3-642-20000-7_7?LI=true
  • Use of cookies

Powered by VIVO | Designed by Cineca | 26.5.0.0 | Sorgente dati: PREPROD (Ribaltamento disabilitato)