Several hardware description mechanisms and computational problems involved in the analysis and design of digital circuits are investigated. The goals are to obtain a deeper, theoretical understanding of how the description mechanism affects these computational problems, and to devise more efficient algorithms for specific problems of interest. New models are being formulated where appropriate, the effects of varying the form of certain description mechanisms are being clarified, new algorithms and construction schemes are being developed, and the complexity of many problems is studied. There is a focus on hierarchical descriptions, with attention paid to which problems can be solved more efficiently than is possible when the flattened circuit specified by the given hierarchical description is constructed. Issues associated with the tree corresponding to a given hierarchical description, and attributed values on this tree are being addressed. The effect of algebraic specification and the effect of the underlying algebraic system are also studied. Problems considered include analysis, simulation, testing, and synthesis. The construction and analysis of test schemes for algorithm-based fault tolerance is studied. Certain hardware synthesis problems are investigated, from the perspective of exploitability of algebraic or hierarchical specifications.
