TRADING INDEPENDENT FOR SYNCHRONIZED PARALLELISM IN FINITE COPYING PARALLEL REWRITING-SYSTEMS

The so-called family of finite copying parallel rewriting systems is c onsidered in this work, including well-known generative devices and tr ansducers as for instance the deterministic tree-walking transducers, the string generating context-free hypergraph grammars, and the multip le context-free grammars. Two parameters have been defined in the lite rature for all or the above systems, called the degree of synchronized parallelism and the degree of independent parallelism. When constant bounds are imposed on these parameters, the subclasses of languages ge nerated by the above systems form a two-dimensional hierarchy. In this paper we investigate the interactions between these two parameters an d establish new inclusion and separation results for subclasses of the hierarchy. More precisely, for a full half of the hierarchy we provid e necessary and sufficient conditions to determine when a language sub class defined by an integer bound of r on the degree of independent pa rallelism is included in, includes, or is incomparable with a subclass defined by a bound of r - 1 on the same parameter. This means that, i n the given range, we can exactly determine which increase in the degr ee of synchronized parallelism must be taken in order to compensate fo r a reduction of one unit in the degree of independent parallelism Thi s solves a question left open in the literature. (C) 1998 Academic Pre ss.