First-Order LTLf Synthesis with Lookback (Extended Version)

Sarah Winkler · 2025

Read First-Order LTLf Synthesis with Lookback (Extended Version) by Sarah Winkler (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-18149.txt.

Introduction

Sarah Winkler extends reactive synthesis to richer logics in a 2025 paper. Synthesis builds a controller that provably meets a temporal specification against any environment moves. Her setting lets rules compare values across time steps, a lookback feature earlier tools mostly banned.

That freedom makes the problem undecidable in general, so the procedure may not always halt. Still, it is sound, and complete whenever a bounded-length winning strategy exists. For several useful fragments it becomes a true decision procedure, recovering known results and adding new ones. Readers get a wider synthesis frontier with honest limits.

Catalog record

CREATORSarah Winkler
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE86 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-18149

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

First-Order LTLf Synthesis with Lookback (Extended Version) Sarah Winkler Abstract Reactive synthesis addresses the problem of generating a controller for a temporal specification in an adversarial environment; it was typically studied for 𝖫𝖳𝖫 \mathsf{LTL} . Driven by applications ranging from AI to business process management, 𝖫𝖳𝖫 \mathsf{LTL} modulo first order-theories over finite traces ( 𝖫𝖳𝖫 𝖿 𝖬𝖳 \mathsf{LTL_{f}^{MT}} ) has recently gained traction, where propositional variables in properties are replaced by first-order constraints. Though reactive synthesis for 𝖫𝖳𝖫 𝖿 \mathsf{LTL_{f}} with some first-order features has been addressed, existing work in this direction strongly restricts or excludes the possibility to compare variables across instants, a limitation that severely restricts expressiveness and applicability. In this work we present a reactive synthesis procedure for 𝖫𝖳𝖫 𝖿 𝖬𝖳 \mathsf{LTL_{f}^{MT}} , where properties support lookback to model cross-instant comparison of variables. Our procedure works for full 𝖫𝖳𝖫 𝖿 𝖬𝖳 \mathsf{LTL_{f}^{MT}} with lookback, subsuming the fragments of 𝖫𝖳𝖫 𝖿 𝖬𝖳 \mathsf{LTL_{f}^{MT}} for which realizability was studied earlier. However, the setting with cross-instant comparison is inherently highly complex, as realizability is undecidable even over decidable background theories. Hence termination of our approach is in general not guaranteed. Nevertheless, we prove its soundness, and show that it is complete if a bound on the strategy length exists. Finally, we show that our approach constitutes a decision procedure for several relevant fragments of 𝖫𝖳𝖫 𝖿 𝖬𝖳 \mathsf{LTL_{f}^{MT}} , at once re-proving known decidability results and identifying new decidable classes. 1 Introduction Reactive synthesis [ Pnueli and Rosner(1989a) , Pnueli and Rosner(1989b) ] addresses the problem of automatically constructing a system that satisfies a given temporal specification in an adversarial environment. Along with the respective decision problem of realizability, it is most typically considered for \mathsf{LTL} , where the input is an \mathsf{LTL} property and a splitting of the set of propositional variables into two disjoint sets that are respectively controlled by the environment and the agent. The aim is to find a strategy for the agent such that the given property is satisfied, no matter which values are assigned to the environment variables. While reactive synthesis was originally considered for \mathsf{LTL} over infinite traces, in a recent line of work, efficient algorithms and tools have been developed that target the synthesis problem for \mathsf{LTL_{f}} , i.e., \mathsf{LTL} over finite traces [ Giacomo and Vardi(2015) , Giacomo et al.(2022)Giacomo, Favorito, Li, Vardi, Xiao, and Zhu , Xiao et al.(2021)Xiao, Li, Zhu, Shi, Pu, and Vardi ] . However, propositional \mathsf{LTL} and \mathsf{LTL_{f}} have limited expressivity that inhibits to realistically model many practical problems. This observation led to the development of synthesis techniques for the logic \mathsf{LTL}_{\mathcal{T}} , where propositional atoms are replaced by atoms from a first-order theory [ Rodríguez and Sánchez(2023) , Rodríguez and Sánchez(2024b) , Rodríguez and Sánchez(2024a) ] . These techniques are based on the compilation of a Boolean abstraction from the first-order problem that can be given to a standard realizability tool after solving some first-order satisfiability problems to ensure that the Boolean abstraction is faithful. Independently, the logic \mathsf{LTL_{f}^{MT}} ( \mathsf{LTL_{f}} modulo theories) has gained traction in the last years [ Geatti et al.(2022)Geatti, Gianola, and Gigante , Gianola et al.(2024)Gianola, Montali, and Winkler ] , as its versatility admits applications in a variety of areas. This includes verification of infinite-state systems using the MoXI intermediate language [ Johannsen et al.(2024)Johannsen, Nukala, Dureja, Irfan, Shankar, Tinelli, Vardi, and Rozier ] whose semantics can be expressed in \mathsf{LTL_{f}^{MT}} , and analysis of business processes [ Gianola et al.(2024)Gianola, Montali, and Winkler ] ; but \mathsf{LTL_{f}^{MT}} also covers languages used for runtime verification such as LoLA [ D’Angelo et al.(2005)D’Angelo, Sankaranarayanan, Sánchez, Robinson, Finkbeiner, Sipma, Mehrotra, and Manna ] , and \mathsf{LTL_{f}} with arithmetic constraints considered for monitoring [ Felli et al.(2023)Felli, Montali, Patrizi, and Winkler ] . \mathsf{LTL_{f}^{MT}} also subsumes the logic \mathsf{LTL}_{\mathcal{T}} , but differs from the latter in that variables can be compared across different time instants. This feature vastly increases expressivity, is crucial to describe the advancement of a dynamic system, and is present in most languages for reasoning over temporal properties that have some first-order flavour, including MoXI, LoLA, the runtime verification language TeSSLa [ Convent et al.(2018)Convent, Hungerecker, Leucker, Scheffel, Schmitz, and Thoma ] , and Data Petri nets, a variant of Petri nets popular in the analysis of business processes [ Mannhardt et al.(2016)Mannhardt, de Leoni, Reijers, and van der Aalst ] . In this paper we will use the term lookback for the feature to compare variables describing the current instant with variables for the previous instant; this is equivalent in expressivity to comparison with variables that refer to (bounded) future instants [ Felli et al.(2023)Felli, Montali, Patrizi, and Winkler ] . However, cross-state comparisons come at the cost that the satisfiability and realizability problems are undecidable even over a benign theory such as linear arithmetic [ Geatti et al.(2022)Geatti, Gianola, and Gigante , Bhaskar and Praveen(2024) ] . The following simple example illustrates the realizability problem in such a setting: Example 1 . Alice runs a resource-consuming computing task that is supposed to take multiple days in a cloud-based elastic system. Suppose that at every instant, a rational number x describes the resources allocated by the cloud system (the environment), and a rational number y holds the resource bound requested by Alice (the agent). Alice wants to take one day off, so she wants to set a resource bound today that is guaranteed to be larger than the resources required the following day. She estimates that the resource consumption increases from one day to the next by at most 2 units. The aim is to find a strategy for Alice that ensures this property. In \mathsf{LTL_{f}^{MT}} , this can be described as \mathsf{G}(x\geq 0\wedge x{-}{\rm Phys.~Rev.~E}{x}\leq 2)\to\mathsf{X}({\rm Phys.~Rev.~E}y>x) , where {\rm Phys.~Rev.~E}x and {\rm Phys.~Rev.~E}y denote the lookback variables that hold the previous values of x and y , respectively. In this paper we address, to the best of our knowledge for the first time, the reactive synthesis problem for full \mathsf{LTL_{f}^{MT}} with lookback. Our approach to this end is conceptually simple: we first represent a DFA for the given \mathsf{LTL_{f}^{MT}} property \psi as an AND-OR-graph \mathcal{A}_{\psi} where edge labels are suitably split into constraints controlled by the environment and constraints controlled by the agent, following [ Giacomo et al.(2022)Giacomo, Favorito, Li, Vardi, Xiao, and Zhu ] . In a second step, we define for every state in \mathcal{A}_{\psi} a first-order formula that constitutes a winning condition for the agent. The overall winning condition is defined as a fixpoint which need not exist in general; but if it does, it gives rise to a strategy to synthesise \psi . In summary, we provide a three-fold contribution: (1) We present a general reactive synthesis procedure for \mathsf{LTL_{f}^{MT}} properties with lookback. (2) We prove its soundness, and show that it is also complete for bounded realizability, i.e., in the case where there is a bound on the length of the strategy. (3) Our procedure is shown to be a decision procedure for several fragments of \mathsf{LTL_{f}^{MT}} , including the case without lookback; properties over the theory of linear arithmetic where atoms are variable-to-variable/constant comparisons; and properties where variable interaction via

Read the complete text