Structural Liveness of Immediate Observation Petri Nets

Article type: Research Article

Authors: Jančar, Petr | Valůšek, Jiří^{; *; †}

Affiliations: Dept of Computer Science, Faculty of Science, Palacký University in Olomouc, Czech Republic, petr.jancar@upol.cz, jiri.valusek01@upol.cz

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

DOI: 10.3233/FI-222146

Journal: Fundamenta Informaticae, vol. 188, no. 3, pp. 179-215, 2022