Combining Spatial and Temporal Logics: Expressiveness vs. Complexity
Abstract
In this paper, we construct and investigate a hierarchy of spatio-temporal formalisms that result from various combinations of propositional spatial and temporal logics such as the propositional temporal logic PT L, the spatial logics RCC-8, BRCC-8, S4u and their fragments. The obtained results give a clear picture of the trade-off between expressiveness and 'computational realisability' within the hierarchy. We demonstrate how different combining principles as well as spatial and temporal primitives can produce NP-, PSPACE-, EXPSPACE-, 2EXPSPACE-complete, and even undecidable spatio-temporal logics out of components that are at most NP- or PSPACE-complete.
Cite
Text
Gabelaia et al. "Combining Spatial and Temporal Logics: Expressiveness vs. Complexity." Journal of Artificial Intelligence Research, 2005. doi:10.1613/JAIR.1537Markdown
[Gabelaia et al. "Combining Spatial and Temporal Logics: Expressiveness vs. Complexity." Journal of Artificial Intelligence Research, 2005.](https://mlanthology.org/jair/2005/gabelaia2005jair-combining/) doi:10.1613/JAIR.1537BibTeX
@article{gabelaia2005jair-combining,
title = {{Combining Spatial and Temporal Logics: Expressiveness vs. Complexity}},
author = {Gabelaia, David and Kontchakov, Roman and Kurucz, Ágnes and Wolter, Frank and Zakharyaschev, Michael},
journal = {Journal of Artificial Intelligence Research},
year = {2005},
pages = {167-243},
doi = {10.1613/JAIR.1537},
volume = {23},
url = {https://mlanthology.org/jair/2005/gabelaia2005jair-combining/}
}