ERC Consolidator Grant · 2025
Reachability in Infinite Systems at High Resolution
The reachability problem is central in computer science. One of the first steps towards understanding computation was showing undecidability of the problem for Turing machines. Recently with co-authors we achieved another milestone, which opens new horizons in the area: we determined the complexity of reachability for Vector Addition Systems with States (VASS) to be Ackermann-complete. The aim of this project is to obtain new milestones in understanding of the reachability problem and the related separability problem for computation models of concurrency and recursion. (1) The first task focuses on the reachability problem for VASS and its extensions. Despite recent progress, the…
From the public funding record at EU CORDIS. Describes the funded project, not the reviews below.