Parallel communicating grammar systems: the context-sensitive case

Abstract

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.

Keywords:

• Parallel communicating grammar systems
• Chomsky grammars
• counter machines

C.R Categories:

• F.4.2
• F.4.3
• H.1