Towards a Complete Classification of Tractability in Allen's Algebra
Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence. Temporal Reasoning. Pages 1466-1474.
Abstract
We characterise the set of subalgebras of Allen's algebra which have a tractable satisfiability problem, and in addition contain certain basic relations. The conclusion is that no tractable subalgebra that is not known in the literature can contain more than the three basic relations (=:), (b) and (b~), where b E {d, o, s, f}. This means that concerning algebras for specifying complete knowledge about temporal information, there is no hope of finding yet unknown classes with much expressivity. Furthermore, we show that there are exactly two maximal tractable algebras which contain the relation (~ >- ). Both of these algebras can express the notion of sequentiality; thus we have a complete characterisation of tractable inference using that notion.
@inproceedings{ijcai1997p211,
title = {Towards a Complete Classification of Tractability in Allen's Algebra},
author = {Drakengren, Thomas and Jonsson, Peter},
booktitle = {Proceedings of the Fifteenth International Joint Conference on
Artificial Intelligence, {IJCAI-97}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Martha E. Pollack},
pages = {1466--1474},
year = {1997},
note = {Temporal Reasoning},
url = {https://ijcai.org/proceedings/1997/211},
}
TY - CPAPER TI - Towards a Complete Classification of Tractability in Allen's Algebra AU - Drakengren, Thomas AU - Jonsson, Peter T2 - Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97 PB - International Joint Conferences on Artificial Intelligence PY - 1997 SP - 1466 EP - 1474 UR - https://ijcai.org/proceedings/1997/211 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
