- Ian Pratt-Hartmann, Department of Computer Science, Manchester University
- Michael Zakharyaschev, Department of Computer Science and Information Systems, Birkbeck, University of London

- Roman Kontchakov, Department of Computer Science and Information Systems, Birkbeck, University of London
- Yavor Nenov, Department of Computer Science, Manchester University
- Adam Trybus, Department of Computer Science, Manchester University

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.

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.

language | RCP(R) | =^{?} |
RC(R) | RCP(R^{2}) |
=^{?} |
RC(R^{2}) |
RCP(R^{3}) |
=^{?} |
RC(R^{3}) |
=^{?} |
RC |
---|---|---|---|---|---|---|---|---|---|---|---|

RCC8 | NP | ||||||||||

RCC8c^{0} |
NP | ≠ | NP | NP | NP | ||||||

RCC8c | NP | ||||||||||

B | NP | ||||||||||

Bc^{0} |
NP | r.e. | ≠ | ≥ r.e. | ExpTime | ≠ | NP | ||||

Bc | r.e. | ≠ | ≥ r.e. | ≥ ExpTime | ? | ≥ ExpTime | ? | ExpTime | |||

C | PSpace | ≠ | NP | ||||||||

Cc^{0} |
PSpace | ≠ | PSpace | r.e. | ≠ | ≥ r.e. | ≥ ExpTime | ≠ | ≥ ExpTime | ≠ | ExpTime |

Cc | r.e. | ≠ | ≥ r.e. | ≥ ExpTime | ? | ≥ ExpTime | ? | ExpTime |

- Y. 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). - A. Trybus.
*An Axiom System for a Spatial Logic with Convexity*. In Proceedings of 19th European Conference on Artificial Intelligence (ECAI 2010). -
R. Kontchakov, I. Pratt-Hartmann, F. Wolter and M. Zakharyaschev.
*Spatial logics with connectedness predicates*. To appear in Logical Methods in Computer Science. - 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. -
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. - 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. - 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). -
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. -
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. -
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.

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