Dana Pardubská, Martin Plátek and Friedrich Otto:  On the Correspondence between Parallel Communicating Grammar Systems and Restarting Automata

Abstract:  This technical report is devoted to the study of the relation between Parallel Communicating Grammar Systems (PCGS) and Freely Rewriting Restarting Automata (FRR). Besides communication complexity we introduce and study also so-called distribution and generation complexity. It is shown that analysis by reduction for a PCGS with distribution complexity bounded by a constant t and generation complexity bounded by a constant j can be implemented by a strongly linearized deterministic FRR-automaton with t rewrites per cycle.We show that, from a communication complexity point of view, 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. That makes this class of languages interesting from the point of view of formal linguistics. Further, we present infinite hierarchies of classes of languages based on the parameters t,j and on the new notion of skeleton.