Petr Jancar ; Jiri Valusek - Structural Liveness of Immediate Observation Petri Nets

fi:10281 - Fundamenta Informaticae, April 18, 2023, Volume 188, Issue 3
Structural Liveness of Immediate Observation Petri NetsArticle

Authors: 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.


    Volume: Volume 188, Issue 3
    Published on: April 18, 2023
    Accepted on: February 28, 2023
    Submitted on: November 9, 2022
    Keywords: Computer Science - Logic in Computer Science

    Consultation statistics

    This page has been seen 146 times.
    This article's PDF has been downloaded 89 times.