COMPLEXITY OF A QUALITATIVE SPATIO-TEMPORAL LOGIC

In this paper we consider the problem of determining the complexity of a qualitative spatio-temporal language introduced by Wolter and Zakharyaschev, that combines the model of the regions RCC5 to the propositional linear temporal logic. By introducing the concept of f -states and by making use of the constraint satisfaction problems techniques, we show that the satisfiability problem of any formula of this language is PSPACE-complete.