TITLE: Chain Programming
SPEAKER: K. Subramani (West Virginia University)
WHEN: April 13, 4:30pm
WHERE: PPB 300
ABSTRACT: Chain Programming is a restricted form of Linear Programming; in a Chain Program, there exists a total ordering on the program variables. In other words, the constraints $x_{1} \le x_{2} \ldots x_{n}$ are either implicitly or explicitly part of the constraint system. At the present juncture, it is not clear whether an arbitrary linear program augmented with a chain is easier to solve than linear programs in general, either asymptotically or computationally. However, if the linear program is constituted entirely of difference constraints, then the total ordering results in an elegant divide and conquer algorithm for the problem of feasibility testing. This approach can be parallelized in straightforward fashion to run on any SIMD or MIMD architecture, thereby greatly enhancing its effectiveness. Inasmuch as difference constraint logic is an integral part of a number of verification problems in both model-checking and real-time scheduling, our result is of particular importance to these communities. One of the surprising consequences of our research is the establishment of a link between Chain Programs over Difference Constraints and a specialized class of Totally Unimoduluar (TUM) matrices called {\em interval} matrices.
