Complexity classification in qualitative temporal constraint reasoning

DOI10.1016/j.artint.2004.05.010zbMath1086.68130OpenAlexW1991242118MaRDI QIDQ814637

Peter Jonsson, Andrei A. Krokhin

Publication date: 7 February 2006

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

Full work available at URL: https://doi.org/10.1016/j.artint.2004.05.010

zbMATH Keywords

Computational complexityConstraint satisfactionTemporal reasoning

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) Temporal logic (03B44)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maintaining knowledge about temporal intervals
• Point algebras for temporal reasoning: Algorithms and complexity
• Temporal constraints: A survey
• ``Corner relations in Allen's algebra
• A unifying approach to temporal constraint reasoning
• Computational complexity of relating time points with intervals
• Twenty-one large tractable subclasses of Allen's algebra
• Combining qualitative and quantitative constraints in temporal reasoning
• Reasoning about temporal relations
• Complexity and algorithms for reasoning about time
• Expressive power and complexity in algebraic logic
• Reasoning about temporal relations
• Constraint Satisfaction Problems on Intervals and Lengths
• Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning

This page was built for publication: Complexity classification in qualitative temporal constraint reasoning