The Reachability Probem for Petri Nets: Where do we stand in 2017?

LFCS LabLunch , Edinburgh, UK
pdf

I will talk about the reachability problem for vector addition systems. While its decidability is considered to be one of the great achievements in theoretical computer science, the massive gap in our knowledge concerning its complexity is a major embarrassment.

I will motivate the model and the relevance of the problem, recall its history and present the status quo. If time permits I'll present some ideas from our LICS'16 paper that fixes the complexity in dimension 2.