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

lmcs:1229 - Logical Methods in Computer Science, August 18, 2010, Volume 6, Issue 3 - https://doi.org/10.2168/LMCS-6(3:7)2010
Spatial logics with connectedness predicatesArticle

Authors: Roman Kontchakov ; Ian Pratt-Hartmann ; Frank Wolter ; Michael Zakharyaschev ORCID

    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.

    https://doi.org/10.2168/LMCS-6(3:7)2010
    Source: arXiv.org:1003.5399
    Volume: Volume 6, Issue 3
    Published on: August 18, 2010
    Imported on: June 17, 2009
    Keywords: Computer Science - Logic in Computer Science,F.4.1, I.2.4
    Licence: arXiv.org - Non-exclusive license to distribute

    Classifications

    Mathematics Subject Classification 20201
    Sources:
    • [1] zbMATH Open.

    12 Documents citing this article

    Share and export

    Consultation statistics

    This page has been seen 1594 times.
    This article's PDF has been downloaded 663 times.