Computer Science – Logic in Computer Science
Scientific paper
2006-05-15
LMCS 2 (2:5) 2006
Computer Science
Logic in Computer Science
Scientific paper
10.2168/LMCS-2(2:5)2006
Logical formalisms for reasoning about relations between spatial regions play a fundamental role in geographical information systems, spatial and constraint databases, and spatial reasoning in AI. In analogy with Halpern and Shoham's modal logic of time intervals based on the Allen relations, we introduce a family of modal logics equipped with eight modal operators that are interpreted by the Egenhofer-Franzosa (or RCC8) relations between regions in topological spaces such as the real plane. We investigate the expressive power and computational complexity of logics obtained in this way. It turns out that our modal logics have the same expressive power as the two-variable fragment of first-order logic, but are exponentially less succinct. The complexity ranges from (undecidable and) recursively enumerable to highly undecidable, where the recursively enumerable logics are obtained by considering substructures of structures induced by topological spaces. As our undecidability results also capture logics based on the real line, they improve upon undecidability results for interval temporal logics by Halpern and Shoham. We also analyze modal logics based on the five RCC5 relations, with similar results regarding the expressive power, but weaker results regarding the complexity.
Lutz Carsten
Wolter Frank
No associations
LandOfFree
Modal Logics of Topological Relations 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 Modal Logics of Topological Relations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Modal Logics of Topological Relations will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-621341