Decompositions in Compositional Translation of LTLf to DFA (Student Abstract)

Yash Kankariya, Suguman BansalAAAI 2024 · DOI

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.

AST optimization via syntactic-equivalence rules, reducing the number of composition operations.

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.

Cumulative time comparison on NIM benchmarks, demonstrating Swift's superior performance.

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

BibTeX
@inproceedings{kankariya2024decompositions,
  author = {Yash Kankariya and Suguman Bansal},
  title = {{Decompositions in Compositional Translation of LTLf to DFA (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i21.30462},
}
Figure