# ICS 269, Fall 2001: Theory Seminar

## 19 October 2001:

TIME SEPARATION OF EVENTS

Ravindra Jejurikar

The problem of time separation of events is an important
problem in interface timing verification. Propagation delays
are specified as a time bound (upper & lower bound) due to
manufacturing and environmental changes.
Three types of constraints are required in modelling
the properties of a circuit viz. max (AND gate), min (OR gate)
and linear (imposed constraints). Computing the maximum separations
under these constraints is discussed in the talk.

We restrict ourselves to ACYCLIC constraint graphs.
It is known that the problem can be solved in polynomail time
in the presence of only a single type of constraint. The problem
is NP-Complete when both max and min type constraints are present.
The complexity of the problem with max and linear constraint
is yet unknown (min + linear is dual of max - linear). It is conjectured
that it can be solved in polynomial time. We have studied the best known
algorithm( by Yen) which is conjectured to run in polynomial time.
We are working on some approaches to have a tight bound on the
algorithm and to verify the posed conjecture for max-linear constraint
problem.