We’re excited to announce that Anton Varonka and Kazuki Watanabe (NII) won the Best Student Paper award for their Paper “On Piecewise Affine Reachability with Bellman Operators” at MFCS 2025!

Piecewise affine maps, despite their simple construction, can exhibit highly complex and unpredictable behavior, making it generally impossible to determine whether one point can reach another through repeated application of these maps—a challenge known as the reachability problem, which is undecidable even in two dimensions. In this paper, the authors focus on a significant subclass known as Bellman operators, which originate from Markov decision processes, widely used in decision-making and reinforcement learning. They demonstrate that the reachability problem for Bellman operators is decidable under natural conditions, and in two dimensions, it is always decidable, offering new insights that bridge theoretical complexity with practical applications in AI and dynamic systems.

The International Symposium on Mathematical Foundations of Computer Science (MFCS) conference series is a leading forum for original research across all areas of theoretical computer science. With a history dating back to 1972, MFCS is one of the longest-running and most respected conferences in the field.

Congratulations to Anton and Kazuki on this outstanding achievement!

Abstract

A piecewise affine map is one of the simplest mathematical objects exhibiting complex dynamics. The reachability problem of piecewise affine maps is as follows: Given two vectors s,t∈ℚd and a piecewise affine map f, is there n∈ℕ such that fn(s)=t? Koiran, Cosnard, and Garzon show that the reachability problem of piecewise affine maps is undecidable even in dimension 2. Most of the recent progress has been focused on decision procedures for one-dimensional piecewise affine maps, where the reachability problem has been shown to be decidable for some subclasses. However, the general undecidability discouraged research into positive results in arbitrary dimension. In this work, we investigate a rich subclass of piecewise affine maps arising as Bellman operators of Markov decision processes (MDPs). We consider the reachability problem restricted to this subclass and examine its decidability in arbitrary dimensions. We establish that the reachability problem for Bellman operators is decidable in any dimension under either of the following conditions (i) the target vector t is not the fixed point of the operator f; or (ii) the initial and target vectors s and t are comparable with respect to the componentwise order. Furthermore, we show that the reachability problem for two-dimensional Bellman operators is decidable for arbitrary s,t∈ℚd, in contrast to the known undecidability of reachability for general piecewise affine maps.

About Anton Varonka

Anton Varonka is a PhD student at the Doctoral College for Logical Methods in Computer Science at TU Wien Informatics, which is co-funded by the Marie Skłodowska-Curie Actions of the European Commission. He is supervised by Laura Kovács, Professor and Head of the Research Unit Formal Methods in Systems Engineering at TU Wien Informatics.

Anton holds a BSc in Informatics (2019) from Belarusian State University and an MSc in Computer Science (2021) from the University of Saarland. For his graduate studies, he was awarded a scholarship by the Saarbrücken Graduate School of Computer Science. During that time, Anton worked on the verification of linear dynamical systems in the group of Prof. Joёl Ouaknine at the Max-Planck Institute for Software Systems. For his PhD thesis, Anton focuses on exploring the boundary of decidability for questions related to formal verification of loop programs. In 2024, as part of his PhD studies, he spent four months at the National Institute of Informatics in Tokyo, Japan, under the supervision of Prof. Ichiro Hasuo.

Anton has presented his work at recognised conferences such as POPL 2022, ISSAC 2023, STACS 2024, and MFCS 2025, as well as multiple international workshops.

Curious about our other news? Subscribe to our news feed, calendar, or newsletter, or follow us on social media.