# Spatio-temporal representation and reasoning: a computational perspective

Michael Zakharyaschev King's College London 4pm, Tuesday 1 May 2001 Room 2511, JCMB, King's Buildings

The aim of the talk is to demonstrate how combinations of some standard propositional modal logics can be used for qualitative spatio-temporal representation and reasoning. The basic spatial formalism we begin with is the fra gment RCC-8 of the region connection calculus RCC of Randell, Cui, and Cohn. We extend it by applications of Boolean operators to spatial regions, which it possible to distinguish between Euclidean and discrete topological spaces. Then we embed the resulting language BRCC-8 into (a fragment of) Lewis's modal logic S4 enriched with the universal modality, study the structure of Kripke models for formulas in this language, and establish the computational complexity of the satisfiability problem. To construct formalisms capable of representing movements of spatial regions in time, we combine BRCC-8 with three types of temporal logics: a fragment of Allen's interval calculus, a point-based propositional temporal logic (over various flows of time), and Ockhamist branching time logic. We illustrate the expressive power of the resulting spatio-temporal hybrids and indicate their computational complexity.