Abstract We show that the EXPSPACE-hardness result for structural liveness of Petri nets [Jančar and Purser, 2019] holds even for a simple subclass of conservative nets. As the main result we then show that for structurally live conservative nets the values of the least live markings are at most double exponential in the size of the nets, which entails the EXPSPACE-completeness of structural liveness for conservative Petri nets; the complexity of the general case remains unclear. As a proof ingredient with a potential of wider applicability, we present an extension of the known results bounding the smallest integer solutions of boolean combinations of linear (in)equations and divisibility constraints.

We look in detail at the structural liveness problem (SLP) for subclasses of Petri nets, namely immediate observation nets (IO nets) and their generalized variant called branching immediate multi-observation nets (BIMO nets), that were recently introduced by Esparza, Raskin, and Weil-Kennedy. We show that SLP is PSPACE-hard for IO nets and in PSPACE for BIMO nets. In particular, we discuss the (small) bounds on the token numbers in net places that are decisive for a marking to be (non)live. Comment: Final version