Emerson-Lei and Manna-Pnueli Games for LTL f + and PPLTL+ Synthesis
Daniel Hausmann, Shufang Zhu, Gianmarco Parretti, Christoph Weinhuber, Giuseppe De Giacomo, Nir Piterman · 2025
Read Emerson-Lei and Manna-Pnueli Games for LTL f + and PPLTL+ Synthesis by Daniel Hausmann, Shufang Zhu, Gianmarco Parretti, Christoph Weinhuber, Giuseppe De Giacomo, Nir Piterman (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-14725.txt.
Introduction
Daniel Hausmann and co-authors built the first solvers for a new family of logic systems used in system design, in a 2025 paper. The logics state rules about how a system must act over time, mixing checks on short runs with demands over endless runs. Solvers turn such rules into games on graphs, then find a winning plan for the system.
One solver rests on Emerson-Lei games, lifting simple goals into harder ones step by step. A second, new kind of game builds the goals straight into the board and joins answers from simpler games. In tests, the new games often ran much faster, though not always, so using both looks best.
Catalog record
| CREATOR | Daniel Hausmann, Shufang Zhu, Gianmarco Parretti, Christoph Weinhuber, Giuseppe De Giacomo, Nir Piterman |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 76 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-14725
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Emerson-Lei and Manna-Pnueli Games for LTL f + and PPLTL+ Synthesis Daniel Hausmann, Shufang Zhu, Gianmarco Parretti, Christoph Weinhuber, Giuseppe De Giacomo, Nir Piterman Abstract Recently, the Manna-Pnueli Hierarchy has been used to define the temporal logics LTL f + and PPLTL+, which allow to use finite-trace LTL f /PPLTL techniques in infinite-trace settings while achieving the expressiveness of full LTL. In this paper, we present the first actual solvers for reactive synthesis in these logics. These are based on games on graphs that leverage DFA-based techniques from LTL f /PPLTL to construct the game arena. We start with a symbolic solver based on Emerson-Lei games, which reduces lower-class properties (guarantee, safety) to higher ones (recurrence, persistence) before solving the game. We then introduce Manna-Pnueli games, which natively embed Manna-Pnueli objectives into the arena. These games are solved by composing solutions to a DAG of simpler Emerson-Lei games, resulting in a provably more efficient approach. We implemented the solvers and practically evaluated their performance on a range of representative formulas. The results show that Manna-Pnueli games often offer significant advantages, though not universally, indicating that combining both approaches could further enhance practical performance. 1 Introduction This paper is about devising actual solvers for reactive synthesis in LTL f + and PPLTL+, which can be seen as a Manna-Pnueli normal form for Linear Temporal Logic (LTL) based respectively on its finite trace variant LTL f and on Pure Past LTL (PPLTL). Reactive synthesis deals with synthesizing programs (aka strategies) from temporal specifications, for systems (e.g. agents, processes, protocols, controllers, robots) that interact with their environments during their execution [ \citeauthoryearPnueli and Rosner1989 , \citeauthoryearFinkbeiner2016 , \citeauthoryearEhlers et al.2017 ] . The most common specification language is possibly Linear Temporal Logic (LTL) [ \citeauthoryearPnueli1977 ] . Reactive synthesis shares foundational techniques with model checking, grounded in the interplay between logic, automata, and games [ \citeauthoryearFijalkow et al.2023 ] . For LTL, synthesis normally proceeds by: (1) specifying the desired behavior with controllable and uncontrollable variables; (2) translating the specification into an equivalent automaton over infinite words; (3) determinizing the automaton—unlike in model checking—to define a game between system and environment; and (4) solving the game, typically with a parity objective, to derive a strategy satisfying the original specification. The symbolic techniques for model checking based on Boolean encodings to compactly represent game arenas and compute fixpoints can also be leveraged in reactive synthesis. Nevertheless, differently from model checking, LTL synthesis has struggled to achieve comparable efficiency, primarily due to the inherent complexity of Step (3): the determinization of nondeterministic Büchi automata (NBA), a process known to be computationally challenging [ \citeauthoryearVardi2007 , \citeauthoryearAlthoff, Thomas, and Wallmeier2006 ] . In AI, reactive synthesis is closely related to strong planning for temporally extended goals in fully observable nondeterministic domains [ \citeauthoryearCimatti et al.2003 , \citeauthoryearBacchus and Kabanza1998 , \citeauthoryearBacchus and Kabanza2000 , \citeauthoryearCalvanese, De Giacomo, and Vardi2002 , \citeauthoryearBaier, Fritz, and McIlraith2007 , \citeauthoryearGerevini et al.2009 , \citeauthoryearDe Giacomo and Rubin2018 , \citeauthoryearCamacho, Bienvenu, and McIlraith2019 ] . Plans are typically assumed to terminate, and this has led to a focus on logics over finite traces, rather than infinite ones, with LTL f , the finite-trace variant of LTL, being a common choice [ \citeauthoryearGabbay et al.1980 , \citeauthoryearBaier and McIlraith2006 , \citeauthoryearDe Giacomo and Vardi2013 , \citeauthoryearDe Giacomo and Vardi2015 ] . In fact, LTL f synthesis [ \citeauthoryearDe Giacomo and Vardi2015 ] is, along with the GR(1) fragment of LTL [ \citeauthoryearPiterman, Pnueli, and Sa’ar2006 ] , one of the two major success stories in reactive synthesis to date. The steps of the LTL f synthesis algorithm closely mirror Steps (1)–(4) outlined for LTL, potentially incurring similar asymptotic blowups. Specifically, Step (2) yields a nondeterministic finite automaton (NFA) that can be exponentially larger than the input formula, and Step (3) determinizes it into a DFA, which can be exponentially larger than the NFA. However, in practice, these worst-case blowups rarely occur for LTL f : Step (2) is shared with model checking, where it performs well; Step (3) benefits from the fact that NFA determinization is rarely problematic in practice – in fact, it is often observed that the resulting DFA is actually smaller than the original NFA [ \citeauthoryearTabakov and Vardi2005 , \citeauthoryearArmoni et al.2006 , \citeauthoryearRozier and Vardi2012 , \citeauthoryearTabakov, Rozier, and Vardi2012 , \citeauthoryearZhu et al.2021 ] . Moreover, tools like MONA [ \citeauthoryearKlarlund, Møller, and Schwartzbach2002 ] , used by LTL f synthesizers to extract automata, return DFAs in semi-symbolic form, i.e., transitions are represented symbolically. This is a very important aspect, because one other significant barrier that we may underestimate in LTL and LTL f synthesis is the alphabet explosion problem. That is to say, once there are just 20 propositions, which is not a very large number, the alphabet already has size 1 million, making explicit treatment of the alphabet infeasible. Symbolic methods circumvent this problem (to some extent). These nice characteristics of LTL f have enabled the community to build a first fully symbolic solver for LTL f synthesis [ \citeauthoryearZhu et al.2017b ] . Since then, a series of papers have improved symbolic technology for LTL f synthesis significantly [ \citeauthoryearBansal et al.2020 , \citeauthoryearDe Giacomo and Favorito2021 , \citeauthoryearKankariya and Bansal2024 , \citeauthoryearZhu and Favorito2025 ] . Furthermore, the LTL f technology has been extended to several other cases, from safety and reachability [ \citeauthoryearZhu et al.2017a , \citeauthoryearBansal et al.2022 , \citeauthoryearAminof et al.2025a ] all the way to GR(1) [ \citeauthoryearDe Giacomo et al.2022 ] . These desirable properties are also exhibited by Pure-Past LTL (PPLTL) [ \citeauthoryearLichtenstein, Pnueli, and Zuck1985 , \citeauthoryearDe Giacomo et al.2020 ] , which has recently emerged as an even simpler alternative to LTL f , while maintaining the same expressive power [ \citeauthoryearBonassi et al.2023b , \citeauthoryearBonassi et al.2023a , \citeauthoryearBonassi et al.2024 ] . The question is, can we use this technology to do LTL synthesis? Recently [ \citeauthoryearAminof et al.2025b ] gave affirmative answer to this question by exploiting Manna and Pnueli’s normal form [ \citeauthoryearManna and Pnueli1990 ] . This normal form is based on specifying finite trace properties, e.g. expressed in LTL f (or PPLTL) and then requiring that the property holds for some prefixes of infinite traces ( guarantee properties), for all prefixes ( safety properties), for infinitely many prefixes ( recurrence properties), or for all but finitely many prefixes ( persistence properties). Any LTL formula can be expressed as a Boolean combination of these four classes. How can we take advantage of Manna and Pnueli’s normal form? An answer is, first of all, in building the arena. For each finite trace property, we can build the DFA, using LTL f technology [ \citeauthoryearAminof et al.2025b ] . Then, depending on Manna and Pnueli’s class, we choose the accepting condition to (guarantee) visit a final state once, (safety) never leave the set of final states, (recurrence) visit some final state infinitely often, (persistence) stay out of the set of final states finitely many times. All these component automata run in parallel, so we can take their product. In fact, we can represent the product symbolically in a straightforward way. To