Complexity of Safety and coSafety Fragments of Linear Temporal Logic


  • Alessandro Artale Free University of Bozen-Bolzano
  • Luca Geatti University of Udine
  • Nicola Gigante Free University of Bozen-Bolzano
  • Andrea Mazzullo Free University of Bozen-Bolzano
  • Angelo Montanari University of Udine



KRR: Computational Complexity of Reasoning, KRR: Geometric, Spatial, and Temporal Reasoning, KRR: Other Foundations of Knowledge Representation & Reasoning


Linear Temporal Logic (LTL) is the de-facto standard temporal logic for system specification, whose foundational properties have been studied for over five decades. Safety and cosafety properties of LTL define notable fragments of LTL, where a prefix of a trace suffices to establish whether a formula is true or not over that trace. In this paper, we study the complexity of the problems of satisfiability, validity, and realizability over infinite and finite traces for the safety and cosafety fragments of LTL. As for satisfiability and validity over infinite traces, we prove that the majority of the fragments have the same complexity as full LTL, that is, they are PSPACE-complete. The picture is radically different for realizability: we find fragments with the same expressive power whose complexity varies from 2EXPTIME-complete (as full LTL) to EXPTIME-complete. Notably, for all cosafety fragments, the complexity of the three problems does not change passing from infinite to finite traces, while for all safety fragments the complexity of satisfiability (resp., realizability) over finite traces drops to NP-complete (resp., Πᴾ₂- complete).




How to Cite

Artale, A., Geatti, L., Gigante, N., Mazzullo, A., & Montanari, A. (2023). Complexity of Safety and coSafety Fragments of Linear Temporal Logic. Proceedings of the AAAI Conference on Artificial Intelligence, 37(5), 6236-6244.



AAAI Technical Track on Knowledge Representation and Reasoning