Skip to main content

Separability of Reachability Sets of Vector Addition Systems

Wojciech Czerwinski ( University of Warsaw )

Given two families of sets F and G, the separability problem of sets from a class G by sets from a class F asks whether for two given sets U, V in G there exists a set S in F such that U is included in S and V has an empty intersection with S.

We show that separability problem of reachability sets of Vector Addition Systems by both modular and unary sets is decidable.

Short bio

Wojciech Czerwinski is an Assistant Professor at the University of Warsaw, where he obtained his PhD in 2013.  He has also been a postdoctoral researcher at the University of Bayreuth.  His main research interests are in the areas of automata theory, logic, verification and database theory.

Share this: