Paper Info
Title
Cd Grammar Systems With Competence Based Entry Conditions In Their Cooperation Protocols
Abstract
In this paper we examine context-free cooperating distributed (CD) grammar systems where the cooperation protocol is based on the competence (capability) of the component grammars in rewriting. We study the power of a derivation mode where every component is allowed to start the generation only if it has a prescribed level of competence and it is allowed to finish the work if it is not competent anymore. The competence level of a component on a string is the number of different nonterminals in this word that can be rewritten by the production set of the grammar. We show that if the prescribed level of competence of the grammar to start the derivation is equal to k or is at least k, for some natural number k >= 2, then these CD grammar systems are as powerful as the ET0L systems with random context conditions. If this competence level is exactly one, or at least one, or it is at most k, where k >= 2, then the class of ET0L languages is determined by these constructions.
Year
DOI
Venue
2006
10.1080/00207160500113355
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS
Keywords
Field
DocType
grammar systems, cooperation, distribution, competence
Rule-based machine translation,Attribute grammar,Regular tree grammar,Computer science,Natural language processing,If and only if,Artificial intelligence,Regular grammar,Mathematical optimization,Natural number,Arithmetic,Grammar,Rewriting
Journal
Volume
Issue
ISSN
83
2
0020-7160
Citations 
PageRank 
References 
5
0.74
2
Authors
3
Name
Order
Citations
PageRank
Erzsébet Csuhaj-Varjú159387.27
Jürgen Dassow2530118.27
Markus Holzer319321.51