On the decidability of connectedness constraints in 2D and 3D euclidean spaces

Roman Kontchakov; Yavor Nenov; Ian Pratt-Hartmann; Michael Zakharyaschev

doi:10.5591/978-1-57735-516-8/IJCAI11-165

On the decidability of connectedness constraints in 2D and 3D euclidean spaces

Roman Kontchakov, Yavor Nenov, Ian Pratt-Hartmann, Michael Zakharyaschev

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

Abstract

We investigate (quantifier-free) spatial constraint languages with equality, contact and connectedness predicates, as well as Boolean operations on regions, interpreted over low-dimensional Euclidean spaces. We show that the complexity of reasoning varies dramatically depending on the dimension of the space and on the type of regions considered. For example, the logic with the interior-connectedness predicate (and without contact) is undecidable over polygons or regular closed sets in ℝ2, EXPTIME-complete over polyhedra in ℝ3, and NP-complete over regular closed sets in ℝ3.

Original language	English
Title of host publication	IJCAI International Joint Conference on Artificial Intelligence\|IJCAI Int. Joint Conf. Artif. Intell.
Publisher	AAAI Press
Pages	957-962
Number of pages	5
ISBN (Print)	9781577355120
DOIs	https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-165
Publication status	Published - 2011
Event	22nd International Joint Conference on Artificial Intelligence, IJCAI 2011 - Barcelona, Catalonia Duration: 1 Jul 2011 → …

Conference

Conference	22nd International Joint Conference on Artificial Intelligence, IJCAI 2011
City	Barcelona, Catalonia
Period	1/07/11 → …

Keywords

Logic
Topology
Artificial Intelligence
Spatial Logic

Access to Document

10.5591/978-1-57735-516-8/IJCAI11-165

Cite this

@inproceedings{ad00585e237b4f9f882b49817c5d6dd4,

title = "On the decidability of connectedness constraints in 2D and 3D euclidean spaces",

abstract = "We investigate (quantifier-free) spatial constraint languages with equality, contact and connectedness predicates, as well as Boolean operations on regions, interpreted over low-dimensional Euclidean spaces. We show that the complexity of reasoning varies dramatically depending on the dimension of the space and on the type of regions considered. For example, the logic with the interior-connectedness predicate (and without contact) is undecidable over polygons or regular closed sets in ℝ2, EXPTIME-complete over polyhedra in ℝ3, and NP-complete over regular closed sets in ℝ3.",

keywords = "Logic, Topology, Artificial Intelligence, Spatial Logic",

author = "Roman Kontchakov and Yavor Nenov and Ian Pratt-Hartmann and Michael Zakharyaschev",

note = "U.K. EPSRC grants EP/E034942/1 and EP/E035248/1.; 22nd International Joint Conference on Artificial Intelligence, IJCAI 2011 ; Conference date: 01-07-2011",

year = "2011",

doi = "10.5591/978-1-57735-516-8/IJCAI11-165",

language = "English",

isbn = "9781577355120",

pages = "957--962",

booktitle = "IJCAI International Joint Conference on Artificial Intelligence|IJCAI Int. Joint Conf. Artif. Intell.",

publisher = "AAAI Press",

address = "United States",

}

Kontchakov, R, Nenov, Y, Pratt-Hartmann, I & Zakharyaschev, M 2011, On the decidability of connectedness constraints in 2D and 3D euclidean spaces. in IJCAI International Joint Conference on Artificial Intelligence|IJCAI Int. Joint Conf. Artif. Intell.. AAAI Press, pp. 957-962, 22nd International Joint Conference on Artificial Intelligence, IJCAI 2011, Barcelona, Catalonia, 1/07/11. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-165

On the decidability of connectedness constraints in 2D and 3D euclidean spaces. / Kontchakov, Roman; Nenov, Yavor; Pratt-Hartmann, Ian et al.
IJCAI International Joint Conference on Artificial Intelligence|IJCAI Int. Joint Conf. Artif. Intell.. AAAI Press, 2011. p. 957-962.

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On the decidability of connectedness constraints in 2D and 3D euclidean spaces

AU - Kontchakov, Roman

AU - Nenov, Yavor

AU - Pratt-Hartmann, Ian

AU - Zakharyaschev, Michael

N1 - U.K. EPSRC grants EP/E034942/1 and EP/E035248/1.

PY - 2011

Y1 - 2011

N2 - We investigate (quantifier-free) spatial constraint languages with equality, contact and connectedness predicates, as well as Boolean operations on regions, interpreted over low-dimensional Euclidean spaces. We show that the complexity of reasoning varies dramatically depending on the dimension of the space and on the type of regions considered. For example, the logic with the interior-connectedness predicate (and without contact) is undecidable over polygons or regular closed sets in ℝ2, EXPTIME-complete over polyhedra in ℝ3, and NP-complete over regular closed sets in ℝ3.

AB - We investigate (quantifier-free) spatial constraint languages with equality, contact and connectedness predicates, as well as Boolean operations on regions, interpreted over low-dimensional Euclidean spaces. We show that the complexity of reasoning varies dramatically depending on the dimension of the space and on the type of regions considered. For example, the logic with the interior-connectedness predicate (and without contact) is undecidable over polygons or regular closed sets in ℝ2, EXPTIME-complete over polyhedra in ℝ3, and NP-complete over regular closed sets in ℝ3.

KW - Logic

KW - Topology

KW - Artificial Intelligence

KW - Spatial Logic

U2 - 10.5591/978-1-57735-516-8/IJCAI11-165

DO - 10.5591/978-1-57735-516-8/IJCAI11-165

M3 - Conference contribution

SN - 9781577355120

SP - 957

EP - 962

BT - IJCAI International Joint Conference on Artificial Intelligence|IJCAI Int. Joint Conf. Artif. Intell.

PB - AAAI Press

T2 - 22nd International Joint Conference on Artificial Intelligence, IJCAI 2011

Y2 - 1 July 2011

ER -

On the decidability of connectedness constraints in 2D and 3D euclidean spaces

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this