Reasoning about temporal relations
From MaRDI portal
Publication:3452504
DOI10.1145/876638.876639zbMath1325.68220MaRDI QIDQ3452504
Andrei A. Krokhin, Peter Jonsson, Peter G. Jeavons
Publication date: 12 November 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/876638.876639
complexity; NP-completeness; dichotomy theorem; tractable cases; Allen's algebra; representing graphs by intervals; satisfiability of temporal constraints
68Q25: Analysis of algorithms and problem complexity
68T27: Logic in artificial intelligence
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Constraint Satisfaction Problems with Infinite Templates, Tractability in constraint satisfaction problems: a survey, Reasoning about cardinal directions between extended objects: the NP-hardness result, Spatial reasoning with \(\mathcal{RCC} 8\) and connectedness constraints in Euclidean spaces, Interval graph representation with given interval and intersection lengths, An initial study of time complexity in infinite-domain constraint satisfaction, Point algebras for temporal reasoning: Algorithms and complexity, Complexity classification in qualitative temporal constraint reasoning, Reasoning about cardinal directions between extended objects, Maximal infinite-valued constraint languages, Determining the consistency of partial tree descriptions, Implementation of the temporal reasoning mechanism in modern intelligent systems, Temporal reasoning about fuzzy intervals, Extending partial representations of interval graphs, Incremental qualitative temporal reasoning: Algorithms for the point algebra and the ORD-Horn class, Planning temporal events using point-interval logic, Satisfying constraint sets through convex envelopes, Quantifying the Discord: Order Discrepancies in Message Sequence Charts, QUANTIFYING THE DISCORD: ORDER DISCREPANCIES IN MESSAGE SEQUENCE CHARTS
