Reasoning about temporal relations
- 3 January 1995
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 42 (1) , 43-66
- https://doi.org/10.1145/200836.200848
Abstract
We introduce a new subclass of Allen's interval algebra we call “ORD-Horn subclass,” which is a strict superset of the “pointisable subclass.” We prove that reasoning in the ORD-Horn subclass is a polynomial-time problem and show that the path-consistency method is sufficient for deciding satisfiability. Further, using an extensive machine-generated case analysis, we show that the ORD-Horn subclass is a maximal tractable subclass of the full algebra (assuming P ≠ NP). In fact, it is the unique greatest tractable subclass amongst the subclasses that contain all basic relations.Keywords
This publication has 13 references indexed in Scilit:
- On binary constraint problemsJournal of the ACM, 1994
- Complexity and algorithms for reasoning about timeJournal of the ACM, 1993
- Exact and approximate reasoning about temporal relations1Computational Intelligence, 1990
- Expressiveness and tractability in knowledge representation and reasoning1Computational Intelligence, 1987
- Linear-time algorithms for testing the satisfiability of propositional horn formulaeThe Journal of Logic Programming, 1984
- Maintaining knowledge about temporal intervalsCommunications of the ACM, 1983
- Synthesizing constraint expressionsCommunications of the ACM, 1978
- Consistency in networks of relationsArtificial Intelligence, 1977
- Unit Refutations and Horn SetsJournal of the ACM, 1974
- Networks of constraints: Fundamental properties and applications to picture processingInformation Sciences, 1974