LTLƒ Synthesis with Fairness and Stability Assumptions

Shufang Zhu, Giuseppe De Giacomo, Geguang Pu, Moshe Y. VardiAAAI 2020 · DOI

Abstract

This paper presents an efficient approach for synthesizing reactive systems with finite-trace goals ($LTL_f$) under infinite-trace environment assumptions, specifically fairness and stability. By utilizing direct BDD-based fixpoint algorithms on Deterministic Finite Automata (DFA), the proposed methods avoid the computationally expensive determinization required by standard LTL synthesis. Experimental results show that the resulting tools, FSyft and StSyft, outperform state-of-the-art LTL synthesis tools by orders of magnitude.

Introduction

In reactive synthesis, the goal is to automatically generate a strategy for an agent that satisfies a given specification regardless of the environment's actions. While many practical goals are expressed over finite traces ($LTL_f$), the environment's behavior often requires constraints over an infinite horizon to make these goals achievable. Common constraints include fairness (e.g., "a request is eventually granted infinitely often") and stability (e.g., "the system eventually remains in a safe state").

The Challenge of Infinite Assumptions

The conventional approach to solving $LTL_f$ synthesis under infinite assumptions involves translating the entire problem into standard LTL synthesis. Although both $LTL$ and $LTL_f$ synthesis share a theoretical worst-case complexity of 2EXPTIME-complete, LTL synthesis is significantly more difficult in practice. It necessitates complex automata determinization, such as Safra’s construction, which is notoriously hard to implement efficiently and often leads to state-space explosion.

The authors of this paper propose a more direct route: handling these infinite-trace assumptions without leaving the simpler, DFA-based world of $LTL_f$ synthesis.

Methodology: Direct DFA-Based Synthesis

The proposed technique focuses on two primary types of environment assumptions:

  1. Fairness ($GF\alpha$): A condition $\alpha$ holds infinitely often.
  2. Stability ($FG\alpha$): A condition $\alpha$ eventually holds and remains true thereafter.

Instead of a full LTL conversion, the methodology uses the DFA of the $LTL_f$ goal as the game arena. The authors define Fair DFA games and Stable DFA games played on this arena. The core solution is a nested fixpoint algorithm implemented using Binary Decision Diagrams (BDDs). This symbolic approach allows for the iterative computation of the "winning region"—the set of states from which the agent can guarantee reaching an accepting state while the environment is constrained by fairness or stability.

These algorithms were implemented in two specialized tools: FSyft (for fairness) and StSyft (for stability).

Experimental Evaluation

The researchers evaluated FSyft and StSyft against Strix, the leading tool in the LTL synthesis competition (SYNTCOMP), using two benchmark sets:

  • Random Conjunctions: 1,000 formulas generated by joining $LTL_f$ patterns with random environment assumptions.
  • Counter Game: A scalable benchmark involving an $n$-bit binary counter reaching its maximum value, covering both realizable and unrealizable cases.
Cumulative solved cases over time for FSyft vs. Strix on fairness benchmarks.

The results demonstrate a massive performance gap. On the random benchmarks, FSyft and StSyft solved nearly every case within seconds, whereas Strix timed out on more than half of the instances. As shown in the cumulative performance plots, the proposed tools often find solutions in under 0.1 seconds.

Execution time comparison between StSyft and Strix on the Counter Game benchmark for stability.

In the Counter Game, the scalability of the DFA-based approach is evident. While Strix began to struggle and time out as the counter size increased beyond 7 bits, FSyft and StSyft handled the 10-bit limit of the comparison with ease, maintaining execution times significantly lower than those of Strix.

Conclusion

By avoiding the "detour" through standard LTL synthesis, this work shows that $LTL_f$ synthesis under fairness and stability assumptions can be performed much more efficiently. The use of BDD-based fixpoint algorithms on DFA arenas provides a scalable and practical solution for reactive synthesis. Future work aims to extend this approach to more general LTL assumptions by integrating parity automata into the DFA-based game framework.

Summary updated

BibTeX
@inproceedings{zhu2020ltl,
  author = {Shufang Zhu and Giuseppe De Giacomo and Geguang Pu and Moshe Y. Vardi},
  title = {{LTLƒ Synthesis with Fairness and Stability Assumptions}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i03.5704},
}
Figure