VASS Reachability: What's new and why do I care?

11^th June 2019, 11:00
Patrick Totzke

Abstract

I will talk about the reachability problem for vector addition systems, a.k.a. Petri Nets.
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.