Logical Methods in Computer Science (Aug 2010)

Spatial logics with connectedness predicates

  • Roman Kontchakov,
  • Ian Pratt-Hartmann,
  • Frank Wolter,
  • Michael Zakharyaschev

DOI
https://doi.org/10.2168/LMCS-6(3:7)2010
Journal volume & issue
Vol. Volume 6, Issue 3

Abstract

Read online

We consider quantifier-free spatial logics, designed for qualitative spatial representation and reasoning in AI, and extend them with the means to represent topological connectedness of regions and restrict the number of their connected components. We investigate the computational complexity of these logics and show that the connectedness constraints can increase complexity from NP to PSpace, ExpTime and, if component counting is allowed, to NExpTime.

Keywords