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.
Published Date: May 2003
Registration: ISBN 978-1-57735-177-1
Copyright: Published by The AAAI Press, Menlo Park, California.