Skip to Main content Skip to Navigation
Conference papers

Computational complexity of propositional linear temporal logics based on qualitative spatial or temporal reasoning

Abstract : We consider the language obtained by mixing the model of the regions and the propositional linear temporal logic. In particular, we propose alternative languages where the model of the regions is replaced by different forms of qualitative spatial or temporal reasoning. In these languages, qualitative formulas describe the movement and the relative positions of spatial or temporal entities in some spatial or temporal universe. This paper addresses the issue of the formal proof that for all forms of qualitative spatial and temporal reasoning such that consistent atomic constraint satisfaction problems are globally consistent, determining of any given qualitative formula whether it is satisfiable or not is PSPACE-complete.
Document type :
Conference papers
Complete list of metadata

https://hal-univ-artois.archives-ouvertes.fr/hal-03300320
Contributor : Fabien Delorme Connect in order to contact the contributor
Submitted on : Tuesday, July 27, 2021 - 9:39:25 AM
Last modification on : Thursday, September 9, 2021 - 3:10:01 PM

Links full text

Identifiers

Citation

Philippe Balbiani, Jean-François Condotta. Computational complexity of propositional linear temporal logics based on qualitative spatial or temporal reasoning. 4th International Workshop on Frontiers of Combining Systems (FroCoS 2002), 2002, Santa Margherita Ligure, Italy. pp.162-176, ⟨10.1007/3-540-45988-X_13⟩. ⟨hal-03300320⟩

Share

Metrics

Record views

31