Abstract
Abstract. This paper presents the second part of the technical report [7] in which the study of the relation between Parallel Communicating Grammar Systems (PCGS) and Freely Rewriting Restarting Automata (FRR) has been initiated.
The first part of [7] is presented in [6]. Here, the distribution and generation complexity for PCGS are introduced and studied.
It is shown that analysis by reduction for PCGS with distribution complexity bounded by a constant k and generation complexity bounded by some other constant j can be implemented by strongly linearized deterministic FRR-automata with k rewrites per cycle. We show infinite hierarchies of classes of languages based on the parameters k; j and on the notion of skeleton.