Articolo in rivista, 2004, ENG
ter Beek M.; Csuhaj-Varju E.; Holzer M.; Vaszil G.
CNR-ISTI, Pisa, Italy; Computer and Automation Research Institute, Hungarian Academy of Sciences, Budapest, Hungary; Institut für Informatik, Technische Universität München, München, Germany; Computer and Automation Research Institute, Hungarian Academy of Sciences, Budapest, Hungary
We investigate the generative power of cooperating distributed grammar systems (CDGSs), if the cooperation protocol is based on the level of competence on the underlying sentential form. A component is said to be =k-competent (=k-competent, resp.) on a sentential form if it is able to rewrite exactly k (at most k, at least k, resp.) different nonterminals appearing in that string. In most cases CDGSs working according to the above described cooperation strategy turn out to give new characterizations of the language families based on random context conditions, namely random context (context-free) languages and the biologically motivated family of languages generated by ET0L systems with random context. Thus, the results presented in this paper can shed new light on some longstanding open problems in the theory of regulated rewriting.
Lecture notes in computer science 3340 , pp. 76–88
Cooperating distributed grammar systems, Cooperation protocols, Competence, Regulated rewriting
ISTI – Istituto di scienza e tecnologie dell'informazione "Alessandro Faedo"
ID: 43765
Year: 2004
Type: Articolo in rivista
Creation: 2009-06-16 00:00:00.000
Last update: 2017-12-05 09:47:41.000
CNR authors
External links
OAI-PMH: Dublin Core
OAI-PMH: Mods
OAI-PMH: RDF
URL: http://www.springerlink.com/link.asp?id=p0d6t3rv9fmc1wx5
External IDs
CNR OAI-PMH: oai:it.cnr:prodotti:43765
Scopus: 2-s2.0-35048856978