On context-free parallel communicating grammar systems: synchronization, communication, and normal forms

In this paper we study the generative power of context-free returning paral lel communicating grammar systems using different synchronization mechanism s and communication protocols. We demonstrate the equivalence of several ty pes of these systems and present normal form theorems showing that all lang uages generated by context-free returning parallel communicating grammar sy stems can also be generated by such systems having only rules of the form X --> alpha, where alpha consists of at most two symbols and if X --> alpha is a query rule, then alpha is a single query symbol. (C) 2001 Elsevier Sci ence B.V. All rights reserved.