On the Correspondence between Parallel Communicating Grammar Systems and Restarting Automata

Abstract This technical report integrates the results of [8] and [9] in which the study of the relation between Parallel Communicating Grammar Systems (PCGS) and Freely Rewriting Restarting Automata (FRR) has been initiated. Besides communication complexity we intro-duce and study 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 deter-ministic 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 com-plexity 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. Here we also consider non-deterministic linearized FRR-automata.