Structural Liveness of Immediate Observation Petri NetsArticle
Authors: Petr Jancar ; Jiri Valusek
NULL##NULL
Petr Jancar;Jiri Valusek
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.