Recently, a hierarchy of spatio-temporal languages based on the prepositional temporal logic PTL and the spatial languages RCC-8, BRCC-8 and S4_u has been introduced. Although a number of results on their computational properties were obtained, the most important questions were left open. In this paper, we solve these problems and provide a clear picture of the balance between expressiveness and 'computational realisability' within the hierarchy.
展开▼
