Multi-Property Synthesis

Christoph Weinhuber, Yannik Schnitzer, Alessandro Abate, David Parker, Giuseppe De Giacomo, Moshe Y. Vardi · 2026

Read Multi-Property Synthesis by Christoph Weinhuber, Yannik Schnitzer, Alessandro Abate, David Parker, Giuseppe De Giacomo, Moshe Y. Vardi (2026) 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-2601-10651.txt.

Introduction

Christoph Weinhuber, Yannik Schnitzer, Alessandro Abate, David Parker, Giuseppe De Giacomo, and Moshe Y. Vardi study synthesis with many properties at once. Synthesis means building a system that is sure to meet a stated goal. The goals here are written in LTLf, a logic for finite runs. The catch is that meeting all goals at once may be impossible.

Rather than test subsets of goals one by one, they compute in a single fixed-point pass. The pass links each game state to the sets of goals that can still be won from it. They then build strategies that achieve the largest winnable sets. The result helps designers of reactive systems get the most from conflicting demands.

Catalog record

CREATORChristoph Weinhuber, Yannik Schnitzer, Alessandro Abate, David Parker, Giuseppe De Giacomo, Moshe Y. Vardi
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-10651

Browse the full library · About the Tower of Babel

Full text

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

Multi-Property Synthesis Christoph Weinhuber, Yannik Schnitzer, Alessandro Abate, David Parker, Giuseppe De Giacomo, Moshe Y. Vardi Abstract We study LTL f \text{LTL}_{f} synthesis with multiple properties, where satisfying all properties may be impossible. Instead of enumerating subsets of properties, we compute in one fixed-point computation the relation between product-game states and the goal sets that are realizable from them, and we synthesize strategies achieving maximal realizable sets. We develop a fully symbolic algorithm that introduces Boolean goal variables and exploits monotonicity to represent exponentially many goal combinations compactly. Our approach substantially outperforms enumeration-based baselines, with speedups of up to two orders of magnitude. 1 1 footnotetext: [email protected], 2 [email protected] 1 Introduction The problem of synthesis from temporal specifications lies at the core of many decision-making problems in artificial intelligence, most prominently automated planning and controller synthesis. In this setting, we automatically construct an agent strategy that guarantees the satisfaction of a given temporal specification against all admissible behaviours of the environment. Linear Temporal Logic (LTL) has long served as the standard formalism for expressing temporally extended goals and assumptions in infinite-horizon settings, particularly in reactive synthesis 18 . In contrast, many real-world AI tasks are inherently finite-horizon : plans are meant to terminate, tasks have a clear notion of completion, and success is achieved once a desired condition is reached. The finite-trace variant of LTL, denoted \text{LTL}_{f} , has emerged as a natural and expressive formalism for specifying goals in such domains. Over the past years, \text{LTL}_{f} synthesis has matured into a standard tool for generating correct-by-construction behaviours for finite-horizon tasks 9 ; 10 . Typical application areas include classical and contingent planning 8 ; 6 , service composition 16 , and business process modelling 17 ; 7 , where the objective is not to react indefinitely, but to reach a satisfactory outcome and stop. While existing \text{LTL}_{f} synthesis techniques are well-suited for reasoning about single, monolithic specifications, they are largely constrained to an all-or-nothing paradigm: the procedure either successfully synthesises a strategy that satisfies the entire specification, or yields no strategy at all, declaring the problem unsolvable 13 . In many realistic scenarios, however, such as robotics, multi-service orchestration, or planning under resource constraints 25 ; 3 , agents face over-subscription 20 . That is, the specification naturally decomposes into multiple properties (or goals), but satisfying all of them simultaneously may be impossible due to conflicting requirements, limited resources, or adversarial environmental choices. In such settings, the all-or-nothing paradigm is overly restrictive, as failure is rarely binary. Even when the conjunction of all goals is unrealisable, an agent may still be able to guarantee the satisfaction of some meaningful subset of them. We study the fundamental question: If not all goals can be achieved simultaneously, which subsets can, and which of them are most desirable? Answering this question is crucial for enabling informed trade-offs, and principled decision-making in over-subscribed domains. A straightforward way to address this question is to enumerate all subsets of goals and, for each subset, solve the synthesis problem for the conjunction of its elements 1 . This, however, can become infeasible even for a moderate number of properties, as it requires solving an exponential number of synthesis instances. We propose a multi-property synthesis technique that reasons about all goal combinations simultaneously. Our approach computes, via a single fixed-point computation, the full relation between states and the subsets of goals that can be simultaneously achieved from them. Rather than checking realisability one subset at a time, we compute, in one pass, which combinations of goals can be guaranteed against all admissible environment behaviours. Crucially, our method is not limited to deciding which subsets of goals can be simultaneously achieved; it also synthesises a strategy that achieves them. The agent interacts with the environment until it reaches a state where the most desirable set of realisable goals has been achieved, at which point it can stop. Strategies are constructed not to react indefinitely, but to ensure progress toward satisfying the desired goals and to halt when this objective has been met. Beyond the fixed-point characterisation, we develop a fully symbolic technique to the multi-property computation. We leverage Boolean synthesis 15 to perform the fixed-point computation in a compact symbolic representation, which is often dramatically more efficient than explicit constructions 28 . Notice that, although the problem domain spans all subsets of goals, it is structured by monotonicity – achieving a set of goals implies achieving any subset of them. Our symbolic encoding is designed to exploit this structure directly, allowing a single Boolean representation to compactly characterize exponentially many goal combinations without explicitly enumerating them. In summary, this paper makes the following contributions: 1. We introduce a technique for multi-property \text{LTL}_{f} synthesis, capturing the realizability of arbitrary subsets of goals in over-subscribed domains. 2. We present a fixed-point characterization that computes, in a single construction, all maximal realizable goal sets and the strategies that achieve them. 3. We develop a symbolic synthesis algorithm that captures the exponentially-many goal combinations in a single compact Boolean form. 4. We empirically demonstrate that our approach significantly outperforms current state-of-the-art enumeration-based approaches by up to two orders of magnitude. 2 Related Work Multi-property Verification. Analysing multiple properties over a fixed model has also been studied in the verification literature. 5 ( 5 ) consider checking multiple invariants on the same circuit and show how to reduce repeated work by exploiting shared structure across properties. Since verification queries are independent , one property being true does not come at the expense of another, and the main challenge is amortizing repeated proof effort. In our synthesis setting, by contrast, properties can compete : enforcing one objective may restrict the available behaviors and thereby preclude satisfying another. In probabilistic verification, multi-objective model checking for Markov decision processes (MDPs) asks whether there exists a strategy that simultaneously meets bounds on the individual probabilities of satisfying multiple properties, and supports trade-off analysis by computing Pareto fronts 14 . Our multi-property synthesis can be seen as an analogous trade-off analysis in a qualitative, adversarial setting: instead of a continuous Pareto front over probability thresholds, we obtain a discrete frontier given by the maximal realizable sets of properties. Maximum-realizability Synthesis 11 ( 11 ) study infinite-trace LTL synthesis with hard specifications and soft safety requirements, of which potentially not all can be satisfied on a single execution. They employ a multi-valued quantitative semantics grading how well each soft property is satisfied along infinite executions that meet the hard constraint 12 . Their technique is optimisation-driven: building on bounded synthesis, they search for a controller that maximises this quantitative score within a bound on controller size 11 . In our setting, we are given many \text{LTL}_{f} goals and compute which subsets are simultaneously realizable, together with strategies fulfill them. We exploit that \text{LTL}_{f} synthesis reduces to DFA reachability games 10 , where satisfaction amounts to reaching accepting states. This yields a direct fixed-point computation with a local acceptance base case, computing in one construction the realizability relation for all states and goal combinations. Over-subscription and Planning with Preferences. Over-subscription and partial-satisfaction planning address settings where limitations prevent fulfilling all goals by utilizing heuristics or utility functions to select valuable

Read the complete text