Parameterized Infinite-State Reactive Synthesis
Benedikt Maderbacher, Roderick Bloem · 2025
Read Parameterized Infinite-State Reactive Synthesis by Benedikt Maderbacher, Roderick Bloem (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-00613.txt.
Introduction
Benedikt Maderbacher and Roderick Bloem present a method that builds reactive software once, for whole families of settings at once, in a 2025 paper. Such systems must answer their surroundings endlessly, and each setting value could demand a fresh build. Their method instead synthesizes a program with the setting left as a dial.
The loop starts by building concrete systems for a few small settings. It then generalizes them into one parameterized program and drafts a proof: an invariant plus a ranking function. Failed proofs hand back a setting worth adding to the first step. Tests cover literature examples stretched with parameters plus fresh problems.
Catalog record
| CREATOR | Benedikt Maderbacher, Roderick Bloem |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 93 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-00613
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Parameterized Infinite-State Reactive Synthesis DOI: XXXXXXX.XXXXXXX CCS: Software and its engineering Formal methods Thanks: This project has received funding from the Austrian research promotion agency FFG under project FATE (№ 894789). Benedikt Maderbacher, Roderick Bloem Abstract . We propose a method to synthesize a parameterized infinite-state systems that can be instantiated for different parameter values. The specification is given in a parameterized temporal logic that allows for data variables as well as parameter variables that encode properties of the environment. Our synthesis method runs in a counterexample-guided loop consisting of four main steps: First, we use existing techniques to synthesize concrete systems for some small parameter instantiations. Second, we generalize the concrete systems into a parameterized program. Third, we create a proof candidate consisting of an invariant and a ranking function. Fourth, we check the proof candidate for consistency with the program. If the proof succeeds, the parameterized program is valid. Otherwise, we identify a parameter value for which the proof fails and add a new concrete instance to step one. To generalize programs and create proof candidates, we use a combination of anti-unification and syntax-guided synthesis to express syntactic differences between programs as functions of the parameters. We evaluate our approach on examples from the literature that have been extended with parameters as well as new problems. 1. Introduction Reactive synthesis on infinite-state domains like integers or reals can be used in settings such as cyber-physical systems that operate on complex data. These systems are often deployed in different environments. We propose to encode the differences in the environment as parameters. We want to construct a single parameterized system that can be used in all environments. By synthesizing a parameterized system, we eliminate the need to create an infinite number of instances, one for each parameter value. Unlike classical reactive synthesis, where the system’s size is heavily influenced by the specification, our approach constructs systems whose size is independent of the parameter values. Example 1.1. A robot with location x\in\mathbb{Z} can move on a track between a loading zone (where x=min ) and an unloading zone ( x=max ). It is affected by wind disturbances that can push it d steps in either direction. The robot must visit the loading and the unloading zone infinitely often. We want a single parameterized controller that works for any value of the parameters min and max with min+1<max . The specification written using the linear temporal operators \Box for globally and \Diamond for eventually is included in . It contains a set of actions that consist of a guard that states when the action may be executed and an update that defines how the state variables are changed. A globally guarantee is syntactic sugar for a condition that is added to every guard. In this example there are three actions : • (min\leq x\leq max,\;x^{\prime}=x+d) , • (min\leq x\leq max,\;x^{\prime}=x+1+d) , and • (min\leq x\leq max,\;x^{\prime}=x-1+d) . The robot can stop, move right, or move left, while wind disturbance d influences the position. The guards specify that actions can only be executed if the robot is on the track. The specification \phi consists of the environment transition relation -1\leq d\leq 1 and the temporal specification (\Box\Diamond d<0\land\Box\Diamond 0<d)\Rightarrow(\Box\Diamond x=min\land\Box\Diamond x=max) , which includes the assumption that the wind does not always blow from the same direction, as this would make it impossible to reach one of the goals. The system must work for all initial states min\leq x\leq max . The main loop of a parameterized program that satisfies \phi is shown in . It is executed in an infinite loop, once in every time step. The program uses an additional variable c to track the goal that is currently being targeted. The first part of the program changes the goal if the current goal has been reached. The program has a subprogram for each goal. If c=1 , the program tries to decrease x until it becomes equal to min . The subprogram may fail to decrease x if there is a head wind and must be careful not to overshoot min if there is a tail wind. The case of c=2 , where the program tries to increase x , is analogous. As intended, this program fulfills the specification, regardless of which concrete values are chosen for min and max . Specification ⬇ Parameters : min,max\in\mathbb{Z} State : x\in\mathbb{Z} Input : d\in\mathbb{Z} Actions : \operatorname{True} , x := x-1+d \operatorname{True} , x := x+d \operatorname{True} , x := x+1+d assume \Box\;-1\leq d\leq 1\;\land \Box\Diamond\;d<0\land\Box\Diamond\;0<d guarantee \Box\;min\leq x\leq max\;\land \Box\Diamond\;x=min\land\Box\Diamond\;x=max System loop body ⬇ if (c=1\land x=min)\;\lor (c=2\land x=max) : c := c\oplus 1 if c=1 : if x+d\geq min+1 : x := x-1+d else : x := x+d if c=2 : if x+d\leq max-1 : x := x+1+d else : x := x+d Summary We propose a novel method to synthesize an infinite-state parameterized system that fulfills a parameterized Generalized Reactivity(1) or GR(1) specification (an extension of propositional GR(1) ( Bloem et al. 2012 ) ). The method consists of a counterexample-driven synthesis loop ( Fig. 1 ). At every iteration of the loop, we have a finite set of parameter values P^{\prime} . We construct a concrete synthesis problem for each p\in P^{\prime} , and pass them to an existing concrete synthesis method, which returns a concrete system and an invariant for each p . We use the concrete solutions as input to a generalization procedure. This procedure constructs a generalized program and a generalized candidate invariant that may both include parameter variables. We also construct a candidate ranking function for the generalized program that we use to prove progress towards the goals of the GR(1) specification. By construction, the generalized program and invariant encompass the behaviors of all concrete programs. We verify whether the generalized system is consistent with the generalized candidate invariant and ranking function, which means that the system is correct for all parameter values. If not, we obtain a new parameter value p for which the program does not match the proof candidate and we add p to P^{\prime} and start the next iteration. There are several alternative executions. First, the concrete synthesis algorithm may find a counterexample to realizability for p , which means that the parameterized specification is unrealizable. Second, the proof candidate may succeed in showing that the generalized program is correct, and synthesis succeeds. Third, because parameterized synthesis is undecidable, the loop may not terminate. Note that the concrete synthesis problems may or may not be be finite state. For instance, the parameters may bound the range of an integer, which means that any concrete system is finite state. If, instead, the parameters bound a real-valued variable, a concrete system is infinite. In the latter case, the concrete synthesis problem is also undecidable and may not terminate. The parameterized synthesis problem is equivalent to infinite state synthesis: Parameterized synthesis can be reduced to infinite state synthesis by defining the parameter as an additional input that does not change during execution, and infinite state synthesis is simply parameterized synthesis using an empty set of parameters. However, existing infinite state synthesis methods are based on Boolean abstraction or symbolic fixpoint computations, rather than