THE COMPLEXITY OF PROCESSING HIERARCHICAL SPECIFICATIONS

Hierarchical object descriptions consisting of a set of module descrip tions are considered, where each module is either a primitive module o r has a body that is an interconnection of submodules. The description represents a flattened object, whose size can be exponential in the s ize of the description. The complexity of processing and/or analyzing such hierarchically specified objects is considered. The simulation of hierarchically specified circuits is emphasized, but the results are applicable to other kinds of hierarchically specified objects. It is s hown that hierarchically specified acyclic circuits can be simulated d eterministically in space linear in the size of the description, even when the description is not explicitly acyclic. THETA(n2)-size-bounded reductions are given from the languages in DSPACE(n) to the problem o f simulating hierarchically specified acyclic monotone circuits. This implies that this simulation problem is PSPACE-complete and that any a lgorithm for it that operates faster than 2O(square-root n) determinis tic time could be used to recognize all DSPACE(n) languages in less th an 2O(n) deterministic time. It is then shown that the simulation prob lem for hierarchically specified acyclic circuits (not necessarily mon otone) can indeed be solved in 2O(square-root n) deterministic time. M oreover, every hierarchically specified acyclic circuit is shown to ha ve an equivalent flat circuit of size 2O(square-root n). For binary ci rcuits the size of the equivalent flat circuit is O (n(3/2)2(1.53) squ are-root n). It is also shown that the problem of simulating hierarchi cally specified circuits is EXPSPACE-complete for cyclic circuits.