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

CREATORKrishnendu Chatterjee, Ehsan Kafshdar Goharshady, Mehrdad Karrabi, Maximilian Seeliger, Đorđe Žikelić
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE57 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.10169

Browse the full library · About the Tower of Babel