In April 2016 Manchester eScholar was replaced by the University of Manchester’s new Research Information Management System, Pure. In the autumn the University’s research outputs will be available to search and browse via a new Research Portal. Until then the University’s full publication record can be accessed via a temporary portal and the old eScholar content is available to search and browse via this archive.

Related resources

Search for item elsewhere

University researcher(s)

Academic department(s)

Computability of Euclidean Spatial Logics

Nenov, Yavor Neychev

[Thesis]. Manchester, UK: The University of Manchester; 2011.

Access to files

FULL-TEXT.PDF (pdf)

Abstract

In the last two decades, qualitative spatial representation and reasoning, and in particular spatial logics, have been the subject of an increased interest from the Artificial Intelligence community. By a spatial logic, we understand a formal language whose variables range over subsets of a fixed topological space, called regions, and whose non-logical primitives have fixed geometric meanings. A spatial logic for reasoning about regions in a Euclidean space is called a Euclidean spatial logic. We consider first-order and quantifier-free Euclidean spatial logics with primitives for topological relations and operations, the property of convexity and the ternary relation of being closer-than. We mainly focus on the computational properties of such logics, but we also obtain interesting model-theoretic results.We provide a systematic overview of the computational properties of firstorder Euclidean spatial logics and fill in some of the gaps left by the literature. We establish upper complexity bounds for the (undecidable) theories of logics based on Euclidean spaces of dimension greater than one, which yields tight complexity bounds for all but two of these theories. In contrast with these undecidability results, we show that the topological theories based on one-dimensional Euclidean space are decidable, but non-elementary. We also study the computational properties of quantifier-free Euclidean spatial logics, and in particular those able to express the property of connectedness. It is known that when variables range over regions in the Euclidean plane, one can find formulas in these languages satisfiable only by regions with infinitely many connected components. Using this result, we show that the corresponding logics are undecidable. Further, we show that there exist formulas that are satisfiable in higher-dimensional Euclidean space, but only by regions with infinitely many connected components. We finish by outlining how the insights gained from this result were used (by another author) to show the undecidability of certain quantifier-free Euclidean spatial logics in higher dimensions.