Topological logics with connectedness over Euclidean spaces

DOI10.1145/2480759.2480765MaRDI QIDQ2946698zbMATH OpenOpenAlexWikidataFDO

Authors Roman Kontchakov, Yavor Nenov, Ian Pratt-Hartmann, Michael Zakharyaschev

Publication date 17 September 2015

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.4034

zbMATH Keywords

connectednessEuclidean spacesqualitative spatial reasoningtopology

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27) Knowledge representation (68T30)

Abstract: We consider the quantifier-free languages, Bc and Bc0, obtained by augmenting the signature of Boolean algebras with a unary predicate representing, respectively, the property of being connected, and the property of having a connected interior. These languages are interpreted over the regular closed sets of n-dimensional Euclidean space (n greater than 1) and, additionally, over the regular closed polyhedral sets of n-dimensional Euclidean space. The resulting logics are examples of formalisms that have recently been proposed in the Artificial Intelligence literature under the rubric "Qualitative Spatial Reasoning." We prove that the satisfiability problem for Bc is undecidable over the regular closed polyhedra in all dimensions greater than 1, and that the satisfiability problem for both languages is undecidable over both the regular closed sets and the regular closed polyhedra in the Euclidean plane. However, we also prove that the satisfiability problem for Bc0 is NP-complete over the regular closed sets in all dimensions greater than 2, while the corresponding problem for the regular closed polyhedra is ExpTime-complete. Our results show, in particular, that spatial reasoning over Euclidean spaces is much harder than reasoning over arbitrary topological spaces.

Recommendations

• Spatial logics with connectedness predicates
• Topology, connectedness, and modal logic
• Spatial reasoning with \(\mathcal{RCC} 8\) and connectedness constraints in Euclidean spaces
• On the computability of region-based Euclidean logics
• On the Computational Complexity of Spatial Logics with Connectedness Constraints

Cited in

(11)

• Relational representation theorems for extended contact algebras
• Extended contact algebras and internal connectedness
• Drawing interactive Euler diagrams from region connection calculus specifications
• Spatial logics with connectedness predicates
• Logics of space with connectedness predicates: complete axiomatizations
• Drawing Euler diagrams from region connection calculus specifications with local search
• Topology, connectedness, and modal logic
• Contact logic is finitary for unification with constants
• On the computability of region-based Euclidean logics
• Decision algorithms for elementary topology I. Topological syllogistics with set and map constructs, connectedness, and cardinality comparison
• Spatial reasoning with \(\mathcal{RCC} 8\) and connectedness constraints in Euclidean spaces

This page was built for publication: Topological logics with connectedness over Euclidean spaces

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