Spatial logics with connectedness predicates

Roman Kontchakov; Ian Pratt-Hartmann; Frank Wolter; Michael Zakharyaschev

doi:10.2168/LMCS-6(3:5)2010

Spatial logics with connectedness predicates

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

Research output: Contribution to journal › Article › peer-review

Abstract

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. © R. Kontchakov, I. Pratt-Hartmann, F. Wolter, and M. Zakharyaschev.

Original language	English
Pages (from-to)	1-43
Number of pages	42
Journal	Logical Methods in Computer Science
Volume	6
Issue number	3
DOIs	https://doi.org/10.2168/LMCS-6(3:5)2010
Publication status	Published - 2010

Keywords

Computational complexity
Connectedness
Spatial logic
Topological space

Access to Document

10.2168/LMCS-6(3:5)2010

http://arxiv.org/PS_cache/arxiv/pdf/1003/1003.5399v2.pdf

Cite this

@article{6a6d2ac4b43b400d8bdd1e2222096651,

title = "Spatial logics with connectedness predicates",

abstract = "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. {\textcopyright} R. Kontchakov, I. Pratt-Hartmann, F. Wolter, and M. Zakharyaschev.",

keywords = "Computational complexity, Connectedness, Spatial logic, Topological space",

author = "Roman Kontchakov and Ian Pratt-Hartmann and Frank Wolter and Michael Zakharyaschev",

year = "2010",

doi = "10.2168/LMCS-6(3:5)2010",

language = "English",

volume = "6",

pages = "1--43",

journal = "Logical Methods in Computer Science",

issn = "1860-5974",

publisher = "International Federation for Computational Logic",

number = "3",

}

TY - JOUR

T1 - Spatial logics with connectedness predicates

AU - Kontchakov, Roman

AU - Pratt-Hartmann, Ian

AU - Wolter, Frank

AU - Zakharyaschev, Michael

PY - 2010

Y1 - 2010

N2 - 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. © R. Kontchakov, I. Pratt-Hartmann, F. Wolter, and M. Zakharyaschev.

AB - 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. © R. Kontchakov, I. Pratt-Hartmann, F. Wolter, and M. Zakharyaschev.

KW - Computational complexity

KW - Connectedness

KW - Spatial logic

KW - Topological space

U2 - 10.2168/LMCS-6(3:5)2010

DO - 10.2168/LMCS-6(3:5)2010

M3 - Article

SN - 1860-5974

VL - 6

SP - 1

EP - 43

JO - Logical Methods in Computer Science

JF - Logical Methods in Computer Science

IS - 3

ER -

Spatial logics with connectedness predicates

Abstract

Keywords

Access to Document

Fingerprint

Cite this