UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Tractable approximations for temporal constraint handling

Hirsch, R; (2000) Tractable approximations for temporal constraint handling. Artificial Intelligence , 116 (1-2) 287 - 295. 10.1016/S0004-3702(99)00089-2.

Full text not available from this repository.


Relation algebras have been used for various kinds of temporal reasoning. Typically the network satisfaction problem turns out to be NP-hard. For the Allen interval algebra it is often convenient to use the propagation algorithm. This algorithm is sound and runs in cubic time but it is not complete. Here we define a series of tractable algorithms that provide approximations to solving the network satisfaction problem for any finite relation algebra. For algebras where all 3-consistent atomic networks are satisfiable, like the Allen interval algebra, we can improve these algorithms so that each algorithm runs in cubic time. These algorithms improve on the Allen propagation algorithm and converge on a complete algorithm.

Title:Tractable approximations for temporal constraint handling
UCL classification:UCL > School of BEAMS > Faculty of Engineering Science > Computer Science

Archive Staff Only: edit this record