A complete classification of tractability in Allen's algebra relative to subsets of basic relations

DOI10.1016/S0004-3702(98)00093-9zbMath0910.68082OpenAlexW2059427085MaRDI QIDQ1277697

Thomas Drakengren, Peter Jonsson

Publication date: 2 March 1999

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

Full work available at URL: https://doi.org/10.1016/s0004-3702(98)00093-9

zbMATH Keywords

computational complexitytemporal reasoningtractabilitycomplete classificationAllen's algebra

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) General topics in artificial intelligence (68T01)

Related Items (5)

Spatial reasoning with rectangular cardinal relations. The convex tractable subalgebra ⋮ Qualitative reasoning with directional relations ⋮ Branching interval algebra: an almost complete picture ⋮ A new approach to cyclic ordering of 2D orientations using ternary relation algebras ⋮ Optimization in temporal qualitative constraint networks

Cites Work

• Maintaining knowledge about temporal intervals
• Solving hard qualitative temporal reasoning problems: Evaluating the efficiency of using the ORD-Horn class
• Temporal constraint networks
• Twenty-one large tractable subclasses of Allen's algebra
• Every planar map is four colorable
• Complexity and algorithms for reasoning about time
• Reasoning about temporal relations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A complete classification of tractability in Allen's algebra relative to subsets of basic relations