Computational Complexity of Spatio-Temporal Logics
David Gabelaia, Roman Kontchakov, Agi Kurucz, Frank Wolter, Michael Zakharyaschev · BIROn (Birkbeck, University of London) · 2003
Recently, a hierarchy of spatio-temporal languages based on the propositional temporal logic PTL and the spatial languages RCC-8, BRCC-8 and S4u 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.