On the Computational Complexity of Spatio-Temporal Logics

David Gabelaia, Roman Kontchakov, Agi Kurucz, Frank Wolter, and Michael Zakharyaschev

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.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.