Our seminar series is free and available for anyone to attend. Unless otherwise stated, seminars take place on Wednesday afternoons at 2pm in the Kilburn Building during teaching season.

If you wish to propose a seminar speaker please contact Antoniu Pop.


RCC8: Connectedness and Euclidean Spaces

  • Speaker:   Dr.  Roman Kontchakov  (Birkbeck College, London)
  • Host:   Ian Pratt-Hartmann
  • 20th November 2013 at 14:00 in Lecture Theatre 1.4, Kilburn Building

RCC8 is a widely-studied formalism for describing topological arrangements of spatial regions, which are standardly understood as regular closed subsets of topological spaces. RCC8, however, lacks the means to say that a spatial region comprises a `single piece?. We study two types of constraints: one expresses connectedness of a region and the other connectedness of its interior. The languages are interpreted over the regular closed and the regular closed semi-linear sets in 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. In particular, (a) the connectedness predicate can distinguish between arbitrary and semi-linear regular closed subsets of the real line and the satisfiability problems is NP-complete in either case; (b) the interior-connectedness predicate can distinguish between regular closed subsets of the Euclidean plane and polygons and the satisfiability problem in the latter case is NP-complete (in the former case decidability is open); ? the connectedness predicate cannot distinguish between polygons and regular closed subsets of the Euclidean plane and the satisfiability problem is NP-complete; (d) in dimensions 3 and above, connectedness and interior-connectedness do not add anything interesting to RCC8.

(joint work with Ian Pratt-Hartmann and Michael Zakharyaschev)
▲ Up to the top