Modal Logics of Topological Relations

C. LutzC. Lutz, F. WolterF. Wolter

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

Download

C. Lutz, F. 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},
}