On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus
From MaRDI portal
Publication:1285670
DOI10.1016/S0004-3702(99)00002-8zbMath0914.68160MaRDI QIDQ1285670
Publication date: 28 April 1999
Published in: Artificial Intelligence (Search for Journal in Brave)
computational complexityregion connection calculusqualitative spatial reasoningpath-consistencytractable subclasses
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) General topics in artificial intelligence (68T01)
Related Items
Disjunctions, independence, refinements ⋮ Querying incomplete information in RDF with SPARQL ⋮ Spatial reasoning in a fuzzy region connection calculus ⋮ Line-based affine reasoning in Euclidean plane ⋮ Drawing interactive Euler diagrams from region connection calculus specifications ⋮ Fuzzy region connection calculus: An interpretation based on closeness ⋮ Generalized Qualitative Spatio-Temporal Reasoning: Complexity and Tableau Method ⋮ On topological consistency and realization ⋮ Drawing Euler Diagrams from Region Connection Calculus Specifications with Local Search ⋮ A tableau algorithm for description logics with concrete domains and general TBoxes ⋮ Hardness of Network Satisfaction for Relation Algebras with Normal Representations ⋮ On redundant topological constraints ⋮ Solving infinite-domain CSPs using the patchwork property ⋮ A condensed semantics for qualitative spatial reasoning about oriented straight line segments ⋮ Reasoning about cardinal directions between extended objects: the NP-hardness result ⋮ Reasoning about visibility ⋮ Unnamed Item ⋮ On standard models of fuzzy region connection calculus ⋮ A semi-dynamical approach for solving qualitative spatial constraint satisfaction problems ⋮ General lower bounds and improved algorithms for infinite-domain CSPs ⋮ Spatial reasoning with \(\mathcal{RCC} 8\) and connectedness constraints in Euclidean spaces ⋮ RCC8 binary constraint network can be consistently extended ⋮ Incremental qualitative temporal reasoning: Algorithms for the point algebra and the ORD-Horn class ⋮ On the consistency of cardinal direction constraints ⋮ Qualitative constraint satisfaction problems: an extended framework with landmarks ⋮ Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms ⋮ Relational representation theorems for extended contact algebras ⋮ A logic for metric and topology ⋮ Constants and finite unary relations in qualitative constraint reasoning ⋮ GNet: a generalized network model and its applications in qualitative spatial reasoning ⋮ Relation algebras and their application in temporal and spatial reasoning ⋮ Reasoning about cardinal directions between extended objects ⋮ Realizing RCC8 networks using convex regions ⋮ Maximal infinite-valued constraint languages ⋮ A Topological Constraint Language with Component Counting ⋮ A Canonical Model of the Region Connection Calculus ⋮ Design and comparison of lattices of topological relations for spatial representation and reasoning ⋮ A new approach to cyclic ordering of 2D orientations using ternary relation algebras ⋮ Constraint Satisfaction Problems with Infinite Templates ⋮ Querying temporal and spatial constraint networks in PTIME ⋮ EXPtime tableaux for ALC ⋮ REASONING WITH TOPOLOGICAL AND DIRECTIONAL SPATIAL INFORMATION ⋮ Computational Short Cuts in Infinite Domain Constraint Satisfaction ⋮ The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom ⋮ Combining topological and size information for spatial reasoning ⋮ Point algebras for temporal reasoning: Algorithms and complexity ⋮ Composing cardinal direction relations ⋮ The complexity of constraint satisfaction problems for small relation algebras ⋮ Generalized region connection calculus
