Introduction
Linear Temporal Logic over Finite Traces (LTLf) is a powerful formalism for specifying behaviors in domains such as formal verification and robotics. To execute these specifications, they must typically be converted into a Deterministic Finite-state Automaton (DFA). However, this translation is computationally intensive, with a worst-case double-exponential growth in the size of the DFA relative to the formula size. While compositional methods have been developed to mitigate this by breaking formulas into sub-components, the efficiency of the initial decomposition phase remains a critical bottleneck.
Methodology: The Swift Tool
This paper introduces Swift, a tool implemented in C++ designed to optimize the decomposition of LTLf formulas. Swift focuses on the structure of the Abstract Syntax Tree (AST) before the composition phase begins. Traditional tools often process the literal syntax of a formula, which can lead to redundant sub-formulas and unnecessary DFA operations.
Swift employs a bottom-up traversal combined with syntactic-equivalence rules to simplify the AST. By rearranging the logical structure, Swift minimizes the number of edges in the decomposition graph, thereby reducing the total number of expensive composition and minimization operations required.
For instance, a formula of the form $(\psi \lor \phi_1) \land (\psi \lor \phi_2) \land \dots \land (\psi \lor \phi_k)$ would normally require $2k - 1$ compositions. Swift recognizes the semantic equivalence to $\psi \lor (\phi_1 \land \phi_2 \land \dots \land \phi_k)$, which requires only $k$ compositions.
Experimental Evaluation
Swift was evaluated against state-of-the-art tools Lisa and Lydia using benchmarks from the SYNTCOMP 2023 LTLf synthesis track. The evaluation focused on two primary sets: the Nim benchmarks, characterized by intermediate sub-formulas that generate massive DFAs, and the Counter/Dcounter benchmarks, which represent formulas with minimal sub-formula repetition.
Results
On the Nim benchmarks, Swift demonstrated a substantial performance advantage. By reducing the number of intermediate nodes in the AST, Swift avoids the "state-space explosion" that typically occurs during the composition of large intermediate DFAs.
In the Counter benchmarks, Swift outperformed Lisa-Explicit and achieved results superior to Lydia in terms of benchmarks solved. The primary driver of this efficiency is the reduced memory footprint achieved through a more optimized AST structure, allowing Swift to solve more benchmarks within standard resource limits.
Conclusion
The development of Swift highlights that the logical "shape" of a specification is as important as its semantic content for efficient translation. Preprocessing the AST to minimize edges significantly improves scalability and runtime. Future work will explore integrating these reductions directly into the AST construction phase and identifying more complex symmetries to further optimize the translation process.
Summary updated