Daily Arxiv

This is a page that curates AI-related papers published worldwide.
All content here is summarized using Google Gemini and operated on a non-profit basis.
Copyright for each paper belongs to the authors and their institutions; please make sure to credit the source when sharing.

Emerson-Lei and Manna-Pnueli Games for LTLf+ and PPLTL+ Synthesis

Created by
  • Haebom

Author

Daniel Hausmann, Shufang Zhu, Gianmarco Parretti, Christoph Weinhuber, Giuseppe De Giacomo, Nir Piterman

Outline

This paper presents the first reactive synthesis solver for temporal logic LTLfp and PPLTLp, which achieves full LTL expressivity in an infinite-trace environment by leveraging finite-trace LTLf/PPLTL techniques. It is based on a graph game that constructs a game arena using a DFA-based LTLf/PPLTL technique. First, we present a symbolic solver based on the Emerson-Lei game, which reduces low-level properties (guarantees and safety) to high-level properties (recursivity and persistence) and solves the game. Finally, we introduce the Manna-Pnueli game, which naturally incorporates the Manna-Pnueli objective into the arena. The Manna-Pnueli game is solved by synthesizing the solution to the DAG of the simpler Emerson-Lei game, a provably more efficient approach. We experimentally evaluate the implemented solver for various formulations, showing that the Manna-Pnueli game often offers significant benefits, but is not universal, suggesting that combining the two approaches could further improve practical performance.

Takeaways, Limitations

Takeaways:
We present the first reactive synthesis solver for LTLfp and PPLTLp.
We present and compare the performance of two solvers based on the Emerson-Lei game and the Manna-Pnueli game.
Experimentally demonstrated that the Manna-Pnueli game is more efficient in certain cases.
Combining the two approaches suggests potential for future performance improvements.
Limitations:
The effectiveness of the Manna-Pnueli game is not guaranteed in all cases.
An improved solver combining both approaches has not yet been presented.
Further research is needed to determine the generalizability of the experimental results.
👍