TY - JOUR
AU - Artale, Alessandro
AU - Geatti, Luca
AU - Gigante, Nicola
AU - Mazzullo, Andrea
AU - Montanari, Angelo
PY - 2023/06/26
Y2 - 2024/04/15
TI - Complexity of Safety and coSafety Fragments of Linear Temporal Logic
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 37
IS - 5
SE - AAAI Technical Track on Knowledge Representation and Reasoning
DO - 10.1609/aaai.v37i5.25768
UR - https://ojs.aaai.org/index.php/AAAI/article/view/25768
SP - 6236-6244
AB - 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).
ER -