TY  - JOUR
A1  - Bordihn, Henning
T1  - On the number of components in cooperating distributed grammar systems
N2  - 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
Y1  - 2005
UR  - https://publishup.uni-potsdam.de/frontdoor/index/index/docId/13511
SN  - 0304-3975
ER  -