An introduction to temporal constraints and mathematical methods

An important class of problems, known as temporal constraint satisfaction problems, is shown to be representable using concepts from linear algebra. This extends to more general cases where alternative constraints may apply between problem variables, and where the original domains for these variables can include disjoint intervals of time. Using computational mechanisms from large-scale linear systems, the new formulation leads to a process where the problem's variables are solved for simultaneously (rather than serially), but where the search process still has to solve the combinatorial problem of determining applicable constraints and domains. Preliminary computational experience is reported on small-scale problems, with promising results.