On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus

Cited In (50)

GNet: a generalized network model and its applications in qualitative spatial reasoning
Hardness of Network Satisfaction for Relation Algebras with Normal Representations
Generalized Qualitative Spatio-Temporal Reasoning: Complexity and Tableau Method
A condensed semantics for qualitative spatial reasoning about oriented straight line segments
Reasoning about visibility
On the consistency of cardinal direction constraints
Querying incomplete information in RDF with SPARQL
Computational Short Cuts in Infinite Domain Constraint Satisfaction
Qualitative constraint satisfaction problems: an extended framework with landmarks
A logic for metric and topology
Reasoning with topological and directional spatial information
A tableau algorithm for description logics with concrete domains and general TBoxes
Constants and finite unary relations in qualitative constraint reasoning
Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
Drawing interactive Euler diagrams from region connection calculus specifications
Maximal infinite-valued constraint languages
On standard models of fuzzy region connection calculus
The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
A Topological Constraint Language with Component Counting
Drawing Euler Diagrams from Region Connection Calculus Specifications with Local Search
Solving infinite-domain CSPs using the patchwork property
A semi-dynamical approach for solving qualitative spatial constraint satisfaction problems
On topological consistency and realization
EXPtime tableaux for ALC
A new approach to cyclic ordering of 2D orientations using ternary relation algebras
Spatial reasoning with \(\mathcal{RCC} 8\) and connectedness constraints in Euclidean spaces
On the Computational Complexity of Spatial Logics with Connectedness Constraints
Relation algebras and their application in temporal and spatial reasoning
On redundant topological constraints
Incremental qualitative temporal reasoning: Algorithms for the point algebra and the ORD-Horn class
RCC8 binary constraint network can be consistently extended
Design and comparison of lattices of topological relations for spatial representation and reasoning
Realizing RCC8 networks using convex regions
Reasoning about cardinal directions between extended objects: the NP-hardness result
Fuzzy region connection calculus: An interpretation based on closeness
Disjunctions, independence, refinements
Composing cardinal direction relations
Spatial reasoning in a fuzzy region connection calculus
Point algebras for temporal reasoning: Algorithms and complexity
Reasoning about cardinal directions between extended objects
Line-based affine reasoning in Euclidean plane
Title not available (Why is that?)
General lower bounds and improved algorithms for infinite-domain CSPs
Relational representation theorems for extended contact algebras
Constraint Satisfaction Problems with Infinite Templates
A Canonical Model of the Region Connection Calculus
Generalized region connection calculus
The complexity of constraint satisfaction problems for small relation algebras
Combining topological and size information for spatial reasoning
Querying temporal and spatial constraint networks in PTIME

This page was built for publication: On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1285670)