Parallel communicating grammar systems and analysis by reduction

Abstract

Abstract. This paper studies the relation between Parallel Communicating Grammar Systems (PCGS) and Freely Rewriting Restarting Automata (FRR).

It is shown that analysis by reduction for a PCGS with m components, and with communication complexity bounded by constant k can be implemented by a strongly linearized deterministic FRR-automaton with t rewrites per cycle. We show that this implementation is almost optimal. As consequences we obtain a pumping lemma for the class of languages generated by PCGS with communication complexity bounded by a constant, and the fact that this class of languages is semi-linear.

Keywords

• Parallel
• communicating
• grammar
• systems
• analysis
• reduction