Maximum Time Separation of Events in Cyclic Systems with Linear and Latest Timing Constraints

The determination of the maximum time separations of events is important in the design, synthesis, and verification of digital systems, especially in interface timing verification. Many researchers have explored solutions to the problem with various restrictions: a) on the type of constraints, and b) on whether the events in the specification are allowed to occur repeatedly.

When the events can occur only once, the problem is well solved. There are fewer concrete results for systems where the events can occur repeatedly. We extend the work by Hulgaard et al.\ for computing the maximum separation of events in cyclic constraint graphs with latest constraints to constraint graphs with both linear and latest constraints.