History


Please fill in your query. A complete syntax description you will find on the General Help page.
Descriptional complexity of restricted CD grammar systems. (English)
J. Autom. Lang. Comb. 14, No. 1, 7-22 (2009).
Summary: The problem is addressed to what extent cooperating distributed (CD) grammar systems with metalinear components are more succinct than metalinear grammars when describing metalinear languages. As measures of succinctness, the number of variables, the number of productions and the total number of symbols are considered. It is shown that CD grammar systems can achieve the best possible increase of efficiency compared with metalinear grammars with respect to all the three measures and in case of almost all derivation modes. Regarding the numbers of variables and productions, these results remain valid even in comparison with context-free grammars. Finally, the known results for unrestricted context-free CD grammar systems in comparison with context-free grammars are supplemented with respect to another derivation mode, namely the full competence (sf-) mode.
WorldCat.org
Valid XHTML 1.0 Transitional Valid CSS!