Publication at Faculty of Mathematics and Physics |
2011
Abstract
Parallel communicating grammar systems with regular control (RPCGS, for short) are introduced, which are obtained from returning regular parallel communicating grammar systems by restricting the derivations that are executed in parallel by the various components through a regular control language. For the class of languages that are generated by RPCGSs with constant communication complexity we derive a characterisation in terms of a restricted type of freely rewriting restarting automaton.
From this characterisation we obtain that these languages are semi-linear, and that for RPCGSs with constant communication complexity, the centralised variant has the same generative power as the non-centralised variant.