Computer Science – Logic in Computer Science
Scientific paper
2011-10-18
Computer Science
Logic in Computer Science
Scientific paper
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.
Kontchakov Roman
Nenov Yavor
Pratt-Hartmann Ian
Zakharyaschev Michael
No associations
LandOfFree
Topological Logics with Connectedness over Euclidean Spaces does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Topological Logics with Connectedness over Euclidean Spaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Topological Logics with Connectedness over Euclidean Spaces will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-292484