Towards the Usage of Window Counting Constraints in the Synthesis of Reactive Systems to Reduce State Space Explosion \rsuper *
Linda Feeken ORCID:0009-0003-7336-0859, Martin Fränzle ORCID:0000-0002-9138-8340 · 2025
Read Towards the Usage of Window Counting Constraints in the Synthesis of Reactive Systems to Reduce State Space Explosion \rsuper * by Linda Feeken ORCID:0009-0003-7336-0859, Martin Fränzle ORCID:0000-0002-9138-8340 (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-2503-21852.txt.
Introduction
Linda Feeken and Martin Fränzle attack a cost problem in building reactive systems in a 2025 paper. Synthesis promises to construct, automatically, a strategy for any system that must respond to its environment forever. The catch is explosion: turning a specification into the machine that yields a strategy can balloon in size, doubly exponentially for common logics.
Their tool is a new kind of specification piece, window counting constraints, which count how often events may occur inside a sliding window. Because such specifications behave monotonically, a synthesis procedure can refine or coarsen them step by step, working on smaller machines first. The authors show how this ladder can shrink the state space that builders must search. The paper offers a route toward synthesis tools that scale to real systems.
Catalog record
| CREATOR | Linda Feeken ORCID:0009-0003-7336-0859, Martin Fränzle ORCID:0000-0002-9138-8340 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 88 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-21852
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Towards the Usage of Window Counting Constraints in the Synthesis of Reactive Systems to Reduce State Space Explosion \rsuper * Linda Feeken ORCID:0009-0003-7336-0859, Martin Fränzle ORCID:0000-0002-9138-8340 Abstract . The synthesis of reactive systems aims for the automated construction of strategies for systems that interact with their environment. Whereas the synthesis approach has the potential to change the development of reactive systems significantly due to the avoidance of manual implementation, it still suffers from a lack of efficient synthesis algorithms for many application scenarios. The translation of the system specification into an automaton that allows for strategy construction (if a winning strategy exists) is nonelementary in the length of the specification in S1S and doubly exponential for LTL, raising the need of highly specialized algorithms. In this article, we present an approach on how to reduce this state space explosion in the construction of this automaton by exploiting a monotonicity property of specifications. For this, we introduce window counting constraints that allow for step-wise refinement or abstraction of specifications. In an iterative synthesis procedure, those window counting constraints are used to construct automata representing over- or under-approximations (depending on the counting constraint) of constraint-compliant behavior. Analysis results on winning regions of previous iterations are used to reduce the size of the next automaton, leading to an overall reduction of the state space explosion extent. We present the implementation results of the iterated synthesis for a zero-sum game setting as proof of concept. Furthermore, we discuss the current limitations of the approach in a zero-sum setting and sketch future work in non-zero-sum settings. Mar. 31, 2025Mar. 31, 2026 \titlecomment \lsuper * This is an extended version of [ FF24 ] presented at the GandALF 2024 conference. [a] [b] † † lmcs-doi: Volume 22, Issue 1, Paper 29 Introduction The automated translation of a system specification into its implementation is one of the most challenging problems in formal methods. Providing correct-by-construction artifacts, such synthesis offers great potential in the development of new systems by significantly reducing the need for manual work in the engineering process. In this article, we focus on synthesis for reactive systems, i.e. systems that are influenced by and interact with their environment. This interaction can be modeled as a game, in which the system tries to play according to its specification, whereas the moves of the environment can potentially impede the system from reaching its goal. Since the interaction between system and environment is typically of long-lasting nature without predefined end date, the game is infinite in the sense that a play of the game has infinite duration, while the arena, modeled as a graph, has finitely many states. The players play by moving a token from one state of the arena to the next. The player whose turn it is decides which of the outgoing transitions of the current state is chosen. A well-known type of game is the safety game: The system wins a play if it can avoid to reach predefined unsafe states. Otherwise, the environment wins. A player has a winning strategy, if it wins against all possible behavior of the other player. For two-player safety games on finite graphs, there always exists a winning strategy for one of the players and this winning strategy can be computed [ BL69 ] , [ Tho95 ] . However, the efficient computation of winning strategies (not only in the case of safety games) is still an open challenge in the synthesis of reactive systems. A common synthesis approach is to first generate a deterministic word automaton as game graph from specifications written as Linear Temporal Logic (LTL) formulae. Then, a strategy that is winning in the game is calculated. By construction, the strategy automatically satisfies the specification. Unfortunately, the construction of the deterministic word automaton leads to an automaton with a number of states that is doubly exponential in the length of the specification [ PR89 ] , making the whole strategy synthesis unfeasible for many applications. For avoiding the most expensive part of the synthesis procedure, there exist synthesis algorithms that start with a subset of the specification language LTL, such that it is possible to construct the game graph in a more efficient way. One example for that is the usage of the LTL subclass Generalized Reactivity(1) (GR(1)), which allows to construct and solve the game in time O(N^{3}) with N being the size of the state space [ PPS06 ] . While GR(1) is expressive enough for the specification of many systems [ MR15 ] , some specifications that do not fall into GR(1) remain unconsidered. For example, Maoz and Ringert mention the consideration of synthesis with counting patterns as future work in [ MR15 ] , but to the best of our knowledge, this has not been addressed yet. In this article, we deal with the request for heuristically efficient synthesis for some types of counting patterns as part of the system specification and present the idea of recursive synthesis for such games. The translation of the full system specification into a deterministic automaton as game arena is out of scope. We already start with a deterministic automaton accompanied with a set of counting patterns. The automaton can be obtained from a specification by any translation procedure (without encoding the counting patterns as well) or can arise naturally like it often occurs in the robotics domain, where the graph encodes the position of an automated system in specified areas like a factory floor. We call the considered counting patterns “window counting constraints” . These are of the form “The system plays action act at least k times out of l of its own moves.” with parameters k,l\in\mathbb{N},\,k\leq l and act encoding an action controllable by the system. The “at least” can also be replaced by “at most” . Such constraints arise naturally when the desired behavior of systems includes reoccurring elements. For example, an automated guided vehicle on a factory floor might need to charge its battery in at least two out of ten moves to avoid facing depleted batteries. By replacing “system” in the window counting constraint by “environment” , the constraint introduces rationality of the environment, since the environment will not primary behave antagonistically to the system in plays of the game, but will behave according to its own constraints. From the synthesis point of view, rationality of the environment implies information for the system on the environment, reducing the space of situations the system could face in a play of the game. The term “window” in the constraint-type name emphasizes the relation of those specifications to sliding windows in data stream monitoring [ PS06 ] . For the sake of readability, we also call them counting constraints for short. We avoid the direct full translation of the specifications in form of counting constraints into a graph and instead focus on the following two observations: (1) It is possible to influence how hard it is to satisfy a counting constraint by varying the parameters k , l in the counting constraints. More precisely, the (non-)existence of a strategy that fulfills the specification in a game with a set of counting constraints allows to make statements about the (non-)existence of such a