Modular Attractor Acceleration in Infinite-State Games (Full Version)

Philippe Heim✉, Rayna Dimitrova · 2026

Read Modular Attractor Acceleration in Infinite-State Games (Full Version) by Philippe Heim✉, Rayna Dimitrova (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-14068.txt.

Introduction

Philippe Heim and Rayna Dimitrova speed up solving games with unbounded data in 2026. Infinite-state games frame the synthesis of reactive systems with unbounded domains. Solving them relies on symbolic fixpoints, mainly symbolic attractors. These computations may not terminate, which blocks synthesis.

Recent acceleration techniques try to force termination. They often rely on acceleration arguments of limited expressiveness. The team's modular attractor acceleration aims for broader power. Systems like controllers and protocols need synthesis that finishes with a proof. Fast, sound games work is key for safe code in planes, cars, and grids. A method that ends more often can widen what teams dare to check.

Catalog record

CREATORPhilippe Heim✉, Rayna Dimitrova
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE83 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel

Full text

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

Modular Attractor Acceleration in Infinite-State Games (Full Version) Philippe Heim✉, Rayna Dimitrova Abstract Infinite-state games provide a framework for the synthesis of reactive systems with unbounded data domains. Solving such games typically relies on computing symbolic fixpoints, particularly symbolic attractors. However, these computations may not terminate, and while recent acceleration techniques have been proposed to address this issue, they often rely on acceleration arguments of limited expressiveness. In this work, we propose an approach for the modular computation of acceleration arguments. It enables the construction of complex acceleration arguments by composing simpler ones, thereby improving both scalability and flexibility. In addition, we introduce a summarization technique that generalizes discovered acceleration arguments, allowing them to be efficiently reused across multiple contexts. Together, these contributions improve the efficiency of solving infinite-state games in reactive synthesis, as demonstrated by our experimental evaluation. 1 Introduction Two-player infinite-duration graph games are a standard formalism used for synthesis of correct-by-construction reactive systems. Synthesizing such a system reduces to computing a winning strategy for the system player against an adversarial environment. Finite-state games are well-established, and efficient techniques and tools are available. However, many systems operate over unbounded data domains, motivating interest in infinite-state games. Solving such games is undecidable, and recent works explored several incomplete methods. Abstraction-based methods [ 6 , 19 , 25 , 26 , 23 , 1 , 24 ] reduce the problem to the finite case. Their effectiveness depends on the abstraction domain’s precision and the ability to discover relevant properties when refining the abstraction. Constraint-based methods [ 9 , 8 , 28 , 20 , 13 ] operate directly on symbolic representations of the infinite state space. The main challenge for these is taming the divergence of the computations. As many game-solving algorithms rely on (nested) fixpoint computations, one line of recent work [ 13 , 29 , 14 ] has focused on accelerating these computations, especially accelerating attractor computations which are the main driver of those fixpoint-based algorithms. Intuitively, an attractor is the set of states in the game from which a given player has a strategy to reach a given target set of states, regardless of the opponent’s behavior. A key notion in [ 13 , 29 , 14 ] is that of acceleration lemmas , which help to establish the existence of strategies for infinite subsets of the attractor, by capturing the effect of an infinite number of computation steps into a single one. Finding acceleration lemmas is challenging, as it requires proving that an acceleration property can be enforced against any adversarial behavior. [ 13 ] computes acceleration lemmas by representing candidates for them as uninterpreted functions and by using symbolic game solving to generate constraints on those. However, the resulting constraint systems can become prohibitively large in complex games. The burden of finding acceleration lemmas is then shifted entirely to the SMT solver. Subsequent methods, such as [ 29 ] have improved this computation but have not departed conceptually from the original idea. Overall, despite promising results, existing methods often struggle when complex acceleration lemmas are required. In this work, we investigate methods for efficiently constructing complex acceleration lemmas by systematically composing them from simpler ones, which allows us to conduct a dedicated search for lemmas. In addition, we explore how acceleration arguments can be reused through appropriate generalization. The following examples motivate these ideas. \mathit{loop} \mathit{done} \small\alpha \small y\leq 0 \small\top (a) \mathcal{G}_{R} \mathit{init} \mathit{iter} \mathit{loop} \mathit{sink} c^{\prime}=123 \beta c<-200 y\leq 0\land c^{\prime}=c \alpha\land c^{\prime}=c \top (b) \mathcal{G}_{B} \begin{array}[]{lll}\small\alpha&:=&(x\leq 0\lor b)\land x^{\prime}=i\land y^{\prime}=y-1\\ &\lor&(x>0\land\neg b)\land x^{\prime}=x-i-2\land y^{\prime}=y\\ &\lor&(x>0\land\neg b)\land x^{\prime}=x+i+1\land y^{\prime}=y\end{array} \begin{array}[]{lll}\small\beta&:=&c\geq-200\land x^{\prime}=i_{x}\land y^{\prime}=i_{y}\\ &\land&(c\geq 0\land c^{\prime}=c+1\lor c<0\land c^{\prime}=c-1)\end{array} (c) Transition formulas. Figure 1 : Symbolic games \mathcal{G}_{R} and \mathcal{G}_{B} for the motivating examples. In both games, x and y are integer state variables, and i and b are input variables with integer and Boolean types, respectively. Additionally, the Büchi game \mathcal{G}_{B} has an integer state variable c and input variables i_{x} and i_{y} , which are also integers. Example 1 Figure 1(a) depicts a game \mathcal{G}_{R} , in which the system player must ensure reaching location \mathit{done} against all possible behaviors of the environment. The game starts in location \mathit{loop} with arbitrary initial values of the state variables x and y . The system controls x and y , subject to the transition formulas labeling the game’s edges. In each step, the environment first chooses values for the input variables i and b , after which the system selects a successor location and state consistent with the corresponding transition formula. For example, from location \mathit{loop} , the system may remain in \mathit{loop} and choose x and y satisfying the transition formula \alpha shown in Figure 1(c) . Concretely, it may set x to i and decrement y when x\leq 0\vee b holds, or otherwise update x in one of two ways while keeping y unchanged. To show that the system wins, one must establish a strategy that, for any initial values of x and y and any sequence of inputs i and b chosen by the environment, eventually reaches \mathit{done} . This amounts to enforcing a state (\mathit{loop},v_{x},v_{y}) with v_{y}\leq 0 . Such a strategy exists: When x>0\land\neg b holds, the system can update x depending on i to ensure that x decreases. Hence, while x>0 and the environment keeps b false, the system can reduce x , eventually enabling the disjunct that decrements y . When y is decremented, the environment picks a new value i for x , and the process repeats. Because y never increases, the first disjunct can only be applied finitely many times with y>0 , i.e., the system can enforce progress toward \mathit{done} . Establishing this formally requires finding a correct strategy (i.e., the system program) and the corresponding acceleration argument. The reasoning above relies on establishing a lexicographic acceleration argument together with a strategy for the system player that enforces it. The argument is that either y decreases, in which case it does not matter how the value of x changes, or the value of y remains unchanged and the value of x decreases. The latter case relies on the system correctly selecting the update to x based on the current input i provided by the environment. Although this argument is conceptually simple, the automatic synthesis of such acceleration lemmas is challenging for existing methods. Current tools for solving infinite-state games fail on this example due to the vast search space of potential acceleration arguments and strategies. In this paper, we address this challenge by introducing a modular approach for constructing such a witness. The key idea is to define composition operations that build up more complex acceleration lemmas from simpler ones . This enables a structured navigation of the search space, leading to the discovery of powerful acceleration lemmas beyond the reach of existing techniques. However, scalability remains a challenge, particularly when solving complex games that require generating multiple acceleration lemmas. The following example illustrates this issue. Example 2 Figure 1(b) depicts a game \mathcal{G}_{B} with a Büchi winning condition requiring that location \mathit{iter} be visited infinitely often. The game contains a sub-game (locations \mathit{iter} and \mathit{loop} ) structurally similar to \mathcal{G}_{R} from Example 1 ,

Read the complete text