Computational Logic of Euclidean Spaces

Research Team

Principal Investigators

Research Staff

Spatial KR&R background

Much of the spatial information we encounter in everyday situations is qualitative, rather than quantitative, in character. Thus, for instance, we may know which of two objects is the closer without measuring their distances; we may perceive an object to be convex without being able to describe its precise shape; or we may identify two areas on a map as sharing a boundary without knowing the equation that describes it.

This observation has prompted the development, within Artificial Intelligence, of various formalisms for reasoning with qualitative spatial information. Although substantial progress has been made in analysing the mathematical foundations and computational characteristics of such formalisms, most of that progress has centred on systems for reasoning about highly abstract problems concerning (typically) arbitrary regions in very general classes of topological spaces.

But of course, the geometrical entities of interest for practical problems are not arbitrary subsets of general topological spaces, but rather mathematically very well-behaved regions of 2 and 3-dimensional Euclidean space. Moreover, the geometrical properties and relations these problems are concerned with are typically not merely topological, but rather affine or even metric in character. Together, these factors severely limit the practical usefulness of current qualitative spatial reasoning formalisms. Overcoming this limitation represents an exciting mathematical and computational challenge.

Project Aims

We propose to meet this challenge by drawing on developments in mathematical logic, geometrical topology, and algebraic geometry that the spatial reasoning literature in AI has so far failed fully to exploit.

Specifically, we are investigating the computational properties of spatial and spatio-temporal logics for reasoning about mathematically well-behaved regions of 2- and 3-dimensional Euclidean space. We are developing and implementing algorithms for reasoning with these logics. This investigation will illuminate the important relationships between hitherto separate research traditions, provide new techniques for addressing challenging problems in the mathematical geometry, and yield logics of direct relevance to practical spatial reasoning problems.

Summary of Complexity Results

language RCP(R) =? RC(R) RCP(R2) =? RC(R2) RCP(R3) =? RC(R3) =? RC
RCC8 NP
RCC8c0 NP ≠ NP NP NP
RCC8c NP
B NP
Bc0 NP r.e. ≠ ≥ r.e. ExpTime ≠ NP
Bc r.e. ≠ ≥ r.e. ≥ ExpTime ? ≥ ExpTime ? ExpTime
C PSpace ≠ NP
Cc0 PSpace ≠ PSpace r.e. ≠ ≥ r.e. ≥ ExpTime ≠ ≥ ExpTime ≠ ExpTime
Cc r.e. ≠ ≥ r.e. ≥ ExpTime ? ≥ ExpTime ? ExpTime

Publications

  1. pdfY. Nenov and I. Pratt-Hartmann. On the Computability of Region-Based Spatial Logics. In Proceedings of 19th EACSL Annual Conferences on Computer Science Logic (CSL 2010).
  2. A. Trybus. An Axiom System for a Spatial Logic with Convexity. In Proceedings of 19th European Conference on Artificial Intelligence (ECAI 2010).
  3. pdf R. Kontchakov, I. Pratt-Hartmann, F. Wolter and M. Zakharyaschev. Spatial logics with connectedness predicates. To appear in Logical Methods in Computer Science.
  4. pdf M. Sheremet, F. Wolter and M. Zakharyaschev. A modal logic framework for reasoning about comparative distances and topology. Annals of Pure and Applied Logic, 161(4):534-559, January 2010.
  5. pdf R. Kontchakov, I. Pratt-Hartmann and M. Zakharyaschev. Interpreting Topological Logics over Euclidean Spaces. In F. Lin, U. Sattler and M. Truszczynski, editors, Proceeding of KR (Toronto, Canada, May 9-13), AAAI Press, 2010.
  6. pdf Y. Nenov. A Note on the Theory of Complete Mereotopologies. In Proceedings of the 14th Student Session of ESSLLI (Bordeaux, July 20-31, 2009), pp. 12-20, 2009.
  7. pdf R. Kontchakov, I. Pratt-Hartmann and M. Zakharyaschev. Topological logics over Euclidean spaces. In Proceedings of Topology, Algebra and Categories in Logic, TACL 2009 (Amsterdam, July 7-11, 2009).
  8. pdf R. Kontchakov, I. Pratt-Hartmann, F. Wolter and M. Zakharyaschev. On the computational complexity of spatial logics with connectedness constraints. In I. Cervesato, H. Veith and A. Voronkov, editors, Proceedings of LPAR 2008 (Doha, Qatar, November 22-27, 2008), LNAI vol. 5330, pp. 574-589. Springer 2008.
  9. ps pdf R. Kontchakov, I. Pratt-Hartmann, F. Wolter and M. Zakharyaschev. Topology, connectedness, and modal logic. In C. Areces and R. Goldblatt, editors, Advances in Modal Logic, vol. 7, pp. 151-176. College Publications, London, 2008.
  10. ps R. Kontchakov, A. Kurucz, F. Wolter and M. Zakharyaschev. Spatial logic + temporal logic = ? In M. Aiello, I. Pratt-Hartmann and J. van Benthem, editors, Handbook of Spatial Logics, pp. 497-564. Springer, 2007.

Selected presentations

  1. pdf24 August 2010, Y. Nenov, CSL, Brno, Czech Republic: On the Computability of Euclidean Logics
  2. pdfMay 2010, I. Pratt-Hartmann, CSE Departmental Colloquium, Buffalo: The Computational Complexity of Topological Logics
  3. pdfMarch 2010, I. Pratt-Hartmann, Schloß Dagstuhl: Survey of Spatial Logics
  4. pdf26 Jan 2010, R. Kontchakov, ALCOP workshop, London: Topological logics over Euclidean spaces
  5. pdf2 Aug 2009, R. Kontchakov, Logic Colloquium, Athens: Topological logics with connectedness predicates
  6. pdf15 July 2009, I. Pratt-Hartmann, Summer Conference on Topology and its Applications, Brno: Computational Complexity of Topological Logics
  7. pdf5 Jun 2008, R. Kontchakov, Topological Methods in Logic, Tbilisi: On the computational complexity of spatial logics with connectedness constraints
  8. pdf11 January 2008, I. Pratt-Hartmann, Symposium on Logic and Physics, Utrecht: From Points to Regions (and back again)
  9. pdfNovember 2007, I. Pratt-Hartmann, Handbook of Spatial Logics Launch, Groningen: Geometrical Logics
  10. pdf5 Aug 2007, I. Pratt-Hartmann, TANCL 2007, Oxford: Mereotopology: a Survey
  11. pdf5 Aug 2007, R. Kontchakov, TANCL 2007, Oxford: On dynamic topological logics