On the number of components in cooperating distributed grammar systems
- It is proved that the number of components in context-free cooperating distributed (CD) grammar systems can be reduced to 3 when they are working in the so-called sf-mode of derivation, which is the cooperation protocol which has been considered first for CD grammar systems. In this derivation mode, a component continues the derivation until and unless there is a nonterminal in the sentential form which cannot be rewritten according to that component. Moreover, it is shown that CD grammar systems in sf-mode with only one component can generate only the context-free languages but they can generate non-context-free languages if two components are used. The sf-mode of derivation is compared with other well-known cooperation protocols with respect to the hierarchies induced by the number of components. (C) 2004 Elsevier B.V. All rights reserved
| Author details: | Henning BordihnORCiD |
|---|---|
| ISSN: | 0304-3975 |
| Publication type: | Article |
| Language: | English |
| Year of first publication: | 2005 |
| Publication year: | 2005 |
| Release date: | 2017/03/24 |
| Source: | Theoretical Computer Science. - ISSN 0304-3975. - 330 (2005), 2, S. 195 - 204 |
| Organizational units: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik und Computational Science |
| Peer review: | Referiert |
| Institution name at the time of the publication: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik |
