Paulin Jacobé de Naurois (CNRS - Univ. Paris 13), Reachability in Vector Addition with States and Split/Join Transitions

Schedule

Abstract

We define Vector Addition with States and Split/Join Transitions, a new model that extends VASS. Non-negative reachability in this model without join transitions is known to be equivalent to the decidability of MELL, and to be TOWER-hard. As a first step towards a reachability result, we define a suitable notion of covering graph for the model, and prove its finiteness and effective constructibility.