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.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:606867 |
| Date | January 2011 |
| Creators | Nenov, Yavor Neychev |
| Contributors | Pratt-Hartmann, Ian |
| Publisher | University of Manchester |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | https://www.research.manchester.ac.uk/portal/en/theses/computability-of-euclidean-spatial-logics(d6bd9f01-660b-43f7-9320-419697997c8b).html |
Page generated in 0.0643 seconds