Abstract:

We compare the complexity of generating a language by a context-free grammar or by a parallel communicating grammar system ($PCGS$), in the sense of Gruska's measures $Var, Prod,\ Symb$. Then we define a specific measure for $PCGS, Com$, dealing with the number of communication symbols appearing in a derivation. The results are the expected ones: the $PCGS$ are definitely more efficient than context-free grammars (the assertion will receive a precise meaning in Section 2), the parameter $Com$ introduces an infinite hierarchy of languages, is incomparable with $Var, Prod, Symb$, and cannot be algorithmically computed.