Cooperating Distributed Grammar Systems as Models of Distributed Problem Solving,Revisited

Abstract

Based on a derivation mode f for cooperating distributed (CD) grammar systems, we introduce a new form of cooperation protocol, the so called "cut-f-mode" of derivation. Intuitively, in the cut-f-mode of derivation the sentential form is partitioned (cut) into several subwords, where some of these subwords are distributed to the components, which derive them according to the underlying f-mode of derivation, and finally the new sentential form is obtained by concatenating all the subwords–derived or not–in their original order. According to the original motivation from distributed artificial intelligence, the new functioning mode appears to be more realistic than the original model. We investigate the cut-mode versions of the basic derivation modes and some of their combined versions. It turns out that in most cases, the cut-f-mode is at most as powerful as the corresponding non-cut-mode, that is, the f-mode itself. In some cases the power is even reduced to that of context-free grammars.