Maximal Tractable Subclasses of Allen's Interval Algebra: Preliminary Report
Abstract
This paper continues Nebel and Burckert's investigation of Allen's interval algebra by presenting nine more maximal tractable subclasses of the algebra (provided that P ≠ N P), in addition to their previously reported ORD-Horn subclass. Furthermore, twelve tractable subclasses are identified, whose maximality is not decided. Four of these can express the notion of sequentiality between intervals, which is not possible in the ORD-Horn algebra. The satisfiability algorithm, which is common for all the algebras, is shown to be linear.
Cite
Text
Drakengren and Jonsson. "Maximal Tractable Subclasses of Allen's Interval Algebra: Preliminary Report." AAAI Conference on Artificial Intelligence, 1996.Markdown
[Drakengren and Jonsson. "Maximal Tractable Subclasses of Allen's Interval Algebra: Preliminary Report." AAAI Conference on Artificial Intelligence, 1996.](https://mlanthology.org/aaai/1996/drakengren1996aaai-maximal/)BibTeX
@inproceedings{drakengren1996aaai-maximal,
title = {{Maximal Tractable Subclasses of Allen's Interval Algebra: Preliminary Report}},
author = {Drakengren, Thomas and Jonsson, Peter},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {1996},
pages = {389-394},
url = {https://mlanthology.org/aaai/1996/drakengren1996aaai-maximal/}
}