Independent Parallelism in Finite Copying Parallel Rewriting Systems

We consider the class of parallel rewriting systems and investigate the interaction between two complexity measures, that in the literature have been called synchronized parallelism and independent parallelism. It is shown that, when the degree of synchronized parallelism is bounded by some constant greater than one, the degree of independent parallelism induces an infinite non-collapsing hierarchy within the family of generated languages. The result is obtained using an original characterization of parallel rewriting systems. Other language-theoretic properties of parallel rewriting systems are proved in this work, that together with our main result provide an answer to some questions that were left open in the literature.