Automated Approach for Solving Infinite-state Polynomial Reachability Games
Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, Mehrdad Karrabi, Maximilian Seeliger, Đorđe Žikelić · 2026
Read Automated Approach for Solving Infinite-state Polynomial Reachability Games by Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, Mehrdad Karrabi, Maximilian Seeliger, Đorđe Žikelić (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-2605-10169.txt.
Description
Chatterjee and four colleagues solve infinite-state polynomial reachability games. These are two-player graph games where one player aims to reach a target set and the other aims to stay away. Such games matter for artificial intelligence and reactive synthesis, and many applications yield infinite-state versions. The paper asks whether the reaching player can win from a given start and how to compute a strategy.
Their first contribution is ranking certificates, a sound and complete proof rule showing the reaching player wins from a given start. Second, for polynomial games, where transitions and objectives are polynomial constraints over real variables, they give a fully automated algorithm. It computes a winning strategy plus a correctness witness. The algorithm is sound, semi-complete and sub-exponential in time. It solves literature examples beyond prior methods, including an optimal strategy for the classic Cinderella-Stepmother game at arbitrary precision.
Catalog record
| CREATOR | Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, Mehrdad Karrabi, Maximilian Seeliger, Đorđe Žikelić |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.10169