Modal Logics of Topological Relations

Carsten LutzCarsten Lutz, Frank WolterFrank Wolter

Datei:LutzWolter-LTCS-04-05.ps.gz

Download

Carsten Lutz, Frank Wolter
Modal Logics of Topological Relations
Technical Report, Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology, volume LTCS-04-05, 2004. LTCS-Report

Details
Bibtex

KurzfassungAbstract
The eight topological RCC8 (or Egenhofer-Franzosa)-relations between spatial regions play a fundamental role in spatial reasoning, spatial and constraint databases, and geographical information systems. 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 RCC8-relations. The semantics is based on region spaces induced by standard topological spaces, in particular the real plane. We investigate the expressive power and computational complexity of the logics obtained in this way. It turns our that, similar to Halpern and Shoham's logic, the expressive power is rather natural, but the computational behavior is problematic: topological modal logics are usually undecidable and often not even recursively enumerable. This even holds if we restrict ourselves to classes of finite region spaces or to substructures of region spaces induced by topological spaces. We also analyze modal logics based on the set of RCC5-relations, with similar results.
Bemerkung: Note: See http://lat.inf.tu-dresden.de/research/reports.html.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@techreport{ LutzWolter-LTCS-04-05,
  address = {Germany},
  author = {C. {Lutz} and F. {Wolter}},
  institution = {Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology},
  note = {See http://lat.inf.tu-dresden.de/research/reports.html.},
  number = {LTCS-04-05},
  title = {Modal Logics of Topological Relations},
  type = {LTCS-Report},
  year = {2004},
}