Several hardware description mechanisms for digital circuits will be investigated, with the goals of obtaining a better theoretical understanding of the comparative advantages and disadvantages of alternate mechanisms, formalizing new models where appropriate, developing efficient algorithms where possible, and revealing computational difficulty where present. Issues to be studied include how expressive power and the computational complexity of analysis and synthesis problems are affected by varying the model of a given description mechanism, or imposing restrictions on its features. Hierarchical, recursive, and algebraic descriptions will be investigated, and descriptions at varying levels of abstraction will be considered. Definitional and computational issues arising from the specification and computation of attributes associated with the exploded tree corresponding to a hierarchical circuit description will be explored. Alternate methods of describing combinational logic, their relative economy of description, their inter-translatability, and their suitability for automatic circuit synthesis and test generation, will be studied. Also to be investigated are issues involved in the use of massively parallel computers, particularly in uses pertaining to hardware analysis. Possible algorithmic factors posed by these machines are the effects of the interconnection network topology, and computation in a single instruction stream, multiple data stream mode.
