---
title: "A Complete Classification of Complexity in Allens Algebra in the Presence of a Non-Trivial Basic Relation"
authors:
  - "Andrei A. Krokhin"
  - "Peter Jeavons"
  - "Peter Jonsson"
doi: ""
url: "https://ijcai.org/proceedings/2001/11"
pdf: "https://ijcai.org/proceedings/2001/0011.pdf"
venue: "Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence"
year: 2001
pages: "83-87"
track: ""
keywords:
---

# A Complete Classification of Complexity in Allens Algebra in the Presence of a Non-Trivial Basic Relation

Andrei A. Krokhin, Peter Jeavons, Peter Jonsson

*Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence*, pages 83-87.

## Abstract

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 NPcomplete 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.