Affiliations: Dept of Computer Science, Faculty of Science, Palacký University in Olomouc, Czech Republic, [email protected], [email protected]
Correspondence:
[†]
Address for correspondence: Dept of Computer Science, Faculty of Science, Palacký University in Olomouc, Czech Republic.
Note: [*] Supported by Grant No. IGA_PrF_2022_018 and IGA_PrF_2021_022 of IGA of Palacký University Olomouc.
Abstract: 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.
Keywords: Petri nets, immediate observation nets, structural liveness, complexity
