Abstract:  The covering and boundedness problems for
branching vector addition systems

Ranko Lazic
University of Warwick

Covering, boundedness and reachability are three fundamental problems
for vector addition systems.  In 1976, Lipton established that they are EXPSPACE-hard. 
The lower bound was matched by Rackoff two years later,
when he showed that covering and boundedness are in EXPSPACE.
Although reachability was proved decidable by Meyer and Kosaraju
several years later, little else remains known about its complexity.
For branching vector addition systems, an intriguing novel model of computation, not even
decidability of reachability is known yet.
However, covering and boundedness were shown decidable in 2005 by
Verma and Goubault-Larrecq.  We determine their complexity.

Joint work with Stephane Demri, Marcin Jurdzinski and Oded Lachish.