A Complete Classification of Complexity in Allens Algebra in the Presence of a Non-Trivial Basic Relation
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.
Andrei A. Krokhin, Peter Jeavons, and Peter Jonsson. 2001. A Complete Classification of Complexity in Allens Algebra in the Presence of a Non-Trivial Basic Relation. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI-01. IJCAI, 83–87. https://ijcai.org/proceedings/2001/11
Krokhin, A. A., Jeavons, P., & Jonsson, P. (2001). A Complete Classification of Complexity in Allens Algebra in the Presence of a Non-Trivial Basic Relation. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI-01 (pp. 83–87). IJCAI. https://ijcai.org/proceedings/2001/11
@inproceedings{ijcai2001p11,
title = {A Complete Classification of Complexity in Allens Algebra in the Presence of a Non-Trivial Basic Relation},
author = {Krokhin, Andrei A. and Jeavons, Peter and Jonsson, Peter},
booktitle = {Proceedings of the Seventeenth International Joint Conference on
Artificial Intelligence, {IJCAI-01}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {83--87},
year = {2001},
url = {https://ijcai.org/proceedings/2001/11},
}
TY - CPAPER TI - A Complete Classification of Complexity in Allens Algebra in the Presence of a Non-Trivial Basic Relation AU - Krokhin, Andrei A. AU - Jeavons, Peter AU - Jonsson, Peter T2 - Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI-01 PB - International Joint Conferences on Artificial Intelligence PY - 2001 SP - 83 EP - 87 UR - https://ijcai.org/proceedings/2001/11 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
