LTLf+ and PPLTL+: Extending LTLf and PPLTL to Infinite Traces
Preprint
Abstract
We introduce LTLf+ and PPLTL+, two logics to express properties of infinite traces, that are based on the linear-time temporal logics LTLf and PPLTL on finite traces. LTLf+/PPLTL+ use levels of Manna and Pnueli's LTL safety-progress hierarchy, and thus have the same expressive power as LTL. However, they also retain a crucial characteristic of the reactive synthesis problem for the base logics: the game arena for strategy extraction can be derived from deterministic finite automata (DFA). Consequently, these logics circumvent the notorious difficulties associated with determinizing infinite trace automata, typical of LTL reactive synthesis. We present DFA-based synthesis techniques for LTLf+/PPLTL+, and show that synthesis is 2EXPTIME-complete for LTLf+ (matching LTLf) and EXPTIME-complete for PPLTL+ (matching PPLTL). Notably, while PPLTL+ retains the full expressive power of LTL, reactive synthesis is EXPTIME-complete instead of 2EXPTIME-complete. The techniques are also adapted to optimally solve satisfiability, validity, and model-checking, to get EXPSPACE-complete for LTLf+ (extending a recent result for the guarantee level using LTLf), and PSPACE-complete for PPLTL+.Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- Towards the exact complexity of realizability for Safety LTLJournal of Logical and Algebraic Methods in Programming, 2024
- Model Checking Strategies from Synthesis over Finite Traces2023
- Oink: An Implementation and Evaluation of Modern Parity Game Solvers2018
- Supervisory control and reactive synthesis: a comparative introductionDiscrete Event Dynamic Systems, 2016
- Non-Markovian control in the Situation CalculusArtificial Intelligence, 2011
- Deterministic planning in the fifth international planning competition: PDDL3 and experimental evaluation of the plannersArtificial Intelligence, 2009
- Weak, strong, and strong cyclic planning via symbolic model checkingArtificial Intelligence, 2003
- Temporal Verification of Reactive Systems1995
- Characterization of temporal property classes1992
- Modalities for model checking: branching time logic strikes backScience of Computer Programming, 1987