Parallel communicating grammar systems: the context-sensitive case
Octavian Procopiuc, Cecilia Magdalena Ionescu, Ferucio Laurenţiu Ţiplea · International Journal of Computer Mathematics · 1993
We prove that any recursively enumerable set can be generated by a returning synchronized parallel communicating grammar system of degree three, where one of its components is context-sensitive and the other two are regular (without using λ-rules). In the case that the rule S → λ is used in at least one component (S being the axiom), the returning or non-returning synchronized context-sensitive parallel communicating systems can simulate the deterministic counter machines, and as a consequence of the undecidability of the halting problem for such machines we obtain that the circularity problem ([6]) for such parallel systems is undecidable.