Spatial logics with connectedness predicates

Abstract

We consider quantifier-free spatial logics, designed for qualitative spatial representation and reasoning in AI, and extend them with the means to represent topological connectedness of regions and restrict the number of their connected components. We investigate the computational complexity of these logics and show that the connectedness constraints can increase complexity from NP to PSpace, ExpTime and, if component counting is allowed, to NExpTime.

Some results of the paper were presented at LPAR 2008 and ECAI 2000

References in corpus (2)

• Combining Spatial and Temporal Logics: Expressiveness vs. Complexity
• Modal Logics of Topological Relations

Cited by in corpus (9)

• Model Checking Spatial Logics for Closure Spaces
• Topological Logics with Connectedness over Euclidean Spaces
• The Boolean Solution Problem from the Perspective of Predicate Logic -- Extended Version
• Representation theorems for extended contact algebras based on equivalence relations
• Algebraic Properties of Qualitative Spatio-Temporal Calculi
• A Game-Theoretic approach to Fault Diagnosis of Hybrid Systems
• On the Decidability of Connectedness Constraints in 2D and 3D Euclidean Spaces
• Undecidable First-Order Theories of Affine Geometries
• On Nondefinability of Interior-Connectedness via the Contact Relation