Modal Logics of Topological Relations

Carsten LutzCarsten Lutz, Frank WolterFrank Wolter

Datei:LutzWolterAiML04.ps.gz

Download

Carsten Lutz, Frank Wolter
Modal Logics of Topological Relations
Proceedings of Advances in Modal Logics 2004, 2004

Details
Bibtex

KurzfassungAbstract
We introduce a family of modal logics that are interpreted in domains consisting of regions in topological spaces, in particular the real plane. The underlying modal language has 8 operators interpreted by the RCC8 (or Egenhofer-Franzosa)-relations between regions. The following results on the expressive power and computational complexity of the resulting modal systems are obtained: they are expressively complete for the two-variable fragment of first-order logic, and are usually undecidable and often not even recursively enumerable. This also holds if we interpret our language in the class of all (finite) substructures of full region spaces. If interpreted in region spaces consisting of intervals in the real line, our results significantly extend undecidability results of Halpern and Shoham in that we prove the undecidability of interval temporal logic over the class of all substructures of all full interval structures. We also analyze modal logics based on the set of RCC5-relations which are more coarse than the RCC8 relations.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ Lutz-Wolter-AiML-04,
  author = {C. {Lutz} and F. {Wolter}},
  booktitle = {Proceedings of Advances in Modal Logics 2004},
  title = {Modal Logics of Topological Relations},
  year = {2004},
}