Kybernetika 28 no. 2, 155-166, 1992

On the syntactic complexity of parallel communicating grammar systems

Gheorghe Păun


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.


68Q42, 68Q50, 68Q25