Title :
Algorithms for interface timing verification
Author :
McMillan, Kenneth L. ; Dill, David L.
Author_Institution :
Sch. of Comput. Sci., Carnegie Mellon Univ., Pittsburgh, PA, USA
Abstract :
Algorithms for analyzing systems of inequalities with min/max constraints that arise in interface timing specifications are examined. A general form of the inequality is shown to be NP-complete, but some interesting special cases can be solved efficiently. A branch-and-bound solution to the general case is developed and applied to a previously published example
Keywords :
computational complexity; logic design; minimax techniques; NP-complete; branch-and-bound solution; interface timing verification; min/max constraints; systems of inequalities; Algorithm design and analysis; Capacitive sensors; Computer science; Constraint optimization; Contracts; Delay effects; Digital circuits; Linear programming; Polynomials; Timing;
Conference_Titel :
Computer Design: VLSI in Computers and Processors, 1992. ICCD '92. Proceedings, IEEE 1992 International Conference on
Conference_Location :
Cambridge, MA
Print_ISBN :
0-8186-3110-4
DOI :
10.1109/ICCD.1992.276208
