Point algebras for temporal reasoning: Algorithms and complexity

DOI10.1016/S0004-3702(03)00075-4zbMath1082.68817MaRDI QIDQ814509

Peter Jonsson, Mathias Broxvall

Publication date: 7 February 2006

Published in: Artificial Intelligence (Search for Journal in Brave)

zbMATH Keywords

Constraint satisfactionTemporal reasoningPoint algebras

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

Solving infinite-domain CSPs using the patchwork property ⋮ Relation algebras of Sugihara, Belnap, Meyer, and Church ⋮ Qualitative constraint satisfaction problems: an extended framework with landmarks ⋮ An initial study of time complexity in infinite-domain constraint satisfaction ⋮ A Dichotomy for First-Order Reducts of Unary Structures ⋮ Constraint Satisfaction Problems with Infinite Templates ⋮ Unnamed Item ⋮ Complexity classification in qualitative temporal constraint reasoning

Cites Work

• Maintaining knowledge about temporal intervals
• Matrix multiplication via arithmetic progressions
• Reasoning about partially ordered events
• Using constraint propagation to reason about unsynchronized clocks
• A unifying approach to temporal constraint reasoning
• On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus
• Computational complexity of relating time points with intervals
• Disjunctions, independence, refinements
• Lattice structure of temporal interval relations
• Reasoning about action in polynomial time
• Building tractable disjunctive constraints
• Reasoning about temporal relations
• The Complexity of the Partial Order Dimension Problem
• Automatic verification of finite-state concurrent systems using temporal logic specifications
• “Sometimes” and “not never” revisited
• Time, clocks, and the ordering of events in a distributed system
• Complexity and algorithms for reasoning about time
• Expressive power and complexity in algebraic logic
• Reasoning about temporal relations
• Partial orders of dimension 2
• The mutual exclusion problem
• Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item