Best Paper Award at STOC 2019
The paper "The Reachability Problem for Petri Nets is Not Elementary", co-authored by Wojciech Czerwinski, who did a post-doc in our group, has won a best paper award at STOC 2019.
This work shows that the central verification problem for Petri nets is much harder than has been known since the landmark result of Richard Lipton in 1976. Petri nets, also known as vector addition systems, are a long established model of concurrency with extensive applications in modelling and analysis of hardware, software and database systems, as well as chemical, biological and business processes.
Congratulations to Wojciech and his co-authors Slawomir Lasota, Ranko Lazic, Jerome Leroux and Filip Mazowiecki!