Affiliations: Institut für Informatik, Universität
Potsdam, August-Bebel-Straße 89, D-14482 Potsdam, Germany.
E-mail: [email protected] | Institut füur Informatik, Technische
Universität München, Boltzmannstraße 3, D-85748 Garching bei
München, Germany. E-mail: [email protected]
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.
Keywords: Cooperating distributed grammar systems, derivation modes, regulated rewriting, programmed grammars, finite index restriction, Lindenmayer languages
