Twenty-one large tractable subclasses of Allen's algebra

DOI10.1016/S0004-3702(97)00021-0zbMath1017.03514MaRDI QIDQ1402726

Thomas Drakengren, Peter Jonsson

Publication date: 28 August 2003

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

zbMATH Keywords

Computational complexityTemporal reasoningAllen's interval algebra

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27) Logic in computer science (03B70) Temporal logic (03B44)

Related Items (9)

Temporal reasoning about fuzzy intervals ⋮ Incremental qualitative temporal reasoning: Algorithms for the point algebra and the ORD-Horn class ⋮ Computing the minimal relations in point-based qualitative temporal reasoning through metagraph closure ⋮ Branching interval algebra: an almost complete picture ⋮ A unifying approach to temporal constraint reasoning ⋮ A complete classification of tractability in Allen's algebra relative to subsets of basic relations ⋮ Backtracking algorithms for disjunctions of temporal constraints ⋮ The complexity of constraint satisfaction problems for small relation algebras ⋮ Complexity classification in qualitative temporal constraint reasoning

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maintaining knowledge about temporal intervals
• Solving hard qualitative temporal reasoning problems: Evaluating the efficiency of using the ORD-Horn class
• Reasoning about qualitative temporal information
• Consistency in networks of relations
• Networks of constraints: Fundamental properties and applications to picture processing
• Full chains of twists for orthogonal algebras.
• Temporal reasoning based on semi-intervals
• Complexity and algorithms for reasoning about time
• Reasoning about temporal relations

This page was built for publication: Twenty-one large tractable subclasses of Allen's algebra