Reasoning about temporal relations

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

zbMATH Keywords

complexity; NP-completeness; dichotomy theorem; tractable cases; Allen's algebra; representing graphs by intervals; satisfiability of temporal constraints

Mathematics Subject Classification ID

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

Parameterized Complexity of the Workflow Satisfiability Problem, Unnamed Item, Unnamed Item, Constraint Satisfaction Problems with Infinite Templates, Unnamed Item, Fuzzy Halpern and Shoham's interval temporal logics, 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, Constants and finite unary relations in qualitative constraint reasoning, Implementation of the temporal reasoning mechanism in modern intelligent systems, Branching interval algebra: an almost complete picture, Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms, 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, General lower bounds and improved algorithms for infinite-domain CSPs, Satisfying constraint sets through convex envelopes, Quantifying the Discord: Order Discrepancies in Message Sequence Charts, QUANTIFYING THE DISCORD: ORDER DISCREPANCIES IN MESSAGE SEQUENCE CHARTS