Abstract
Hierarchical object descriptions consisting of a set of module descriptions are considered, where each module is either a primitive module or has a body that is an interconnection of submodules. The description represents a flattened object, whose size can be exponential in the size 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 shown that hierarchically specified acyclic circuits can be simulated deterministically in space linear in the size of the description, even when the description is not explicitly acyclic. Θ(n 2)-size-bounded reductions are given from the languages in DSPACE(n) to the problem of simulating hierarchically specified acyclic monotone circuits. This implies that this simulation problem is PSPACE-complete and that any algorithm for it that operates faster than \(2^{O(\sqrt{n})}\) deterministic time could be used to recognize all DSPACE(n) languages in less than 2O(n) deterministic time. It is then shown that the simulation problem for hierarchically specified acyclic circuits (not necessarily monotone) can indeed be solved in \(2^{O(\sqrt{n})}\) deterministic time. Moreover, every hierarchically specified acyclic circuit is shown to have an equivalent flat circuit of size \(2^{O(\sqrt{n})}\) . For binary circuits the size of the equivalent flat circuit is \(O(n^{3/2}2^{1.53\sqrt{n}})\) . It is also shown that the problem of simulating hierarchically specified circuits is EXPSPACE-complete for cyclic circuits.
This research was supported by the National Science Foundation grants DCR 86-03184 and CCR 88-03278.
This research was supported by the National Science Foundation grants DCR 86-03184 and CCR 89-03319.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison–Wesley, Reading, 1974.
J. Benkoski and A. J. Strojwas. A new approach to hierarchical and statistical timing simulations. IEEE Trans. Computer-Aided Design, CAD-6:1039–1052, 1987.
J. L. Bentley and T. Ottman. The complexity of manipulating hierarchically defined sets of rectangles. In J. Gruska and M. Chytil, editors, Proc. Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, volume 118, pages 1–15. Springer, Berlin, 1981.
P. A. Bloniarz, H. B. Hunt III, and D. J. Rosenkrantz. Algebraic structures with hard equivalence and minimization problems. J. Assoc. Comput. Mach., 31:879–904, 1984.
J. D. Crawford. EDIF: A mechanism for the exchange of design information. IEEE Design and Test, 2:63–69, 1985.
M. R. Garey and D. S. Johnson. Computers and Intractability. Freeman, San Francisco, 1979.
J. P. Hayes. Digital simulation with multiple logic values. IEEE Trans. Computer-Aided Design, CAD-5:274–283, 1986.
R. Kolla and B. Serf. The virtual feedback problem in hierarchical representations of combinatorial circuits. Acta Informatica, 28:463–476, 1991.
T. Lengauer. Exploiting hierarchy in VLSI design. In F. Makedon , editor, Proc. Aegean Workshop on Computing. Lecture Notes in Computer Science, volume 227, pages 180–193. Springer, Berlin, 1986.
T. Lengauer. Hierarchical planarity testing algorithms. In L. Kott, editor, Proc. 13th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, volume 226, pages 215–225. Springer, Berlin, 1986.
T. Lengauer. Efficient algorithms for finding minimum spanning forests of hierarchically defined graphs. J. Algorithms, 8:260–284, 1987.
T. Lengauer and K. W. Wagner. The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems. In E. J. Brandenburg , editors, Proc. 4th Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, volume 247, pages 100–113. Springer, Berlin, 1987.
T. Lengauer and E. Wanke. Efficient solution of connectivity problems in hierarchically defined graphs. SIAM J. Comput., 17:1063–1089, 1988.
Y. Levendel and P. R. Menon. Fault simulation. In D. K. Pradhan, editor, Fault-Tolerant Computing: Theory and Techniques, volume 1, pages 184–264. Prentice Hall, Englewood Cliffs, 1986.
R. Lipsett, E. Marschner, and M. Shahdad. VHDL–the language. IEEE Design and Test, 3:28–41, 1986.
S. Maclane and G. Birkhoff. Algebra. MacMillan, New York, 1967.
J. Magee, J. Kramer, and M. Sloman. Constructing distributed systems in conic. IEEE Trans. Software Engrg., 15:663–675, 1989.
C. Mead and L. Conway. Introduction to VLSI Systems. Addison–Wesley, Reading, 1980.
C. Niessen. Hierarchical design methodologies and tools for VLSI chips. Proc. IEEE, 41:65–75, 1983.
J. K. Ousterhout, G. T. Hamachi, R. N. Mayo, W. S. Scott, and G. S. Taylor. The magic VLSI layout system. IEEE Design and Test, 2:19–30, 1985.
L. K. Scheffer and R. Soetarman. Hierarchical analysis of IC artwork with user defined abstraction rules. In Proc. ACM/IEEE 22nd Design Automation Conference, pages 293–298, 1985.
L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time. In Proc. 5th Annual ACM Symposium on Theory of Computing, pages 1–9, 1973.
T. J. Wagner. Hierarchical layout verification. IEEE Design and Test, 2:31–37, 1985.
U. Zimmerman. Linear and Combinatorial Optimization in Ordered Algebraic Structures. North-Holland, Amsterdam, 1981.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer Science + Business Media B.V.
About this chapter
Cite this chapter
Rosenkrantz, D.J., Hunt, H.B. (2009). The Complexity of Processing Hierarchical Specifications. In: Ravi, S.S., Shukla, S.K. (eds) Fundamental Problems in Computing. Springer, Dordrecht. https://doi.org/10.1007/978-1-4020-9688-4_8
Download citation
DOI: https://doi.org/10.1007/978-1-4020-9688-4_8
Publisher Name: Springer, Dordrecht
Print ISBN: 978-1-4020-9687-7
Online ISBN: 978-1-4020-9688-4
eBook Packages: Computer ScienceComputer Science (R0)