The Minimization and Decomposition of Interface State Machines

There is a well-recognized need for accurate timing-verification tools that account for the functional behavior of component interfaces, and thereby do not traverse false sequential and combinational paths. Such tools, however, are susceptible to an exponential increase in task complexity as circuit-size and functional-complexity of component interfaces increase. The viability of accurate timing verifiers, therefore, hinges on their ability to efficiently analyze the smallest subset of circuit behaviors, while verifying timing characteristics of the overall space of behaviors. This paper presents theoretical results that address this issue for the timing-verification of circuits composed of interacting state machines.