Kontchakov, Roman and Pratt-Hartmann, Ian and Wolter, Frank and Zakharyaschev, Michael - Spatial logics with connectedness predicates

lmcs:1229 - Logical Methods in Computer Science, August 18, 2010, Volume 6, Issue 3
Spatial logics with connectedness predicates

Authors: Kontchakov, Roman and Pratt-Hartmann, Ian and Wolter, Frank and Zakharyaschev, Michael

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.


Source : oai:arXiv.org:1003.5399
DOI : 10.2168/LMCS-6(3:7)2010
Volume: Volume 6, Issue 3
Published on: August 18, 2010
Submitted on: June 17, 2009
Keywords: Computer Science - Logic in Computer Science,F.4.1, I.2.4


Share

Consultation statistics

This page has been seen 40 times.
This article's PDF has been downloaded 132 times.