The DOI matches its Crossref record; 20 of the 20 references it cites were found in a registry or an index.
Reasoning about temporal relations: a maximal tractable subclass of Allen's interval algebra
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Maintaining knowledge about temporal intervals
Allen, J. F. (1983) · Communications of the ACM · doi:10.1145/182.358434 · Cited by 7,593 · cited 12×
“Provided we are interested in temporal reasoning in the framework as described by Allen [2], one necessary requirement is that all basic relations are contained in the subclass.”
BackgroundMethodInfluentialLecture Notes in Artificial Intelligence
Brézillon, P., & Bouquet, P. (1999) · Cited by 7,473
Proceedings of the 19th International Joint Conference on Artificial Intelligence
Pujol, J. M., Delgado, J., Ramon Sangüesa, A., & Flache, A. (2005) · International Joint Conference on Artificial Intelligence · Cited by 5,771
Towards a general theory of action and time
Allen, J. F. (1984) · Artificial Intelligence · doi:10.1016/0004-3702(84)90008-0 · Cited by 2,559
Consistency in networks of relations
Mackworth, A. K. (1977) · Artificial Intelligence · doi:10.1016/0004-3702(77)90007-8 · Cited by 2,498
Networks of constraints: Fundamental properties and applications to picture processing
Montanari, U. (1974) · Information Sciences · doi:10.1016/0020-0255(74)90008-5 · Cited by 1,275
Linear-time algorithms for testing the satisfiability of propositional horn formulae
Dowling, W. F., & Gallier, J. H. (1984) · The Journal of Logic Programming · doi:10.1016/0743-1066(84)90014-1 · Cited by 1,013
Temporal reasoning based on semi-intervals
Freksa, C. (1992) · Artificial Intelligence · doi:10.1016/0004-3702(92)90090-k · Cited by 678
Constraint propagation algorithms for temporal reasoning
Vilain, M., & Kautz, H. (1986) · Cited by 632
Mackworth, A. K., & Freuder, E. C. (1985) · Artificial Intelligence · doi:10.1016/0004-3702(85)90041-4 · Cited by 619
Synthesizing constraint expressions
Freuder, E. C. (1978) · Communications of the ACM · doi:10.1145/359642.359654 · Cited by 538
Constraint Propagation Algorithms for Temporal Reasoning: A Revised Report
Vilain, M., Kautz, H., & van Beek, P. (1990) · Readings in Qualitative Reasoning About Physical Systems · doi:10.1016/b978-1-4832-1447-4.50034-1 · Cited by 354
Expressiveness and tractability in knowledge representation and reasoning1
Levesque, H. J., & Brachman, R. J. (1987) · Computational Intelligence · doi:10.1111/j.1467-8640.1987.tb00176.x · Cited by 320
Planning using a temporal world model
Allen, J. F., & Koomen, J. A. G. M. (1983) · Cited by 263
Exact and approximate reasoning about temporal relations1
Van Beek, P., & Cohen, R. (1990) · Computational Intelligence · doi:10.1111/j.1467-8640.1990.tb00130.x · Cited by 196
Complexity and algorithms for reasoning about time: a graph-theoretic approach
Golumbic, M. C., & Shamir, R. (1993) · Journal of the ACM · doi:10.1145/174147.169675 · Cited by 188
Ladkin, P. B., & Maddux, R. D. (1994) · Journal of the ACM · doi:10.1145/176584.176585 · Cited by 185
Managing efficiently temporal relations through indexed spanning trees
Ghallab, M., & Alaoui, A. M. (1989) · Cited by 81
The satisfiability of temporal constraint networks
Valdés‐Pérez, R. E. (1987) · National Conference on Artificial Intelligence · Cited by 36
Algorithms and complexity for reasoning about time
Golumbic, M. C., & Ron Shamir, A. (1992) · National Conference on Artificial Intelligence · Cited by 17
Cited by
Handbook of Constraint Programming
(2006) · Foundations of Artificial Intelligence · doi:10.1016/s1574-6526(06)x8001-x · Cited by 1,483
Qualitative Spatial Representation and Reasoning: An Overview
Cohn, A. G., & Hazarika, S. M. (2001) · doi:10.5555/1219982.1219984 · Cited by 667
Qualitative Spatial Representation and Reasoning with the Region Connection Calculus
Cohn, A. G., Bennett, B., Gooday, J., & Gotts, N. M. (1997) · GeoInformatica · doi:10.1023/a:1009712514511 · Cited by 566
Chapter 13 Qualitative Spatial Representation and Reasoning
(2008) · Foundations of Artificial Intelligence · doi:10.1016/s1574-6526(07)03013-1 · Cited by 361
Qualitative Spatial Reasoning Using Constraint Calculi
Renz, J., & Nebel, B. (2007) · Handbook of Spatial Logics · doi:10.1007/978-1-4020-5587-4_4 · Cited by 261
Self-citation
Metadata
- Authors
- Nebel, B., & Bürckert, H.-J.
- Venue
- Journal of the ACM
- Published
- 1995-01-03
- Volume
- 42
- Issue
- 1
- Pages
- 43-66
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W1996011776
- Cited by
- 406
- References
- 20
- FWCI
- 22.31
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.