A complete classification of complexity in Allen's algebra in the presence of a non-trivial basic relation
Andrei Krokhin, Peter Jeavons, Peter Jönsson · International Joint Conference on Artificial Intelligence · 2001
We study fragments of Allen's algebra that contain a basic relation distinct from the equality relation. We prove that such a fragment is either NP-complete or else contained in some already known tractable subalgebra. We obtain this result by giving a new uniform description of known maximal tractable subalgebras and then systematically using an algebraic technique for description of maximal subalgebras with a given property. This approach avoids the need for extensive computerassisted search.